MENU

十种经典排序算法

April 14, 2021 • Read: 1179 • 编程之路,Algorithm

总结图

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

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 计数排序

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

桶/基数/计数 排序比较

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

  • 桶排序:每个桶存储一定范围的数值;
  • 计数排序:每个桶只存储一个值;
  • 基数排序:根据值的每一位上的数字来分配桶;
- - - 结束 - - -
  • 文章标题:十种经典排序算法
  • 文章链接:https://blog.canye365.cn/archives/376.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )