【数据结构】排序算法大全-思路/复杂度/稳定性/Java代码

• 折半插入，适用于记录较多的场景，但是记录的移动次数和直接插入排序一样，故时间复杂度一样。最好是O(n)，最差是 O(n²)，平均是 O(n²)。空间复杂度是 O(1)。
• 特点：折半插入排序的比较次数和初始的序列无关，因为折半的次数一定，折一次比较一次。和直接插入比较，仅减少了比较次数，移动次数不变。
• 折半插入排序是稳定排序;

7. 希尔排序

7.1 希尔排序思路

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

希尔排序的步骤：

1. 首先根据初始序列的长度，选定一个递减增量序列t1，t2，t3......tk，其中ti>tj，tk = 1。
2. 根据选定的增量序列元素个数k，对初始序列进行k趟排序。
3. 根据增量序列的值ti，每趟排序会把初始序列划分成若干个元素的子序列，然后对这些子序列使用插入排序，因为这是递减增量序列，所以第一趟的排序，增量值最大，那么划分的子序列数量也就最多，每个子序列的元素也就越少，可以看做是一个“几乎”已经排好序的序列，当增量值越来越小的时候，子序列数量也就越少，每个子序列的元素也就越多，但是，基于前几次的排序，这些子序列虽然元素多，但是已经是一个“几乎”排好序的序列了，当最后一次排序的时候，即增量序列的值为1时，就是对整个无序序列进行排序，这时整个序列已经是一个“几乎”排好序的序列了。

7.2 希尔排序分析

import java.util.Arrays;

public class Code_ShellSort {

    public static void ShellSort(int[] arr) {
        // i表示希尔排序中的第n/2+1个元素（或者n/4+1）
        // j表示希尔排序中从0到n/2的元素（n/4）
        // r表示希尔排序中n/2+1或者n/4+1的值
        int i, j, r, tmp;
        // 划组排序
        for(r = arr.length / 2; r >= 1; r = r / 2) {
            for(i = r; i < arr.length; i++) {
                tmp = arr[i];
                j = i - r;
                // 一轮排序
                while(j >= 0 && tmp < arr[j]) {
                    arr[j+r] = arr[j];
                    j -= r;
                }
                arr[j+r] = tmp;
            }
        }
    }

    public static void main(String[] args){
        int[] arr=new int [] {1,23,2,6,8,100,25,45};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));
        System.out.println("排序后：");
        ShellSort(arr);
        System.out.println(Arrays.toString(arr));    
    }

}

8. 归并排序

8.1 归并排序思路

例子2：

import java.util.Arrays;
public class Code_MergeSort {
    public static void mergeSort(int [] arr){
        if(arr==null || arr.length<2){
            return;
        }
        mergeSort(arr,0,arr.length-1);
    }
    
    public static void mergeSort(int[] arr,int l,int r){
        if(l==r){
            return;
        }
        int mid = l+((r-l)>>1); //中点位置，即(l+r)/2
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);
        merge(arr,l,mid,r);
    }
    
    public static void merge(int[] arr,int l,int mid,int r){
        int [] help= new int[r-l+1];    //辅助数组
        int i=0;
        int p1=l; //左半数组的下标
        int p2=mid+1; //右半数组的下标
        
        //判断是否越界
        while(p1<=mid && p2<=r){
            help[i++]=arr[p1]<arr[p2] ? arr[p1++] : arr[p2++];
        }
        //p1没有越界，说明p2越界了，将左边剩余元素拷贝到辅助数组
        while(p1<=mid){
            help[i++]=arr[p1++];
        }
        //p2没有越界，说明p1越界了
        while(p2<=r){
            help[i++]=arr[p2++];
        }
        //将辅助数组元素拷贝会原数组
        for(i=0;i<help.length;i++){
            arr[l+i]=help[i];
        }
    }
    
    public static void main(String[] args){
        int[] arr = new int[]{10,1,25,100,95,15,45};
        System.out.print("排序前：");
        System.out.println(Arrays.toString(arr));
        System.out.print("排序后：");
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

9. 基数排序

9.1 基数排序思路

9.2 基数排序分析

9.3 基数排序代码

import java.util.*;

public class Code_RadixSort {
    
    public static void main(String[] args) {
        int[] arr = {63, 157, 189, 51, 101, 47, 141, 121, 157, 156,194, 117, 98, 139, 67, 133, 181, 12, 28, 0, 109};
        System.out.print("排序前：");
        System.out.println(Arrays.toString(arr));
        System.out.print("排序后：");
       radixSort(arr);
       System.out.println(Arrays.toString(arr));
    }

    /**
     * 高位优先法
     * @param arr 待排序列，必须为自然数
     */
    private static void radixSort(int[] arr) {
        //待排序列最大值
        int max = arr[0];
        int exp;//指数

        //计算最大值
        for (int anArr : arr) {
            if (anArr > max) {
                max = anArr;
            }
        }

        //从个位开始，对数组进行排序
        for (exp = 1; max / exp > 0; exp *= 10) {
            //存储待排元素的临时数组
            int[] temp = new int[arr.length];
            //分桶个数
            int[] buckets = new int[10];

            //将数据出现的次数存储在buckets中
            for (int value : arr) {
                //(value / exp) % 10 :value的最底位(个位)
                buckets[(value / exp) % 10]++;
            }

            //更改buckets[i]，
            for (int i = 1; i < 10; i++) {
                buckets[i] += buckets[i - 1];
            }

            //将数据存储到临时数组temp中
            for (int i = arr.length - 1; i >= 0; i--) {
                temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
                buckets[(arr[i] / exp) % 10]--;
            }

            //将有序元素temp赋给arr
            System.arraycopy(temp, 0, arr, 0, arr.length);
        }
    }
}

10. 桶排序

10.1 桶排序思路

10.2 桶排序分析

10.3 桶排序代码

import java.util.*;

public class Code_BucketSort {
    
    public static void bucketSort(int[] arr){
        
        // 计算最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        
        // 计算桶的数量
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<Integer>());
        }
        
        // 将每个元素放入桶
        for(int i = 0; i < arr.length; i++){
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }
        
        // 对每个桶进行排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
        }
        
        // 将桶中的元素赋值到原序列
        int index = 0;
        for(int i = 0; i < bucketArr.size(); i++){
            for(int j = 0; j < bucketArr.get(i).size(); j++){
                arr[index++] = bucketArr.get(i).get(j);
            }
        }  
    }
    
    public static void main(String[] args){
        int[] arr = new int[]{10,1,25,100,95,15,45};
        System.out.print("排序前：");
        System.out.println(Arrays.toString(arr));
        System.out.print("排序后：");
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

11. 计数排序

11.1 计数排序思路

1. 找出原数组中元素值最大的，记为max。
2. 创建一个新数组count，其长度是max加1，其元素默认值都为0。
3. 遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。
4. 创建结果数组result，起始索引index。
5. 遍历count数组，找出其中元素值>0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值<=0，依次处理count中剩下的元素。
6. 返回结果数组result。

import java.util.Arrays;
public class Code_CountSort {
    
    public static void main(String[] args){
        int [] arr=new int[] {10,23,1,5,2,0,1};
        System.out.print(Arrays.toString(arr));
        System.out.println();
        countSort(arr);
        System.out.print(Arrays.toString(arr));
    }

    public static void countSort(int[] arr){
        if(arr == null || arr.length<2){
            return;
        }
        int max = Integer.MIN_VALUE;   //最小的整数
        for(int i=0; i<arr.length; i++){
            max=Math.max(max, arr[i]);
        }
        int [] bucket=new int[max+1];//桶的下标代表数组中数值的大小，所以桶的长度要为数组中的最大值
        for(int i=0;i<arr.length;i++){
            bucket[arr[i]]++;//记数排序，相同值出现的次数
        }
        int i=0;
        for(int j=0;j<bucket.length;j++){ //将排好的数存会原数组
            while(bucket[j]-->0){
                arr[i++]=j;
            }
        }
    }
    
}

12. 比较器

方法1： 使用lambda表达式

Collections.sort(List, (a,b) -> x1 - x2);

方法2： 自定义Comparator方法

Collections.sort(List, new Comparator<E>(){
    public int compare(int a, int b){
      return a - b;
    }
});

public static class IdAscendingComparator implents Comparator{
    @Override
    public int compare(Student o1, Student o2) {
        // 返回负值o1排前面，返回正值o2排前面
        return o1.id - o2.id;
    }
}
Arrays.sort(students, new IdAscendingComparator());

PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>(){
        public int compare(Integer a,Integer b){
            return a.compareTo(b);
        }
    });
//  PriorityQueue<Integer> queue = new PriorityQueue();

PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer> (k,new Comparator<Integer>(){ @Override public int compare(Integer o1,Integer o2){
                return o2.compareTo(o1);
            }
        });
PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(k,(a,b)->b.compareTo(a)); 

13. 总结及应用

实际工程中的排序算法一般会将 归并排序、插入排序、快速排序综合起来，集大家之所长来应对不同的场景要求：

• 当要排序的元素为基本数据类型且元素个数较少时，直接使用 插入排序。因为在样本规模较小时（比如60），O(NlogN)的优势并不明显甚至不及O(N^2)，而在O(N^2)的算法中，插入排序的常数时间操作最少。
• 当要排序的元素为对象数据类型（包含若干字段），为保证稳定性将采用 归并排序。
• 当要排序的元素为基本数据类型且样本规模较大时，将采用 快速排序。

13.1 荷兰国旗问题：快速排序

问题：给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。

//利用快速排序的思想；

思路：利用两个指针L、R，将L指向首元素之前，将R指向尾元素之后。从头遍历序列，将当前遍历元素与num比较，若<num，则将其与L的右一个元素交换位置并遍历下一个元素、右移L；若=num则直接遍历下一个元素；若>num则将其和R的左一个元素交换位置，并重新判断当前位置元素与num的关系。直到遍历的元素下标到为R-1为止。

说明：L代表小于num的数的右界，R代表大于num的左界，partition的过程就是遍历元素、不断壮大L、R范围的过程。这里比较难理解的地方可能是为什么arr[i]<num时要右移L而arr[i]>num时却不左移R，这是因为对于当前元素arr[i]，如果arr[i]<num进行swap(arr[i],arr[L+1])之后对于当前下标的数据状况是知晓的（一定有arr[i]=arr[L+1]），因为是从头遍历到i的，而L+1<=i。但是如果arr[i]>num进行swap(arr[i],arr[R-1])之后对于当前元素的数据状况是不清楚的，因为R-1>=i，arr[R-1]还没遍历到。

public class Code_08_NetherlandsFlags {
    public static int[] partition(int[] arr,int L,int R,int p){
        int less=L;//左边下标从0开始
        int more=R;//右边下标从arr.length-1开始
        int current=L;//current作为遍历数组的下标
        while(current<more){
            if(arr[current]<p){
                swap(arr,less++,current++);
                            //less右移动一位,current++
            }
            else if(arr[current]>p){
                swap(arr,more--,current);
                           //more左移动一位，current不移动，因为current还要继续比较
            }
            else{
                current++;
                           //不做任何处理，current++继续向右遍历
            }
        }
        return new int[] {less+1,more-1};
    }
    //交换函数
    public static void swap(int[]arr,int i,int j){
        int tmp;
        tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    //打印数组
    public static void printArray(int[]arr){
        if(arr == null){
            return;
        }
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
    
    public static void main(String[] args){
        int[] arr=new int[]{2,1,8,5,3,9,7,4,10};
        int num=5;
        Code_08_NetherlandsFlags.partition(arr,0,arr.length-1,num);
        printArray(arr);
    }

13.2 小和问题：归并排序

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

对于数组[1,3,4,2,5] 
1左边比1小的数，没有； 
3左边比3小的数，1； 
4左边比4小的数，1、3； 
2左边比2小的数，1； 
5左边比5小的数，1、3、4、2； 
所以小和为1+1+3+1+1+3+4+2=16

方法一：暴力求解

  public static int smallSum(int[] arr){
        if(arr==null||arr.length<=0)
            return 0;
        int sum=0;
        for(int i=0,len=arr.length;i<len;i++){
            for(int j=0;j<i;j++){
                if(arr[j]<arr[i])
                    sum+=arr[j];
            }
        }
        return sum;
    }

方法二：利用归并排序的并入逻辑：

简单的做法就是遍历一遍数组，将当前遍历的数与该数之前数比较并记录小于该数的数。易知其时间复杂度为O(n^2)（0+1+2+……+n-1）。

更优化的做法是利用归并排序的并入逻辑：

public class Code_SmallSum {

    public static long smallSum(int[] arr){
        if(arr == null || arr.length<2){
            return 0;
        }
        return mergeSort(arr,0,arr.length-1);
    }
    
    public static long mergeSort(int[] arr,int l,int r){
        if(l == r){ //结束条件
            return 0;
        }
        int mid=l+( (r-l) >> 1);// 中点位置，即(l+r)/2
        return mergeSort(arr,l,mid)+mergeSort(arr,mid+1,r)+merge(arr,l,mid,r);
        //左边排序+右边排序+合并 产生的小和 相加在一起；
    }
    
    public static long merge(int[] arr,int l,int mid,int r){
        int[] help = new int[r-l+1]; //辅助数组
        int i=0;
        int p1=l; //左半数组的下标
        int p2=mid+1;//右半数组的下标
        long res=0; //小和的值
        //判断是否越界
        
        //如果左边指向的值小于右边指向的值，那么p1位置的值一定小于p2以后的所有值，因为是有序的，这时候产生小和
        while(p1<=mid && p2<=r){ 
            res+=arr[p1]<arr[p2] ? arr[p1]*(r-p2+1) : 0; //计算小和
            help[i++]=arr[p1]<arr[p2] ? arr[p1++] : arr[p2++]; // 排序
        }
        
        //p1没有越界，说明p2越界了，将左边剩余元素拷贝到辅助数组
        while(p1<=mid){
            help[i++]=arr[p1++];
        }
        //p2没有越界，说明p1越界了
        while(p2<=r){
            help[i++]=arr[p2++];
        }
        //将辅助数组元素拷贝会原数组
        for(i=0;i<help.length;i++){
            arr[l+i]=help[i];
        }
        return res;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for(int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.print(smallSum(arr));
    }
    
}

13.3 逆序对问题：归并排序

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

在一个数组中， 左边的数如果比右边的数大， 则这两个数构成一个逆序对， 请打印所有逆序对。

思路：所谓逆序对就是[4,2],[4,1],[5,1]…,也就是左边比右边大，那么有多少个逆序对就是,中间位置mid减去左指针下坐标P1+1个逆序对，也就是(mid-P1+1)个逆序对，把逆序对相加进行返回就是共有多少逆序对。

public static void reverseOrder(int[] arr) {
    if (arr==null || arr.length<2) {
        return ;
    }
    mergeSort(arr,0,arr.length-1);
}

public static int mergeSort(int[] arr, int l, int r) {        
    if (l == r) {
        return 0;
    }
    int mid = (l+r)/2;
    int k = mergeSort(arr, l, mid)+mergeSort(arr, mid+1, r)+merge(arr,l,mid,r);
    System.out.println("merge总逆序数："+k);
    return k;
}

public static int merge(int[] arr, int l, int mid, int r) {
    int merge_res=0;
    int[] help = new int[r - l + 1];   //help的长度不是一个大的N 而是每次分治 的长度
    int i=0;
    int p1 = l;
    int p2 = mid+1;
    
    while(p1 <= mid && p2 <= r) {
        if ( arr[p2] < arr[p1] ) {    //说明p2此时比p1中剩下的元素都小    
            merge_res += (mid-p1+1);  //核心 
            for(int k=0;k<mid-p1+1;k++) //打印此时的逆序对
                    System.out.println(arr[p1+k]+" "+arr[p2]);
        }
        help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++] ;
    }
    while(p1<=mid) {
        help[i++] = arr[p1++];
    }
    while (p2<=r) {
        help[i++] = arr[p2++];
    }
    //拷贝到 arr数组
    for (int j = 0; j < help.length; j++) {
        arr[l+j] = help[j];
    }
    System.out.println("merge_res:"+merge_res);
    return merge_res;
}

13.4 TopK问题：堆排序

TopK大：https://leetcode-cn.com/problems/xx4gT2/

TopK小：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

• 冒泡排序的改进：冒K次

也就是说不用全部排序；只挑出符合提议的K个就可以；

冒泡排序的思想，只不过最外层循环K次就可以了；

13.5 相邻两数的最大值：桶排序

题目：给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(n),且要求不能用非基于比较的排序

思路：首先为这N个数准备N+1个桶，然后以其中的最小值和最大值为边界将数值范围均分成N等分，然后遍历数组将对应范围类的数放入对应的桶中，下图以数组长度为9举例

题目问的是求如果排序后，相邻两数的最大差值。该算法巧妙的借助一个空桶（N个数进N+1个桶，必然有一个是空桶），将问题转向了求两个相邻非空桶

（其中可能隔着若干个空桶）之间前桶的最大值和后桶最小值的差值，而无需在意每个桶中进了哪些数（只需记录每个桶入数的最大值和最小值以及是否有数）

 public static int getMaxGap(int[] nums){
        if(nums == null || nums.length<2){
            return 0;
        }
        int len=nums.length;
        int min=Integer.MAX_VALUE;//数组中最小的元素
        int max=Integer.MIN_VALUE;//数组中最大的元素
        for(int i=0;i<len;i++){
            min=Math.min(min, nums[i]);
            max=Math.max(max, nums[i]);//找到最小值和最大值
        }
        if(min==max){
            return 0;//说明只有一种数，返回0；
        }
        boolean [] hasNum=new boolean[len+1];//表示桶里是否有数字
        int [] maxs = new int[len+1];
        int [] mins = new int[len+1];// 一个桶的三组信息hasNum、 maxs、 mins
        int index = 0;//桶的下标
        for(int i=0; i<len; i++){ //nums[i]应该放到哪个桶里
            index=bucket(nums[i],len,min,max);
            mins[index] = hasNum[index] ? Math.min(mins[index], nums[i]) : nums[i];
            maxs[index] = hasNum[index] ? Math.max(maxs[index], nums[i]) : nums[i];
            hasNum[index] = true;
        }
         //计算相邻非空桶中左桶的最大值和右桶的最小值的差值，找到最大的返回
        int res=0;
        int lastMax=maxs[0]; //非空左桶的最大值
        int i=1;
        for(;i<=len;i++){
            if(hasNum[i]){
                res=Math.max(res, mins[i]-lastMax);
                lastMax=maxs[i];
            }
        }
        return res;
    }
   
    public static int bucket(long num,long len,long min,long max){//计算num应该存放在哪个桶,long防止溢出
        return (int)((num-min)*len/(max-min));
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        System.out.print(getMaxGap(arr));
    }