十大经典排序算法动画与解析

排序算法可以分为内部排序和外部排序。
内部排序是数据记录在内存中进行排序。
而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
用一张图概括：
时间复杂度与空间复杂度

关于时间复杂度：

  1. 平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
  2. 线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
  3. O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

  4. 线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

    关于稳定性：

  5. 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

  6. 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

    冒泡排序

    1. public class BubbleSort {
    2.  @Test
    3.  public void test1(){
    4.      int[] arr = new int[]{1,5,3,4,2};
    5.      int res = sort2(arr);
    6.      System.out.println("共遍历了"+res+"次");
    7.      System.out.println(Arrays.toString(arr));
    8.  }
    10.  public void sort(int[] arr){
    11.      for(int i=arr.length-1; i>0; i--){
    12.          for(int j=0;j<i;j++){
    13.              if(arr[j]>arr[j+1]){
    14.                  swap(arr,j,j+1);
    15.              }
    16.          }
    17.      }
    18.  }
    20.  public int sort2(int[] arr){
    21.      int res=-1;
    22.      for(int i=arr.length-1; i>0; i--){
    23.          //使用flag记录本次遍历是否进行了交换：true：没有进行交换
    24.          //如果为true也就是待排序列已经有序，该数组的排序已经完成
    25.          boolean flag = true;
    26.          for(int j=0;j<i;j++){
    27.              if(arr[j]>arr[j+1]){
    28.                  swap(arr,j,j+1);
    29.                  flag = false;
    30.              }
    31.          }
    32.          if(flag){
    33.              res = arr.length-i;
    34.              break;
    35.          }
    36.          if(i==1){
    37.              res = arr.length-1;
    38.          }
    39.      }
    40.      return res;
    41.  }
    43.  private void swap(int[] arr,int i,int j){
    44.      int tmp = arr[i];
    45.      arr[i] = arr[j];
    46.      arr[j] = tmp;
    47.  }
    48. }

    选择排序

    ```java public class SelectionSort { @Test public void test1(){

    1.  int[] arr = new int[]{1,5,3,4,2};
    2.  sort2(arr);
    3.  System.out.println(Arrays.toString(arr));

    }

  1. public void sort(int[] arr){
  2.     for(int i=0; i<arr.length-1; i++){
  3.         int minValue = Integer.MAX_VALUE;
  4.         int minIndex = i;
  5.         for(int j=i+1;j<arr.length; j++){
  6.             if(arr[j] < minValue){
  7.                 minValue = arr[j];
  8.                 minIndex = j;
  9.             }
  10.         }
  11.         if(minIndex!=i){
  12.             swap(arr,i,minIndex);
  13.         }
  14.     }
  15. }
  17. public void sort2(int[] arr){
  18.     for(int i=0; i<arr.length-1; i++){
  19.         int minIndex = i;
  20.         for(int j=i+1;j<arr.length; j++){
  21.             if(arr[j] < arr[minIndex]){
  22.                 minIndex = j;
  23.             }
  24.         }
  25.         if(minIndex!=i){
  26.             swap(arr,i,minIndex);
  27.         }
  28.     }
  29. }
  31. private void swap(int[] arr,int i,int j){
  32.     int tmp = arr[i];
  33.     arr[i] = arr[j];
  34.     arr[j] = tmp;
  35. }

}

  1. <a name="lxKTI"></a>
  2. # 插入排序
  3. ```java
  4. public class InsertSort {
  5.     @Test
  6.     public void test1(){
  7.         int[] arr = new int[]{1,5,3,4,2};
  8.         sort(arr);
  9.         System.out.println(Arrays.toString(arr));
  10.     }
  12.     public void sort(int[] arr){
  13.         for(int i =1;i<arr.length;i++){
  14.             //记录当前未排序元素cur
  15.             int cur = arr[i];
  16.             for(int j=i-1;j>=0;j--){
  17.                 //如果当前未排序元素比当前已排序元素小，则已排序元素后移一位
  18.                 if(cur<arr[j]){
  19.                     arr[j+1]=arr[j];
  20.                     if(j==0){
  21.                         arr[j]=arr[i];
  22.                     }
  23.                 }else{
  24.                     //如果当前未排序元素大于等于当前已排序元素，则插入到当前已排序元素后面
  25.                     arr[j+1]=cur;
  26.                     break;
  27.                 }
  28.             }
  29.         }
  30.     }
  32. }

希尔排序

public class ShellSort {
    @Test
    public void test1(){
        int[] arr = new int[]{1,5,3,4,2};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sort(int[] arr){
        int gap = arr.length/2;
        while(gap>0){
            for(int i=gap;i<arr.length;i++){
                int tmp = arr[i];
                int j = i-gap;
                while(j>=0&&arr[j]>tmp){
                    arr[j+gap] = arr[j];
                    j-=gap;
                }
                arr[j+gap] = tmp;
            }
            gap = Math.floorDiv(gap,2);
        }
    }
}

归并排序

归并排序、随机快排

public class MergeSort {
    @Test
    public void test1(){
        int[] arr = new int[]{1,5,3,4,2};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sort(int[] arr){
        mergeSort(arr,0,arr.length-1);
    }
    private void mergeSort(int[] arr,int l,int r){
        int[] res = null;
        if(l>=r){
            return;
        }
        int mid = l+((r-l)>>1);
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);
        sortInL_R(arr,l,r);
    }

    private void sortInL_R(int[] arr,int l,int r){
        int mid = l+((r-l)>>1);
        int lLength = mid-l+1;
        int[] tempArr = Arrays.copyOfRange(arr, l, r + 1);
        int idx=l;
        int i=0,j=lLength;
        while(j<tempArr.length&&i<lLength){
            if(tempArr[i] > tempArr[j]){
                arr[idx++]=tempArr[j++];
            }
            else{
                arr[idx++]=tempArr[i++];
            }
        }
        while(i<lLength){
            arr[idx++]=tempArr[i++];
        }
        while(j<tempArr.length){
            arr[idx++]=tempArr[j++];
        }
    }
}

快速排序

归并排序、随机快排

public class PartitionAndQuickSort {

    @Test
    public void test1(){
        int[] arr = new int[]{1,5,3,4,2,56,33,87,89,25,6,7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    @Test
    public void test2(){
        int[] arr = new int[]{1,5,3,4,2,56,33,87,89,25,6,7};
        sort2(arr);
        System.out.println(Arrays.toString(arr));
    }

    @Test
    public void test3(){
        int[] arr = new int[]{1,5,3,4,2,56,33,87,89,25,6,7};
        sort3(arr);
        System.out.println(Arrays.toString(arr));
    }

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

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

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

    /**
     * 一次排一个数
     */
    private void quickSort(int[] arr,int L,int R){
        if(L>=R){
            return;
        }
        int partition = partition(arr, L, R);
        quickSort(arr,L,partition-1);
        quickSort(arr,partition+1,R);
    }

    /**
     * 一次排多个数
     */
    private void quickSort2(int[] arr,int L,int R){
        if(L>=R){
            return;
        }
        int[] ints = netherlandsFlag(arr, L, R);
        quickSort2(arr,L,ints[0]-1);
        quickSort2(arr,ints[1]+1,R);
    }

    /**
     * 一次排多个数
     * 并且随机选择基准数，进一步降低排序的时间复杂度
     */
    private void quickSort3(int[] arr,int L,int R){
        if(L>=R){
            return;
        }
        //随机选择位置，与arr[R]上的数做交换
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
//        swap(arr,L+(int)(Math.random()*(R-L+1)),R);
        int[] ints = netherlandsFlag(arr, L, R);
        quickSort3(arr,L,ints[0]-1);
        quickSort3(arr,ints[1]+1,R);
    }

    /**
     * 将数组arr下标在[L,R]中比arr[R]小的排到数组的左边，比arr[R]大的排在数组右边，arr[R]排在两者中间
     * 返回arr[R]的下标
     */
    private int partition(int[] arr,int L,int R){
        if(L>R){
            return -1;
        }
        if(L==R){
            return L;
        }
        //设置le为小于等于区域的右下标
        int le = L-1;
        int idx = L;
        //对【idx，R-1】范围中的元素进行分组
        while(idx<R){
            if(arr[idx]<=arr[R]){
                swap(arr,idx,++le);
            }
            idx++;
        }
        //将下标为R的元素交换到最终位置
        swap(arr,++le,R);
        return le;
    }

    /**
     * 将数组arr下标在[L,R]中比arr[R]小的排到数组的左边，比arr[R]大的排在数组右边，等于arr[R]排在两者中间
     * 返回等于arr[R]区域的左右下标
     */
    public int[] netherlandsFlag(int[] arr, int L, int R){
        if(L>R){
            return new int[]{-1,-1};
        }
        if(L==R){
            return new int[]{L,L};
        }
        //设置l、r分别为小于区域的右下标和大于区域的左下标
        int l = L-1,r = R;
        int idx = L;
        //小于区域的右下标大于等于大于区域的左下标时跳出循环，此时只有下标为R的数没有终于最终位置
        while(idx<r){
            if(arr[idx]==arr[R]){
                idx++;
            }else if(arr[idx]<arr[R]){
                swap(arr,++l,idx++);
            }else{
                swap(arr,--r,idx);
            }
        }
        //将下标为R的数交换到最终位置
        swap(arr,r,R);
        return new int[]{l+1,r};
    }

    private void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

堆排序

public class HeapSort {
    @Test
    public void test1(){
        int[] arr = generateRandomArray(10,20);
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sort(int[] arr){
        for(int i=arr.length-1; i>=0; i--){
            makeDump(arr,0,i);
            swap(arr,0,i);
        }
    }

    private void makeDump(int[] arr,int L,int R){
        for(int i=L+1;i<=R;i++){
            dump(arr,i);
        }
    }

    private void dump(int[] arr,int i){
        if(i<=0){
            return;
        }
        int parent;
        if(i%2==0){
            parent = (i-1)/2;
        }else{
            parent = i/2;
        }
        if(arr[parent]<arr[i]){
            swap(arr,i,parent);
            dump(arr,parent);
        }
    }

    private void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }
}

桶排序、计数排序和基数排序的区别

计数排序

/**
 * Description 计数排序 待排数组只能为正整数
 *
 * @ClassName algorithm.sort.CountingSort
 * @Version 1.0
 * @Date: 2022/2/18 17:22
 * @Author xuyi
 */
public class CountingSort {
    @Test
    public void test1(){
        int[] arr = new int[]{1,5,3,4,2,56,33,87,89,25,6,7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }


    public void sort(int[] arr){
        if(arr == null||arr.length<2){
            return;
        }
        countingSort(arr);
    }

    private void countingSort(int[] arr){
        int bucketLength = getMax(arr)+1;
        int[] bucket  = new int[bucketLength];
        for(int num:arr){
            bucket[num]++;
        }

        int idx = 0;
        for(int i=0;i<bucket .length;i++){
            while(bucket [i]>0){
                arr[idx++]=i;
                bucket [i]--;
            }
        }
    }

    private int getMax(int[] arr){
        int max = arr[0];
        for(int i =1;i<arr.length;i++){
            if(arr[i]>max){
                max = arr[i];
            }
        }
        return max;
    }
}

桶排序

桶排序复杂度分析

时间复杂度：

  1. 时间复杂度：O(N + C)，C=N*(logN-logM)

对于待排序序列大小为 N，共分为 M 个桶，主要步骤有：

N 次循环，将每个元素装入对应的桶中

M 次循环，对每个桶中的数据进行排序（平均每个桶有 N/M 个元素）

一般使用较为快速的排序算法，时间复杂度为 O(NlogN)，实际的桶排序过程是以链表形式插入的。

整个桶排序的时间复杂度为：

O(N)+O(M∗(N/M∗log(N/M))) = O(N)+O(N∗(log(N/M)) = O(N)+O(C）= O(N∗(log(N/M)+1))

当 N = M 时，复杂度为 O(N)

额外空间复杂度：O(N + M)

稳定性分析

桶排序的稳定性取决于桶内排序使用的算法。

public class BucketSort {
    private InsertSort insertSort = new InsertSort();

    @Test
    public void test1(){
        int[] arr = new int[]{1,5,3,4,2,56,33,87,89,25,6,7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sort(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        bucketSort(arr,3);
    }

    /**
     * bucketNum 桶数量
     */
    private void bucketSort(int[] arr,int bucketNum){
        int[] maxAndMin = getMaxAndMin(arr);
        int min = maxAndMin[0],max = maxAndMin[1];
        //计算桶大小 bucketSize
        int bucketSize = (int)Math.floor((max-min)/bucketNum)+1;
        int[][] buckets = new int[bucketNum][0];
        //将每一个元素放入适当的桶中
        for (int i=0;i<arr.length;i++){
            int idx = (arr[i] - min)/bucketSize;
            buckets[idx] = arrAppend(buckets[idx],arr[i]);
        }
        int arrIdx = 0;
        for(int[] bucket:buckets){
            if(bucket.length<=0){
                continue;
            }
            insertSort.sort(bucket);
            for(int num:bucket){
                arr[arrIdx++] = num;
            }
        }
    }

    private int[] getMaxAndMin(int[] arr){
        int max = arr[0];
        int min = arr[0];
        for(int i =1;i<arr.length;i++){
            if(arr[i]>max){
                max = arr[i];
            }
            if(arr[i]<min){
                min=arr[i];
            }
        }
        return new int[]{min,max};
    }

    /**
     54     * 自动扩容，并保存数据
     55     *
     56     * @param arr
     57     * @param value
     58     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

基数排序

public class RadixSort {

    @Test
    public void test1(){
        int[] arr = new int[]{1,5,3,4,2,56,33,87,89,25,6,7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sort(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        int maxBit = getMaxBit(arr);
        radixSort(arr,maxBit);
    }

    private int getMaxBit(int[] arr){
        int max = getMax(arr);
        return getLength(max);
    }

    private int getLength(int num){
        if(num==0){
            return 1;
        }
        int len = 0;
        for(int tmp=num;tmp!=0;tmp/=10){
            len++;
        }
        return len;
    }

    private int getMax(int[] arr){
        int max = arr[0];
        for(int i =1;i<arr.length;i++){
            if(arr[i]>max){
                max = arr[i];
            }
        }
        return max;
    }

    private void radixSort(int[] arr,int maxBit){
        int mod = 10;
        int dev = 1;
        for(int i=0;i<maxBit;i++,mod*=10,dev*=10){
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] buckets = new int[mod*2][0];
            for(int j=0;j<arr.length;j++){
                int bucket = (arr[j]%mod)+mod;
                buckets[bucket] = arrAppend(buckets[bucket],arr[j]);
            }
            int pos = 0;
            for(int[] bucket:buckets){
                for(int num:bucket){
                    arr[pos++] = num;
                }
            }
        }
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}