栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

常见的排序算法和二分法查找

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

常见的排序算法和二分法查找

首先我们要明白一个思路,所有的for循环都可以通过递归的方式进行代替。
所以根据情况我们会选择不同的方式,选择用递归还是循环其实是思路一样的。

1.二分法查找

一般数组的查找通过遍历的方式,但是对于有序的数组,可以通过二分法,也就是对半查找的方式进行查找,每次找出中间值进行比较

1.如果中间值刚好和目标相等,就一次性输出。
2.如果中间值大于目标值,就说明这个值在0-中间值-1直接
3.如果中间值小于目标值,就说明这个值在中间值+1到100之间
4.根据上面的范围再次对半比较,直到相等为止

代码实现

    @Test
    public void getRepeatSubscript(){
        int[] array = {1,3,5,9,12,15,19,22,35,55,68,77,79,81,95,99};  //数组一定要排好序,不重复的
        int findValue = 56;   //这个就是我们所要查的值,也可能不在数组里
        int min = 0;   //刚开始是从0开始
        int max = array.length -1; //数组下标是数组长度减1
        //这里设置一个死循环,只有两种情况下退出,
        // 一种查到了,打印下标 退出循环
        // 第二种就是查不到,打印查不到,退出循环
        while (true){
            //如果查不到 最终会导致max < min
            // 因为每一次都会减1最为最大值或者最小值 这样下标会相邻,相等,相差
            if(max < min){
                System.out.println("目标值不在数组之内!");
                break;
            }
            int mid = (min + max)/2;
            if(findValue == array[mid]){
                //相等说明查到了
                System.out.println("下标为" + mid);
                break;
            }else if(findValue < array[mid]){
                //查找的值小于中间值,说明我们范围缩小到min-中间值-1
                max = mid - 1;

            }else {
                //查找的值大于中间值,说明我们范围缩小到中间值+1到max
                min = mid + 1;
            }
        }
    }

换成递归其实更容易理解

@Test
    public void getRepeatSubscript(){
        int[] array = {1,3,5,9,12,15,19,22,35,55,68,77,79,81,95,99};  //数组一定要排好序,不重复的
        int findValue = 56;   //这个就是我们所要查的值,也可能不在数组里
        int subscript = binarySearch(array, findValue, 0, array.length - 1);
        System.out.println("下标位置为" + subscript);

    }
    
    public static int binarySearch(int[] array, int findValue, int min, int max){
        if(max < min){
            return -1;  //查不到返回-1
        }
        int mid = (max + min)/2;
        if(array[mid] == findValue){
            return mid;
        }else if(array[mid] > findValue){
            return binarySearch(array,findValue,min,mid-1);
        }else {
            return binarySearch(array,findValue,mid+1,max);
        }
    }

更循环思路一致,代码更为简洁。

2.冒泡排序

冒泡排序是最简单的排序方式,就是相邻的两个元素比较,谁大谁放在后面。这样一轮下来最大的就是最后一个,再来一轮就是第二大的在倒数第二个。
这样一轮循环的次数是数组的长度,然后每轮交换就不需要每次都循环到头了,只有循环到上次找到最大值的位置就行了。

代码如下

  @Test
    public void bubbling(){
        int[] bubbleNums = {6,1,5,7,8,19,3,58,65,27,2};
        //假设数组长度为10 我们只要来9论即可
        for(int i = 1;i
            for(int j = 0;j
                //每轮比较也不要都比较到末尾,比较到上一次最大值出现的地方即可
                if(bubbleNums[j]>bubbleNums[j+1]){
                    //相邻的两个交换位置
                    int temp = bubbleNums[j];
                    bubbleNums[j] = bubbleNums[j+1];
                    bubbleNums[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(bubbleNums));
    }
3.选择排序

选择排序思路更简单,也是从第一个开始,依次朝着后面比较
每一轮都把最小的选择出来,放在最前面

代码如下

    @Test
    public void fastSorting(){
        int[] bubbleNums = {6,1,5,7,8,19,3,58,65,27,2};
        for(int i = 0;i
            for(int j = i + 1;j
                if(bubbleNums[i]>bubbleNums[j]){
                    int temp = bubbleNums[j];
                    bubbleNums[j] = bubbleNums[i];
                    bubbleNums[i] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(bubbleNums));
    }
4.插入排序

插入排序其实可以理解为我们玩扑克时摸牌的过程,我们在摸牌的时候手里的牌总是有序的,每摸一张牌,就把这张牌插到它应该在的位置。等所有的牌都摸完了以后,全部的牌就都有序了。

5.快速排序

快速排序是对冒泡的一种优化。
每次选取一个数,我们选择第一个数,比他小的在左边,大的在右边
这样不断递归,最后就得到了排序的结果

   @Test
    public void insertSorting(){
        int[] bubbleNums = {6,1,5,7,8,19,3,58,65,27,2};
        Quick_Sort(bubbleNums,0,bubbleNums.length-1);
        System.out.println(Arrays.toString(bubbleNums));
    }

    void Quick_Sort(int[]arr, int begin, int end){
        if(begin > end)
            return;
        int tmp = arr[begin];
        int i = begin;
        int j = end;
        while(i != j){
            while(arr[j] >= tmp && j > i)
                j--;
            while(arr[i] <= tmp && j > i)
                i++;
            if(j > i){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        arr[begin] = arr[i];
        arr[i] = tmp;
        Quick_Sort(arr, begin, i-1);
        Quick_Sort(arr, i+1, end);
    }
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/957228.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号