常见六种排序算法(java版本)

Java资料站

共 14340字,需浏览 29分钟

 ·

2021-05-14 12:26

点击上方蓝色字体,选择“标星公众号”

优质文章,第一时间送达

什么是排序算法的稳定性?

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

冒泡排序算法

时间/空间复杂度

最好平均最坏辅助存储稳定
O(n)O(n²)O(n²)O(1)Y

实现原理:
冒泡排序算法使用双层循环嵌套,依次比较相邻的两个元素,按照升/降序,把最大/小的数字冒泡到最外围
第一层循环,把最大/小的数字冒泡到最外围
第二层循环,即要进行几次一层循环

public static int [] maopao1(int array[]){
    int t;
    for(int i = 0;i <array.length;i ++){
        for(int j = 0;j < array.length-i-1;j ++){
            if(array[j] < array[j+1]){
                t = array[j+1];
                array[j+1] = array[j];
                array[j] = t;
            }
        }
    }
    return array;
}

选择排序算法

时间/空间复杂度

最好平均最坏辅助存储稳定
O(n²)O(n²)O(n²)O(1)N

实现原理:
也是双重循环,假设升序排列,假设下标为0的元素为最小值min,依次用min与后面的元素进行比较,如果后面的元素比min小,则把该元素的下标赋给min,直到与所有元素比较,这样就找到了最小的元素的下标,然后把最小的元素的下标与第一个元素互换,选择性的把最小的元素排列在了数组的头部位置,继续把第二个元素当作除了第一个元素以外的最小值,与后面比较…

//选择
    public static int [] selectSort(int[] array){
        int t = 0;
        int max = 0;
        for(int i = 0; i < array.length;i ++){
            max = i;
            for(int j = i;j < array.length;j ++){
                if(array[j] > array[max]){
                    max = j;
                }
            }
            //如果i就是max,不用交换位置
            if(i != max){
                t = array[max];
                array[max] = array[i];
                array[i] = t;
            }
        }
        return array;
    }

选择排序算法不稳定,举例:
5,12,13,12,7进行从小到大的排序
第一趟:5, 12(1), 13, 12(2), 7
第二趟: 5, 7, 13 12(2) 12(1)
12(1)原来是在12(2)前面,但经过选择排序,12(1)被换到了12(2)的后面,所以不稳定

快速排序算法

时间/空间复杂度

最好平均最坏辅助存储稳定
O(nlog(n))O(nlog(n))O(n²)O(log(2)(n))N

实现原理:
{12 , 14 , 8 , 16 , 7 , 15}
left(i)=k --------------- right(j)
快速排序算法运用分而治之的思想,两个指针分别在数组的左边和右边
假设从小到大排序 K = array[left]为基准值
从左边开始的指针找到比K大的。------------- K 大 … …
从右边开始的指针找到比K小的。------------ K … … 小
交换left与right的指针 ---------------------------- K 小 … 大
当i=j时,比较k与array[i]的大小---------------- K … i=j …
当K > array[i]时互换 ------------------------------ i … K …

//快速排序:分而治之的思想,一左一右两个指针,以left为基准
    public static void quickSort(int left,int right,int [] arr){
        //从小到大排序
        int i = left;
        int j = right;
        //注意:i也不能等于j,当i==j说明排序完成,最后一次的左/右部分只有一个数字
        if(i >= j)
            return ;
        //定义一个基准值
        int k = arr[left];
        while(i != j){
            //i不能大于j
            if(arr[i] <= k && i < j){
                i++;
            }
            if(arr[j] > k && i < j){
                j --;
            }
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //i == j
        if(k > arr[i]){
            int temp = arr[left];
            arr[left] = arr[i];
            arr[i] = temp;
        }
        //递归
        quickSort(left,i-1,arr);
        quickSort(i,right,arr);
    }

快速排序算法不稳定,举例:
12,14(1),8,14(2),7,15进行从小到大的排序
第一趟:12,7,8,14(12),14(1),15
14(1)原来是在14(2)前面,但经过快速排序,14(1)被换到了14(2)的后面,所以不稳定

归并排序算法

时间/空间复杂度

最好平均最坏辅助存储稳定
O(nlog(n))O(nlog(n))O(nlog(n))O(n)Y

辅助存储为O(n)是因为新建了一个数组来合并两个数组

实现原理:
1.自上而下分割数组,把所有的数组拆分成单一的数组
2.自下而上合并数组,两两把单一数组合并

//归并排序:先分割,再合并
    //分割
    public static int [] separate(int [] arr){
        if(arr.length < 2){
            return arr;
        }
        //找中位数,Math.floor(a)得到小于a的最大整数
        //可能数组数量为奇数的情况下
        int mid = (int)Math.floor(arr.length/2);
        //分成两个
        int [] left = Arrays.copyOfRange(arr,0,mid);//(左闭右开]
        int [] right = Arrays.copyOfRange(arr,mid,arr.length);//因为下标从0开始,所以本来就取不到arr.length,不用减一
        //递归
        return merge(separate(left),separate(right));
    }
    //合并
    public static int [] merge(int [] left,int [] right){
        int [] arr = new int[left.length+right.length];
        if(arr.length < 2){
            //判断如果数组长度小于2,那么必定其中一个数组有值,一个无值,返回有值的即可
            return left.length == 0?right:left;
        }
        int i=0,j=0,k=0;
        while(i<left.length && j<right.length){
            //把小的那个数组添加到新数组中
            if(left[i] < right[j]){
                arr[k++] = left[i++];
            }else{
                arr[k++] = right[j++];
            }
        }
        //最后还有一个没有添加到arr新数组中,这时加上去
        while(i < left.length){
            arr[k++] = left[i++];
        }while(j < left.length){
            arr[k++] = right[j++];
        }
        return arr;
    }

直接插入排序算法

时间/空间复杂度

最好平均最坏辅助存储稳定
O(n)O(n²)O(n²)O(1)Y

实现原理:
创建一个哨兵位置,哨兵并不在数组中,只是暂存数组中的元素
1.从第一个元素开始,我们可以认为该元素已经被排序了
2.取出下一个元素,从已经排好序的元素中从后往前扫描
3.若是升序,只需判断排序好的序列中比哨兵大的元素即可,因为是从后往前扫描的

初始:
哨兵() (32) (14 17 64 58)
第一趟:
14放到哨兵中,14 < 32 32右移,14放到32原来的位置上
哨兵(14) (14 32) (17 64 58)
第二趟:
17放到哨兵中,17<32,32右移,17>14,从哨兵中把17取出来,放到32原来的位置上
哨兵(17) (14 17 32) (64 58)
第三趟:
64放到哨兵中,64>32,跳过,下一步
哨兵(64) (14 17 32 64) (58)
第四趟:
58放到哨兵中,58<64,64右移,58>32,从哨兵中把58取出来,放到64原来的位置上
哨兵(58) (14 17 32 64 58)

public static void insertSortAsc(int [] arr){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];//temp哨兵位置
            int index=i-1;//index代表与哨兵比较的值的下标
            //index不能小于0&&升序,把index指向的数值与哨兵作比较,如果哨兵小于index指向的元素
            while(index >=0 && arr[index] > temp){
                //把index指向的元素后移一位
                arr[index+1] = arr[index];
                index --;//index--确保从已经排好的元素中选择,从后往前扫描
            }
            //这时,在拍排的序列中,比哨兵大的元素都已在哨兵右边,此时把哨兵放到index+1位置上即可
            arr[index+1] = temp;
        }
    }

希尔排序算法

时间/空间复杂度

最好平均最坏辅助存储稳定
O(n)O(n^(3/2))O(n^(3/2))O(1)N

实现原理:
希尔排序也叫加强版的插入排序(增量递减插入排序),先将整个待排序序列分割成若干个子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行一次直接插入排序
举例:
当增量gap=10/2=5时,间隔4个进行比较,
31 12 1 45 67 98 21 -1 0 0
31--------------- 98
----12--------------- 21
--------1----------------- -1
-----------45---------------- 0
--------------- 67------------- 0
第一趟排序后结果
31 12 -1 0 0 98 21 1 45 67
第二趟时gap = 5/2 = 2,排序结果
-1 0 0 1 21 12 31 67 45 98
第三趟gap = 2 / 2 = 1,当gap=1时就变成了直接插入排序
-1 0 0 1 12 21 31 45 67 98

public static void shellSortAsc(int[] arr){
        int gap=arr.length/2;//增量,初始为数组长度一半
        while(gap>=1){
            for(int i=gap;i<arr.length;i++){//这里其实就是插入排序,不过把原来的i=1变成i=gap
                int temp=arr[i];
                int index=i-gap;
                while(index>=0&&arr[index]>temp){
                    arr[index+gap]=arr[index];
                    index=index-gap;
                }
                arr[index+gap]=temp;
            }
            gap=gap/2;//增量递减
        }
    }

希尔排序算法不稳定,举例:
5(1),7,5(2),4,3,2,1进行从小到大的排序
gap = 7/2 = 3
第一趟:1,3,2,4,7,5(2),5(1)
5(1)原来是在5(2)前面,但经过希尔排序,5(1)被换到了5(2)的后面,所以不稳定




版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:

https://blog.csdn.net/suo_jia_hao/article/details/116565973






锋哥最新SpringCloud分布式电商秒杀课程发布

👇👇👇

👆长按上方微信二维码 2 秒





感谢点赞支持下哈 

浏览 10
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报