开始之前

进阶排序是对一些特殊情况下排序的处理方式，也是非常重要的一些排序方法

表排序

  • 当数据不再是简单的数字或者字符，而是一些比较大的元素，例如文件等，那么这时在之前介绍的排序中所采取方式就会产生很大的时间复杂度 —— 因为文件的移动是需要时间的，而且需要不短的一段时间，我们普通的排序所采取的不停Swap的操作，就会使时间大大增加

间接排序

  • 那么此时，我们可以采取间接排序的方式，也就是在结构体中添加一个属性，将之进行简单排序，来作为数据的真实顺序
A [0] [1] [2] [3] [4] [5] [6] [7]
key f d c a g b h e
table 0 1 2 3 4 5 6 7
  • 对table根据key值进行排序即可
A [0] [1] [2] [3] [4] [5] [6] [7]
key f d c a g b h e
table 3 5 2 1 7 0 4 6
  • 排序完成后结果如上，这时如果要求按顺序输出元素，就可按照A[table[i]] `i取值为0~n-1

物理排序

  • 如果明确要求需要对数据进行物理排序的话，那么我们就可以在表排序的基础之上对数据进行交换
  • 首先我们将A[0]取出，赋给临时值temp，之后寻找A[table[0]]，将之移动到空位上，依次寻找并移动
  • 因有定理：N个数字的排列由若干个独立的环组成，所以我们将每个环都一次移动一遍就好
  • 那么如何判断一个环已经全部排列整齐呢？我们可以将已排列好的环的table值改为A的下标值，所以if(table[i] == i)为true之时，就说明此环已经被排列整齐

物理排序复杂度分析

  • 最好情况：有序，不用交换
  • 最坏情况：每个环都只有两个元素

桶排序

  • 采用传统交换的排序，其时间下限为\(O(Nlog(N))\) ，就算是最快的排序也总能找到一个特例，使其最坏时间复杂度为\(O(Nlog(N))\)
  • 那么就无法让排序变为线性复杂度吗？

例：有N(N = 50000)个学生，考试成绩为 0 - 100 ，那么此时将学生的考试成绩排序，怎样排序最快呢？

这时我们可以采用桶排序，将时间复杂度提升到线性时间：

  • 因为人数极多，而分数只有101种可能，所以我们可以先建立101个桶（指针数组）
  • 遍历每个学生的成绩，将其放在对应的桶下
  • 依次输出每个桶内的学生，排序完成

实现思路

桶排序的一般实现思路：

  • 在数据种类小而数据规模大时使用
  • 为所有可能出现的数据种类建桶，将数据分别放入对应的桶中
  • 从桶中取出并进行之后的操作

那么，如果数据规模不大，但是种类比较多，又该如何操作呢？

基数排序

假设有10个整数，数字在0到999之间，这时应该怎样使用基数排序呢？

  • 次位优先法进行排序
  • 在一个数中，个位被称为该数的次位，最高位称为主位

实例说明

例：有数字 64， 8， 216， 512， 27， 729 ，0， 1， 343， 125

  • 因为是十进制数字，所以我们建立0-9十个桶
0 1 2 3 4 5 6 7 8 9
0 1 512 343 64 125 216 27 8 729
  • 第一次排列，根据个位（次位）数字，将之放入相应的桶中
0 1 2 3 4 5 6 7 8 9
0 512 125 343 64
1 216 27
8 729
  • 第二次排列，在第一次的基础上按照十位数字将元素放入相应的桶中
0 1 2 3 4 5 6 7 8 9
0 125 216 343 512 729
1
8
27
64
  • 第三次排列，按照百位数字放入相应的桶中，排序完毕
  • 用的时候，直接将元素按次序从桶中依次取出即可

实现思路

  • 显然，我们首先要知道最高位的位数，以便知晓我们应该进行几趟排序
  • 之后就是每一趟将元素依次放入桶中即可

次位优先

  • 实现需要创建桶的结构体
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define MAX_DIGIT 4
#define REDIX 10

/* 桶元素结点 */
typedef struct Node* PtrToNode;
struct Node{
    int key;
    PtrToNode next;
};
/* 桶头结点 */
struct HeadNode{
    PtrToNode head, tail;
};
typedef struct HeadNode Bucket[REDIX];
  • REDIX表示需要排序数字的进制，MAX_DIGIT表示排序数字的最高位数
  • 之后，因为要根据每一位的数字来放置，所以需要一个取固定位 数字的函数
1
2
3
4
5
6
7
8
int GetDit (int x, int d) {
    int tmp, i;
    for (i = 0; i <= d; ++i) {
        tmp = x % REDIX;
        x /= REDIX;
    }
    return tmp;
}
  • 准备工作做完之后，就可以进行排序了
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
void LSDRadixSort (ELEMENT_TYPE a[], int n) {
    int d, di, i;
    Bucket bucket;
    PtrToNode tmp, p, list = NULL;
    for (i = 0; i < REDIX; ++i) // 初始化桶
        bucket[i].head = bucket[i].tail = NULL;
    for (i = 0; i < n; ++i) {   // 将数组逆序存入list链表
        tmp = (PtrToNode)malloc(sizeof(struct Node));
        tmp->key = a[i];
        tmp->next = list;
        list = tmp;
    }
    for (d = 1; d <= MAX_DIGIT; ++d) {	// 排序
        p = list;
        while (p) {	// 将 list 按顺序放入桶中
            di = GetDit(p->key, d);
            tmp = p;
            p = p->next;
            tmp->next = NULL;
            if (bucket[di].head == NULL)
                bucket[di].head = bucket[di].tail = tmp;
            else {
                bucket[di].tail->next = tmp;
                bucket[di].tail = tmp;
            }
        }
        list = NULL;
        for (di = REDIX-1; di >= 0; di--) {	// 将桶中数字按顺序放回 list 中
            if (bucket[di].head) {
                bucket[di].tail->next = list;
                list = bucket[di].head;
                bucket[di].head = bucket[di].tail = NULL;
            }
        }
    }

    for (i = 0; i < n; ++i) {	// 将排序完成的list重新赋值给a数组
        tmp = list;
        list = list->next;
        a[i] = tmp->key;
        free(tmp);
    }
}

主位优先

  • 该算法采用递归的方式实现，初始化部分和之前一致，只是后面有点差异
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
void MSD (ELEMENT_TYPE a[], int l, int r, int d) {
    int di, i, j;
    Bucket bucket;
    PtrToNode tmp, p, list = NULL;
    if (d == 0)
        return;
    for (i = 0; i < REDIX; ++i)
        bucket[i].head = bucket[i].tail = NULL;
    for (i = l; l <= r; ++l) {
        tmp = (PtrToNode)malloc(sizeof(struct Node));
        tmp->key = a[i];
        tmp->next = list;
        list = tmp;
    }
    p = list;
    while (p) {
        di = GetDit(p->key, d);
        tmp = p;
        p = p->next;
        if (bucket[di].head == NULL)
            bucket[di].tail = tmp;
        tmp->next = bucket[di].head;
        bucket[di].head = tmp;
    }
    i = j = l;
    for (di = 0; di < REDIX; ++di) {
        if (bucket[di].head) {
            p = bucket[di].head;
            while (p) {
                tmp = p;
                p = p->next;
                a[j++] = tmp->key;
                free(tmp);
            }
            MSD(a, i, j-1, d-1);
            i = j;
        }
    }
}

void MSDRadixSort (ELEMENT_TYPE a[], int n) {
    MSD(a, 0, n-1, MAX_DIGIT);
}

如上

基数排序的应用

在有多个条件之时，可以先按照一个条件将之进行简单的归类，再逐个类进行排序，最后将其合并

总结

排序算法的探究到这里就告一段落了，我们对所有排序的时间复杂度和空间复杂度，以及其是否稳定进行一次统计总结：

排序方法 平均时间复杂度 最坏时间复杂度 额外空间复杂度 稳定性
简单选择排序 \(O(N^2)\) \(O(N^2)\) \(O(1)\) 不稳定
冒泡排序 $O(N^ 2 ) $ \(O(N^2 )\) \(O(1)\) 稳定
直接插入排序 \(O(N^ 2)\) \(O(N^ 2)\) \(O(1)\) 稳定
希尔排序 \(O(N^ d)\) \(O(N^ 2)\) \(O(1)\) 不稳定
堆排序 \(O(Nlog N)\) \(O(Nlog N)\) \(O(1)\) 不稳定
快速排序 \(O(Nlog N)\) \(O(N^ 2)\) \(O(log N)\) 不稳定
归并排序 \(O(Nlog N)\) \(O(Nlog N)\) \(O( N)\) 稳定
基数排序 \(O(P(N+B))\) \(O(P(N+B))\) \(O(N+B)\) 稳定