十种经典排序算法

总结图

以下代码如无特殊说明，均为从小到大排序。

0x01 选择排序$O(n^2)$

• 原理：每次在未排序数组中找到最大/最小的值，放到该数组最后一个位置，然后在剩下的未排序数组中继续循环上述操作。第$i$轮($i$从$0$开始)时在$[0,n-i-1]$中找最值。共寻找$n-1$轮。
• 特点：依次找到未排序列的最值。

public static void selectionSort(int[] arr, int n) {
    int maxIndex, temp;
    for (int i = 0; i < n - 1; i++) {
        maxIndex = 0;
        for (int j = 0; j < n - i; j++) {
            if (arr[j] > arr[maxIndex])
                maxIndex = j;
        }
        temp = arr[n-1-i];
        arr[n-1-i] = arr[maxIndex];
        arr[maxIndex] = temp;
    }
}

0x02 冒泡排序$O(n^2)$

• 原理：每次比较两个元素，如果顺序错误则交换位置。每次比较都会把最大/最小的值冒泡冒到最后，因此第$i$轮($i$从$0$开始)只需要比较$n-1-i$次，共需要比较$n-1$轮。
• 特点：比较并交换元素

public static void bubbleSort(int[] arr, int n) {
    int temp;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 1; j < n - i; j++) {
            if (arr[j-1] > arr[j]) {
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}

0x03 插入排序O($n^{2}$)

• 原理：在有序序列基础上（初始从1个元素开始），每次插入一个元素到相应位置。
• 特点：比较元素+移动数组

public static void insertSort(int[] arr, int n) {
    for (int i = 1; i < n; i++) {
        //第一个元素作为基准元素，从第二个元素开始把其插到正确的位置
        if (arr[i] < arr[i - 1]) {
            //如果第i个元素比前面的元素小
            int j = i - 1;
            int temp = arr[i];
            while (j >= 0 && temp < arr[j]) {
                //找正确位置，比arr[i]大的元素依次后移
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }
}

0x04 希尔排序$O(n^{1.3})$

又叫缩小增量排序，是插入排序的改进版。

• 原理：对数组按照一定间隔(即增量)进行分组，每个组都在组内进行插入排序，然后缩小增量再次分组，重复上述。核心是增量，常见的希尔增量初始化是$n/2$，每次缩小$2$倍。

• 常用增量序列：

  • 希尔增量：$\{N/2, (N / 2)/2, ..., 1\}$，最坏时间复杂度是$O(n^{2})$
  • Hibbard：$\{1, 3, ..., 2^k-1\}$，最坏时间复杂度是$O(n^{1.5})$
  • Sedgewick：$\{1, 5, 19, 41, 109...\}$该序列中的项或者是$9*4^i - 9*2^i + 1$或者是$4^i - 3*2^i + 1$
• 特点：分组，组内插入排序

// 希尔增量
public static void shellSort(int[] arr, int n) {
    for (int step = n / 2; step > 0; step /= 2) {
        // 对每个分组进行插入排序
        for (int i = 0; i < step; ++i) {
            for (int j = i + step; j < n; j += step) {
                if (arr[j] < arr[j - step]) {
                    int temp = arr[j];
                    int k = j - step;
                    while (k >= 0 && arr[k] > temp) {
                        arr[k + step] = arr[k];
                        k -= step;
                    }
                    arr[k + step] = temp;
                }
            }
        }
    }
}

// Hibbard增量
public static void shellSortByHibbard(int[] arr, int n) {
    // 先找到增量序列的最大值，然后递减到1
    int t = 1;
    while((1 << t) - 1 < n)     t++;
    t --;
    // 此时(2^t)-1是增量序列的最大值， 递减到1
    while (t > 0) {
        int step = (1 << t) - 1;t --;
        // 对每个分组进行插入排序
        for (int i = 0; i < step; ++i) {
            for (int j = i + step; j < n; j += step) {
                if (arr[j] < arr[j - step]) {
                    int temp = arr[j];
                    int k = j - step;
                    while (k >= 0 && arr[k] > temp) {
                        arr[k + step] = arr[k];
                        k -= step;
                    }
                    arr[k + step] = temp;
                }
            }
        }
    }
}

0x05 堆排序$O(n\log n)$

• 原理：利用堆这种数据结构，依次从堆顶中取出最值放到数组中。每次取出都要shiftDown调整树($O(\log n)$)，取$n$次。
• 特点：数据结构堆

private static int pop() {
    int t = arr[1];
    arr[1] = arr[size--];
    shiftDown(1);
    return t;
}

private static void push(int x){
    arr[++size] = x;
    shiftUp(size);
}
private static void shiftUp(int idx){
    while(idx > 1 && arr[idx] < arr[idx>>1]){
        int j = idx >> 1;
        int t = arr[idx]; arr[idx] = arr[j]; arr[j] = t;
        idx >>= 1;
    }
}
private static void shiftDown(int idx){
    while (idx * 2 <= size) {
        int j = idx << 1;
        if(j + 1 <= size && arr[j+1] < arr[j])
            j = j | 1;
        if(arr[idx] < arr[j])     break;
        int t = arr[idx]; arr[idx] = arr[j]; arr[j] = t;
        idx = j;
    }
}

public static int size;
private static int[] arr = new int[N]; //堆
private static int[] res = new int[N]; //结果数组
/***** main *****/
for(int i = 1 ; i <= n ; i ++){
    int x = sc.nextInt();
    push(x);
}
for(int i = 0 ; i < n ; i ++){
    res[i] = pop();
} 

0x06 快速排序/快排/三路快排$O(n\log n)$

• 原理：通过一趟排序将序列分为三部分，小于关键字+ 等于关键字 +大于关键字。然后进而对这两部分分别进行排序。当数组有大量重复元素时仍然保持较高性能。
• 特点：分治法，拆分数组

• 原始/二路快排：

  • 原始快排：将序列分为两部分，小于关键字+大于等于关键字（或小于等于关键字+大于关键字）
  • 二路快排：将序列分为两部分，小于等于关键字+大于等于关键字。避免了原始快排遇大量重复元素退化到$O(n^2)$

public static void quickSort(int l, int r){
    if (l >= r) return;
    // ===== partition分区操作 ===== 
    int t = l + r >> 1; // 取中间的值作为关键字
    int i = l - 1, j = r + 1, x = arr[t];
    while (i < j){
        do i ++ ; while (arr[i] < x);
        do j -- ; while (arr[j] > x);
        if (i < j) {
            int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
        }
    }
    quickSort(l, j);
    quickSort(j + 1, r);
}

边界问题：

• 递归$[l, j ]$和$[j + 1, r]$的时候，防止死循环，$t$不能取到右边界，要写$l + r $
• 递归$[l, i -1 ]$和$[i, r]$的时候，防止死循环，$t$不能取到左边界，要写$l + r + 1$

当$l=0, r = 1$时，结束时$j=t-1$

快排优化

小区间使用插入排序优化

0x07 归并排序$O(n\log n)$

• 原理：将已有序的子序列数组合并，得到完全有序的序列。一般是每次将两个有序的数组合并，称为2-路归并
• 特点：分治法，合并数组

//public static int[] temp = new int[N];
public static void mergeSort(int[] arr, int l, int r){
    if(l >= r)    return;
    int mid = l + r >> 1;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r)
        temp[k ++] = arr[i] <= arr[j] ? arr[i ++] : arr[j ++];
    while(i <= mid)
        temp[k ++] = arr[i ++];
    while(j <= r)
        temp[k ++] = arr[j ++];
    for(i=l, j =0 ; j < k ; i ++, j++)
        arr[i] = temp[j];
}

0x08 桶排序

• 原理：类似哈希的链地址法，利用函数映射将数组序列映射到一些槽/桶中，这样这些不同桶中的数天然具备了大小关系。比如$[10,34, 5,7,13,25,11,31,23]$，按$\div 10$关系映射结果如下。

桶	元素
0	$5, 7$
1	$10, 13, 11$
2	$25, 23$
3	$34,31$

可以看到，关系是$0$号桶元素 < $1$号桶元素 < $2$号桶元素 < $3$号桶元素，在每一个桶内进行元素排序，然后按照桶的顺序遍历元素即可。

• 特点：映射到桶+桶内排序+桶间天然有序
• 核心问题：映射函数，需要对不同的场景设计不同的映射函数。
• 注意：对负数特判

代码略

0x09 基数排序（LSD）

• 原理：遍历每一位上的数字，先看个位，按照个位的值放入0~10的桶中，然后依次取出(此时个位有序)，接着看十位，重复上述操作，此时十位有序。
• 特点：依次对个位十位百位进行排序。
• 注意：对负数特判

代码略

0x0A 计数排序

• 原理：遍历数组，计算每个数出现的次数，然后按顺序输出。
• 特点：统计出现次数
• 注意：对负数特判

代码略

桶/基数/计数 排序比较

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 桶排序：每个桶存储一定范围的数值；
• 计数排序：每个桶只存储一个值；
• 基数排序：根据值的每一位上的数字来分配桶；