速通版

排序类别 排序名称 时间复杂度（最好 / 平均 / 最坏） 空间复杂度 稳定性
插入排序 直接插入排序 O(n) / O(n²) / O(n²) O(1) 稳定
插入排序 折半插入排序 O(n) / O(n²) / O(n²) O(1) 稳定
插入排序 希尔排序 O(n log n) ~ O(n²) O(1) 不稳定
交换排序 冒泡排序 O(n) / O(n²) / O(n²) O(1) 稳定
交换排序 快速排序 O(n log n) / O(n log n) / O(n²) O(log n) 不稳定
选择排序 简单选择排序 O(n²) / O(n²) / O(n²) O(1) 不稳定
选择排序 堆排序 O(n log n) / O(n log n) / O(n log n) O(1) 不稳定
归并排序 O(n log n) / O(n log n) / O(n log n) O(n) 稳定
基数排序 O(d · (n + k)) O(n + k) 稳定

排序算法

插入排序

  • O(n^2)不可取

直接插入排序

思路:
找到upper_bound,插入后将后面的数组下标加一,重点是找到插入下标.

1
2
3
4
5
6
7
8
9
10
11
for(int i=2;i<=n;i++){
    int temp=a[i],index=i;
    for(int j=i-1;j>=1;j--){
        if(a[j]>temp) index--;
        else break;
    }
    for(int j=i-1;j>index;j--){
        a[j+1]=a[j];
    }
    a[index]=temp;
}

折半插入排序

思路与上面相同,只是这次用二分法找到upper_bound

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(int i=2;i<=n;i++){
    int temp=a[i],index=i;
    int l=1,r=i-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]>temp){
            r=mid-1;
        }
        else l=mid+1;
    }
    for(int j=i-1;j>=l;j--){
        a[j+1]=a[j];
    }
    a[l]=temp;
}
  • 尽管查找时间为O(logn),但移动时间为O(n),故总复杂度仍然是O(n*n)

希尔排序

每次取增量的一半进行分组排序,直到增量为1,保证完全有序

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int gap = n / 2; gap >= 1; gap /= 2) {  // 外层：缩小 gap
        // 对于当前 gap，进行分组插入排序
        for (int i = gap; i < n; i++) {  // 从 gap 开始，每个元素插入到前面的子序列
            int temp = a[i];  // 当前元素
            int j = i;
            // 在子序列中向后移（步长 gap）
            while (j >= gap && a[j - gap] > temp) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = temp;  // 插入
        }
    }

交换排序

冒泡排序

每一轮排好一个数字,n个数字排n-1轮

1
2
3
4
5
6
7
8
9
10
11
for(int i=n;i>1;i--){
    for(int j=1;j<i;j++){
        int temp=a[j+1];
        if(temp<a[j]){
            a[j+1]=a[j];
            a[j]=temp;
        }
        //可以直接用swap
    }
}
//这里是把最大数送到最后面

快速排序

我想快速排序应该是最难理解的排序算法了

  • 之所以不稳定是因为枢轴的位置可以随意变化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int partition(int a[], int l, int r)
{
    // 选取最左端元素作为“枢轴”（pivot）
    // 枢轴的作用：最终它左边的数都 <= pivot，右边的数都 >= pivot
    int pivot = a[l];

    // i、j 分别作为左右指针
    // i 从左向右移动，j 从右向左移动
    int i = l, j = r;

    // 当左右指针未相遇时循环
    while (i < j)
    {
        /*
         * 第一步：从右向左找
         * 找到第一个 < pivot 的元素
         * 这样这个元素应该放到 pivot 左边
         */
        while (i < j && a[j] >= pivot)
            j--;

        // 将右侧找到的小元素放到左边空出来的位置
        // 此时 a[i] 原来的值（pivot）已经被“腾空”
        a[i] = a[j];

        /*
         * 第二步：从左向右找
         * 找到第一个 > pivot 的元素
         * 这样这个元素应该放到 pivot 右边
         */
        while (i < j && a[i] <= pivot)
            i++;

        // 将左侧找到的大元素放到右边空出来的位置
        a[j] = a[i];
    }
    //不断挖坑直到i==j
    /*
     * 当 i == j 时，左右指针相遇
     * 这个位置就是 pivot 的最终正确位置
     */
    a[i] = pivot;

    // 返回 pivot 的最终下标
    return i;
}
//注意到这样仅仅是做到左边的数都比pivot小,右边的数都比pivot大,没有做到内部有序,故仍然需要经过递归处理子区间来保证最终有序
void quickSort(int a[], int l, int r)
{
    if (l >= r) return;
    int mid = partition(a, l, r);
    quickSort(a, l, mid - 1);
    quickSort(a, mid + 1, r);
}
int main(){
    quickSort(a,1,n);
}

选择排序

简单选择排序

每一轮选择当前最小数放到最前面,左边界每次加一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 简单选择排序
void selectionSort(int a[], int n) {
    for (int i = 1; i <= n; i++) {
        int minIndex = i;
        for (int j = i + 1; j <= n; j++) {
            if (a[j] < a[minIndex])
                minIndex = j;
        }
        if (minIndex != i) {
            int temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
}

堆排序

先建立好最大堆,再将堆顶与堆尾不断交换,输出堆尾并调整堆
之所以不用小根堆,是因为小根堆只能保证子女大于父亲,故仍然需要进行交换处理,这样交换之后反而为降序,与一般排序顺序不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 堆排序（大根堆）

void heapify(int a[], int n, int i) {
    int largest = i;
    int l = 2 * i;
    int r = 2 * i + 1;

    if (l <= n && a[l] > a[largest]) largest = l;
    if (r <= n && a[r] > a[largest]) largest = r;

    if (largest != i) {
        int temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;
        heapify(a, n, largest);
    }
}

void heapSort(int a[], int n) {
    // 建堆
    for (int i = n / 2; i >= 1; i--)
        heapify(a, n, i);

    // 排序
    for (int i = n; i > 1; i--) {
        int temp = a[1];
        a[1] = a[i];
        a[i] = temp;
        heapify(a, i - 1, 1);
    }
}

归并排序

基本方法就是移动三个指针,n路归并就移动(n+1)个指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 将两个有序区间 [l, mid] 和 [mid+1, r] 合并为一个有序区间
void merge(int a[], int l, int mid, int r, int temp[]) {
    int i = l;        // 左子区间起始指针
    int j = mid + 1;  // 右子区间起始指针
    int k = l;        // 临时数组指针

    // 同时遍历左右两个子区间，按大小顺序放入 temp
    while (i <= mid && j <= r) {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    // 左子区间还有剩余元素，直接复制
    while (i <= mid)
        temp[k++] = a[i++];

    // 右子区间还有剩余元素，直接复制
    while (j <= r)
        temp[k++] = a[j++];

    // 将合并后的有序结果拷贝回原数组
    for (int p = l; p <= r; p++)
        a[p] = temp[p];
}

// 归并排序主函数：递归拆分区间
void mergeSort(int a[], int l, int r, int temp[]) {
    // 递归结束条件：区间长度为 0 或 1
    if (l >= r) return;

    int mid = (l + r) / 2;      // 取中点
    mergeSort(a, l, mid, temp);      // 排序左半部分
    mergeSort(a, mid + 1, r, temp);  // 排序右半部分
    merge(a, l, mid, r, temp);       // 合并两个有序区间
}

基数排序

简单说来就是先把一串数字个位从小到大排,接着排十位,百位,直到遍历完最高位,由于不考算法,就不贴上来了.

以下为参考视频

吐槽一下B站直接在分享点嵌入代码给出的是<iframe src="//player.bilibili.com/player.html?isOutside=true&aid=1205817791&bvid=BV1tf421Q7eh&cid=1596291120&p=1" scrolling="no" border="0" frameborder="no" framespacing="0" allowfullscreen="true"></iframe>
结果只能在很小的一块区域显示,所以我用ai改成了<iframe src="//player.bilibili.com/player.html?isOutside=true&aid=1205817791&bvid=BV1tf421Q7eh&cid=1596291120&p=1" width="100%" height="500" frameborder="0" allowfullscreen></iframe>