跳转至

12. 希尔，堆，归并，快速排序

阅读信息

约 811 个字  5 分钟  本页总访问量：加载中... 次

:banjo:Class Twelve

排序

简单排序：

  1. 选择排序 seection：每次找最大的元素，放在末尾
  2. 交换排序 exchange：从头到尾遍历，看两个相邻元素是否符合，位置不对则交换（冒泡）
  3. 插入排序 insertion：每次之前的元素都排好，插入一个元素使其保持排序的特性。 最坏时间复杂度和平均时间复杂度都是 O(n^2) 但最好时间复杂度不同，选择排序为 O(n^2)，冒泡排序可通过标签优化，插入排序最优为 O(n)。

inversion 逆序对：大的在前小的在后，成为一对逆序对。 如果长度为 n 的序列，最多 n(n-1)/2 个逆序对，平均约 nn/4 个逆序。 相邻两个元素对调，改变一个逆序对。 排序算法突破：跳着比较 希尔排序：分组比较+插入排序

分治法：归并排序 T(n)=2T(n/2)+Cn => T(n)=O(nlogn)

快速排序：选择 pivot，将所有元素分为比它小和比它大。

堆排序：构建树，每次选出最大后。每层只有一个元素可能是第二大。

桶排序：

基数排序：先按个位数放入不同的桶，排成序列。再按十位数放入不同的桶，再按百位数……最后排成从小到大的序列。 循环的次数等于位数。

排序的稳定性：相等的元素排序前后顺序是不是相同。

插入排序对输入顺序敏感.如果输入数据基本排好,则排序时间短.

希尔排序

跨区域比较:分组

将数据间隔分组,每组排序 减少组数,再将每组排序 继续减少分组,直到只分一组,完成排序

若数据基本有序,插入排序时间接近线性. 分组多,单组时间复杂度低;分组少时,数据接近有序,时间线性. 开始时分 k 组,组内有序的时间复杂度为全部有序的 1/k.

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void shellsort(int arr[], int n) {
    for (int step = n / 2; step > 0; step /= 2) {  // step表示步长
        for (int i = step; i < n; i++) {
            int tmp = arr[i];
            int j;
            for (j = i; j >= step; j -= step) {  // 插入排序
                if (tmp < arr[j - step])
                    arr[j] = arr[j - step];
                else
                    break;
            }
            arr[j] = tmp;
        }
    }
}

按step = n / 2; step > 0; step /= 2分组,最坏时间复杂度:\(O(N^2)\) Hibbard's Increment Sequence: 按\(step=2^k-1\)分组

堆排序

方法 1(不好)

C
1
2
3
4
5
6
7
void heapsort(int arr[]) {
    BuildHeap(H);
    for (int i = 0; i < n; i++)
        tmpH[i] = DeleteMin(H);
    for (int i = 0; i < n; i++)
        H[i] = tmpH[i];
}

堆排序:

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void heapSort(int* arr, int n) {
    // 1. 构建大根堆（从最后一个非叶子节点开始）
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 2. 逐个提取元素
    for (int i = n - 1; i > 0; i--) {
        交换arr[0]和arr[i]; // 将当前根（最大值）移动到数组末尾
        heapify(arr, i, 0); // 对缩减后的堆进行调整
    }
}

时间复杂度:\(N\log N-N\log\log N\)

归并排序(分治法)

先分别排序,再 merge. 时间复杂度: 分成两组:\(O(1)\) 递归将两组分别排序:\(2T(N/2)\) merge: \(O(N)\)

quicksort: merge 的步骤减小时间.分组时选择 pivot,将所有元素分成比 pivot 小和比 pivot 大的两组. 这样分组不一定是 n/2 的两组,时间复杂度为\(T(i)+T(N-i)\)

C
 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
58
#include <stdio.h>

// 避免每次调用生成temp临时数组,在外部同一申请temp,作为参数传入
void merge(int a[],
           int left,
           int leftend,
           int right,
           int temp[]) {  // 合并两个有序数组
    int i, j, k;
    i = left;
    j = leftend + 1;
    k = left;

    while (i <= leftend && j <= right) {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
    while (i <= leftend)
        temp[k++] = a[i++];
    while (j <= right)
        temp[k++] = a[j++];
}

// 设计成递归函数,必须将边界作为参数传入
void mergesort(int a[],
               int left,
               int right,
               int temp[]) {  // 排序，用temp临时存储
    if (left >= right)
        return;

    int mid = (left + right) / 2;
    mergesort(a, left, mid, temp);
    mergesort(a, mid + 1, right, temp);
    merge(a, left, mid, right, temp);
    for (int i = left; i <= right; i++) {
        a[i] = temp[i];
    }
}

int main() {
    int a[101], tempa[101];
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    mergesort(a, 0, n - 1, tempa);

    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

时间复杂度比较 和\(T(n)=2T(n/2)+Cn\)比较 \(T(n)=3T(n/2)+Cn\): 更复杂 \(T(n)=2T(n/3)+Cn\): 更简单

临时数组

  1. 外部统一申请,作为参数传入
  2. 每次合并新申请空间
  3. 原地排序,不额外申请空间(复杂)
  4. 两个相同长度的数组,一个排序时占用另一个数组
  5. 三个已排序数组合并,用堆(??)

快速排序

关键:分组时选择 pivot,将所有元素分成比 pivot 小和比 pivot 大的两组.

难点:

  1. 怎么选择 pivot
  2. 原地排序,不额外申请数组

选择 pivot 的方法:

  1. 选第一个(不好)
  2. 随机选择(仍不好)
  3. 头,尾,中间值三个中选中间值
  4. 五等分点选中间值
  5. 随便选一个分组,看两组是否均匀(可 ¼ 为界),若均匀则继续进行,若不均匀则重来(按期望为做两次)

蒙塔卡洛:做特定次数,做完后停止,不管是否符合最佳条件 拉斯维加斯:按特定要求,若一直不符合要求则一直进行

但是,数组小时选 pivot 快排效率低. 在数组规模小于阈值时,直接使用简单排序.

怎么原地分类?

两边扫描

基准元素放在最后 指针 i 放在开头,比 pivot 小时向右走,>=时停下 指针 j 放在结尾,比 pivot 大时向左走,<=时停下 都停下时交换 i 和 j 的值 直到 i==j 或 i>j,将 pivot 放在最终位置

一边扫描

一个指针向右走,左边是小的一堆和大的一堆 如果指针处大,继续向右走 如果指针处小,和大的那堆的第一个元素交换(需要标记大的那堆的第一个元素位置)

荷兰旗问题 三种数据排序

一个指针向右走,左边是 R 的一堆,G 的一堆,B 的一堆 如果指针处是 B,继续向右走 如果指针处是 G,和 B 堆的第一个交换 如果指针处是 R,指针处元素放在 G 堆第一个位置,G 堆第一个放在 B 堆第一个位置,B 堆第一个放在指针位置

指针移动要求:维护扫过的区域符合要求. 双边扫描:左指针左侧都小,右指针右侧都大 一边扫描:指针左侧是分好的堆