数据结构和算法——用C语言实现所有排序算法

排序算法的基本概念

排序算法就是将结构中所有数据按照关键字有序的过程。排序的分类如下：

评价一个排序算法的指标通常有以下三种：

• 时间复杂度
• 空间复杂度
• 稳定性

其中稳定性是指关键字相同的元素在排序前后相对位置是否改变，如果不变则称该排序算法是稳定的，否则就是不稳定的。

内部排序

插入排序

算法思想：每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。

直接插入排序

• 算法思想：每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。
• 时间复杂度：$O(n)\sim O(n^2)$
• 空间复杂度：$O(1)$
• 稳定性：稳定

/**
 * 直接插入排序
 * @param dataList
 * @param length
 */
void directInsert(void *dataList[], int length, int (*compare)(void *, void *)) {
    for (int unOrderListIterator = 2; unOrderListIterator <= length; ++unOrderListIterator) {
        void *sortedData = dataList[unOrderListIterator - 1];
        int orderListIterator;
        for (orderListIterator = unOrderListIterator - 1; orderListIterator >= 1 && compare(sortedData, dataList[orderListIterator - 1]) < 0; --orderListIterator) {
            dataList[orderListIterator + 1 - 1] = dataList[orderListIterator - 1];
        }
        dataList[orderListIterator + 1 - 1] = sortedData;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

折半插入排序

• 算法思想：在直接插入排序的基础上，用二分查找待排元素的位置。
• 时间复杂度：$O(nlo{g}_{2}n)\sim O(n^2)$
• 空间复杂度：$O(1)$
• 稳定性：稳定

/**
 * 折半插入排序
 * @param dataList
 * @param length
 */
void binaryInsertSort(void *dataList[], int length, int (*compare)(void *, void *)) {
    for (int unOrderListIterator = 2; unOrderListIterator <= length; ++unOrderListIterator) {
        void *sortedData = dataList[unOrderListIterator - 1];
        int mid, high = unOrderListIterator - 1, low = 1;
        while (low <= high) {
            mid = (high + low) / 2;
            if (compare(dataList[mid - 1], sortedData) > 0) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        for (int orderListIterator = unOrderListIterator; orderListIterator > low; orderListIterator--) {
            dataList[orderListIterator - 1] = dataList[orderListIterator - 1 - 1];
        }
        dataList[low - 1] = sortedData;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

希尔排序

• 算法思想：先将待排序列表分割成若干形如$L[i,i+d,i+2d,\dots ,i+kd]$的子表，然后对各个子表分别进行直接插入排序，之后缩小增量$d$，重复上述过程，直到$d=1$。
• 时间复杂度：无法用数学方法准确表示，当$n$在某一范围内时间复杂度为$O(n^{1.3})$，最坏的时间复杂度为$O(n^2)$
• 空间复杂度：$O(1)$
• 稳定性：不稳定

/**
 * 希尔排序
 * @param dataList
 * @param length
 * @param compare
 */
void shellSort(void *dataList[], int length, int (*compare)(void *, void *)) {
    for (int p = length / 2; p >= 1; p /= 2) {
        for (int unOrderListIterator = p + 1; unOrderListIterator <= length; ++unOrderListIterator) {
            void *sortedData = dataList[unOrderListIterator - 1];
            int orderListIterator;
            for (orderListIterator = unOrderListIterator - p; orderListIterator >= 1 && compare(sortedData, dataList[orderListIterator - 1]) < 0; orderListIterator -= p) {
                dataList[orderListIterator + p - 1] = dataList[orderListIterator - 1];
            }
            dataList[orderListIterator + p - 1] = sortedData;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

交换排序

算法思想：根据序列中两个元素关键字的比较结果来对换这两个元素在序列中的位置。

冒泡排序

• 算法思想：从前往后两两比较相邻两元素的关键字，若为逆序则交换它们，直到序列比较完成，此时最小的元素将被交换到第一个位置，这就是一趟冒泡。只要经过$n-1$趟冒泡，待排序列就有序了。
• 时间复杂度：$O(n)\sim O(n^2)$
• 空间复杂度：$O(1)$
• 稳定性：稳定

/**
 * 冒泡排序
 * @param dataList
 * @param length
 * @param compare
 */
void bubbleSort(void *dataList[], int length, int (*compare)(void *, void *)) {
    for (int trip = 1; trip <= length - 1; trip++) {
        bool isSwap = false;
        for (int j = length; j > trip; j--) {
            if (compare(dataList[j - 1], dataList[j - 1 - 1]) < 0) {
                swap(dataList + j - 1, dataList + j - 1 - 1);
                isSwap = true;
            }
        }
        //如果没有交换则序列已有序
        if (!isSwap) {
            break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

快速排序

快速排序算法的平均时间复杂度接近最好时间复杂度的排序算法，是最好的内部排序。

• 算法思想：在待排序列中选择一个元素$pivot$作为基准，通过一趟排序将序列划分为两部分$L[1,\dots ,k-1]$和$L[k+1,\dots ,n]$，使得$L[1,\dots ,k-1]$中所有元素小于$pivot$，$L[k+1,\dots ,n]$中所有元素大于等于$pivot$。$piovt$则放在了其最终的位置$L[k]$上，这个过程为一趟快速排序。然后分别递归的对两个部分重复上述过程，直到每部分只有一个元素或空为止。
• 时间复杂度：$O(nlo{g}_{2}n)\sim O(n^2)$，具体为$O(n\times 递归层数)$
• 空间复杂度：$O(lo{g}_{2}n)\sim O(n)$，具体为$O(递归层数)$
• 稳定性：不稳定

static int partition(void *dataList[], int low, int high, int (*compare)(void *, void *)) {
    void *pivot = dataList[low - 1];
    while (low < high) {
        while (low < high && compare(dataList[high - 1], pivot) > 0) {
            high--;
        }
        dataList[low - 1] = dataList[high - 1];
        while (low < high && compare(dataList[low - 1], pivot) <= 0) {
            low++;
        }
        dataList[high - 1] = dataList[low - 1];
    }
    dataList[low - 1] = pivot;
    return low;
}

/**
 * 快速排序
 * @param dataList 
 * @param low 
 * @param high 
 * @param compare 
 */
void quickSort(void *dataList[], int low, int high, int (*compare)(void *, void *)) {
    if (low < high) {
        int pivotPos = partition(dataList, low, high, compare);
        quickSort(dataList, low, pivotPos - 1, compare);
        quickSort(dataList, pivotPos + 1, high, compare);
    }
}
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

选择排序

算法思想：每一趟在待排序序列中选择关键字最小或最大的元素加入有序子序列。

简单选择排序

• 算法思想：第$i$趟从$L(i...n)$中选择关键字最小的元素与$L(i)$交换，每一趟排序都可以确定一个元素的最终位置。
• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$
• 稳定性：不稳定

/**
 * 简单选择排序
 * @param dataList 
 * @param length 
 * @param compare 
 */
void simpleSelectSort(void *dataList[], int length, int (*compare)(void *, void *)) {
    for (int orderListIterator = 1; orderListIterator < length; ++orderListIterator) {
        int minIndex = orderListIterator;
        for (int unOrderListIterator = orderListIterator + 1; unOrderListIterator <= length; ++unOrderListIterator) {
            if (compare(dataList[unOrderListIterator - 1], dataList[minIndex - 1]) < 0) {
                minIndex = unOrderListIterator;
            }
        }
        if (minIndex != orderListIterator) {
            swap(dataList + orderListIterator - 1, dataList + minIndex - 1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

堆排序

当一个序列$L[1,\dots ,n]$满足：

• $L(i)>=L(2i)$且$L(i)>=L(2i+1)$时，称该序列为大顶堆
• $L(i)<=L(2i)$且$L(i)<=L(2i+1)$时，称该序列为小顶堆

可以将堆看成一棵线性存储的完全二叉树：

• 大顶堆的最大元素存放在根结点，且其任一非根结点的值小于等于其双亲结点的值。
• 小顶堆的最小元素存放在根结点，且其任一非根结点的值大于等于其双亲结点的值。
• 在完全二叉树中：
  • 若$i<=\lfloor n/2\rfloor$，那么结点$i$为分支结点，否则为叶子结点。
  • $i$的左孩子$2i$
  • $i$的右孩子$2i+1$
  • $i$的父结点$\lfloor i/2\rfloor$

堆排序首要任务就是先构建一个堆（以大顶堆为例）：

• 检查所有分支结点的关键字是否满足大顶堆的性质，如果不满足，则用最大孩子的关键字和分支结点的关键字交换，使该分支子树成为大顶堆。之后依次对$\lfloor n/2\rfloor -1\sim 1$位置的分支结点重复以上检查。
• 若关键字交换破坏了下一级的堆，则采用相同的方式继续往下调整。

堆构建完后就可以进行堆排序了，堆排序的算法思想如下：

• 每一趟将堆顶元素加入有序子序列（与待排序列中的最后一个元素交换），并将待排元素序列再次调整为大顶堆。
• 时间复杂度：
  • 建立堆时：$O(n)$
  • 排序时：$O(nlo{g}_{2}n)$
  • 整体：$O(nlo{g}_{2}n)$
• 空间复杂度：$O(1)$
• 稳定性：不稳定

如果要在堆中插入或删除元素（以小顶堆为例），那么思想为：

• 插入元素时，首先将新元素放到堆尾，然后与父结点对比，若新元素比父结点更小，则将两者互换，一直重复此步骤直至新元素无法上升。
• 删除元素时，首先用堆底元素代替被删除的元素，然后让该元素不断的下坠，直到无法下坠为止。

static void heapAdjust(void **dataList, int rootIndex, int length, int (*compare)(void *, void *)) {
    void *root = dataList[rootIndex - 1];
    //i指向左孩子
    for (int i = 2 * rootIndex; i <= length; i *= 2) {
        //如果右孩子>左孩子，则让i指向右孩子
        if (i < length && compare(dataList[i + 1 - 1], dataList[i - 1]) > 0) {
            i++;
        }
        if (compare(root, dataList[i - 1]) > 0) {
            break;
        } else {
            dataList[rootIndex - 1] = dataList[i - 1];
            //调整完当前子树后接着向下调整，以免上一次的交换破坏了下一级的堆
            rootIndex = i;
        }
    }
    dataList[rootIndex - 1] = root;
}

static void maxHeapBuild(void **dataList, int length, int (*compare)(void *, void *)) {
    for (int i = length / 2; i >= 1; i--) {
        int a = *((int *) dataList[i - 1]);
        heapAdjust(dataList, i, length, compare);
    }
}

/**
 * 堆排序
 * @param dataList
 * @param length
 * @param compare
 */
void heapSort(void **dataList, int length, int (*compare)(void *, void *)) {
    maxHeapBuild(dataList, length, compare);
    for (int i = length; i > 1; i--) {
        swap(dataList + i - 1, dataList + 1 - 1);
        heapAdjust(dataList, 1, i - 1, compare);
    }
}
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

归并排序

• 算法思想：将待排序列视为$n$个有序的子序列，然后两两（或两个以上）归并，得到$\lceil n/2\rceil$个长度为$2$或为$1$的有序序列，然后继续归并，直到合成一个长度为$n$的有序序列为止。
• 时间复杂度：$O(nlo{g}_{2}n)$
• 空间复杂度：$O(n)$
• 稳定性：稳定

static void merge(void *dataList[], int length, int low, int mid, int high, int (*compare)(void *, void *)) {
    void *temp[length];
    int i, j, k;
    for (k = low; k <= high; ++k) {
        temp[k-1] = dataList[k-1];
    }
    for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {
        if (compare(temp[i - 1], temp[j - 1]) < 0) {
            dataList[k - 1] = temp[i - 1];
            i++;
        } else {
            dataList[k - 1] = temp[j - 1];
            j++;
        }
    }
    while (i <= mid) {
        dataList[k - 1] = temp[i - 1];
        k++;
        i++;
    }
    for (; j <= high;) {
        dataList[k - 1] = temp[j - 1];
        k++;
        j++;
    }
}

/**
 * 归并排序
 * @param dataList
 * @param length
 * @param low
 * @param high
 * @param compare
 */
void mergeSort(void *dataList[], int length, int low, int high, int (*compare)(void *, void *)) {
    if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(dataList, length, low, mid, compare);
        mergeSort(dataList, length, mid + 1, high, compare);
        merge(dataList, length, low, mid, high, compare);
    }
}
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

基数排序

假设长度为$n$的排序列表中每个结点$a_j$的关键字由$d$元组$(k_j^{d-1},k_j^{d-2},\dots ,k_j^1,k_j^0)$组成，其中$0\le k_j^i\le r-1,(0\le j<n,0\le i\le d-1)$，$r$称为基数。那么基数排序的算法思想为：

• 初始化：设置$r$个空队列，$Q_0,Q_1,\dots ,Q_{r-1}$
• 按照各个关键字位权重递增的次数对$d$个关键字位分别进行分配和收集
  • 分配：顺序扫描各个元素，若当前处理的关键字位$=x$，则将元素插入$Q_x$队尾
  • 收集：把 $Q_0,Q_1,\dots ,Q_{r-1}$各个队列中的结点依次出队链接
• 时间复杂度：$O(d(n+r))$
• 空间复杂度：$O(r)$
• 稳定性：稳定

以int dataList[] = {278, 109, 63, 930, 589, 184, 505, 269, 8, 83}为例：

/**
 * 基数排序
 * @param dataList
 * @param length
 * @param maxLength
 */
void radixSort(int dataList[], int length, int maxLength) {
    LinkedQueue queue = linkedQueueConstructor();
    for (int i = 0; i < length; ++i) {
        linkedQueueEnQueue(queue, dataList + i);
    }
    LinkedQueue queue0 = linkedQueueConstructor();
    LinkedQueue queue1 = linkedQueueConstructor();
    LinkedQueue queue2 = linkedQueueConstructor();
    LinkedQueue queue3 = linkedQueueConstructor();
    LinkedQueue queue4 = linkedQueueConstructor();
    LinkedQueue queue5 = linkedQueueConstructor();
    LinkedQueue queue6 = linkedQueueConstructor();
    LinkedQueue queue7 = linkedQueueConstructor();
    LinkedQueue queue8 = linkedQueueConstructor();
    LinkedQueue queue9 = linkedQueueConstructor();
    LinkedQueue queueList[] = {queue0, queue1, queue2, queue3, queue4, queue5, queue6, queue7, queue8, queue9};
    for (int i = 1; i <= maxLength; ++i) {
        while (!linkedQueueIsEmpty(queue)) {
            void *data = linkedQueueDeQueue(queue);
            int key = *(int *) data / (int) pow(10, i - 1) % 10;
            linkedQueueEnQueue(queueList[key], data);
        }
        for (int j = 0; j < 10; ++j) {
            LinkedQueue keyQueue = queueList[j];
            while (!linkedQueueIsEmpty(keyQueue)) {
                linkedQueueEnQueue(queue, linkedQueueDeQueue(keyQueue));
            }
        }
    }
    while (!linkedQueueIsEmpty(queue)) {
        void *data = linkedQueueDeQueue(queue);
        printf("%d,", *(int *) data);
    }
}
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

外部排序

多路归并

操作系统以块为单位对磁盘存储空间进行管理，如果要修改磁盘块中的数据，就需要把对应磁盘块的内容读到内存中，在内存中修改后再写回磁盘。在对磁盘数据进行排序时，如果磁盘中的数据过多，那么无法一次将数据全部读到内存中，此时就应该使用外部排序。实现外部排序的思想是使用归并排序的的方法，最少只需要在内存中分配三块大小的缓冲区即可对任意一个大文件进行排序。

外部排序的步骤如下：

• 构造归并段：每次将磁盘中两个块的内容读入输入缓冲区中，进行内部排序写到输出缓冲区，当某个输入缓冲区为空时就立即读入磁盘中的下一个段，当输出缓冲区已满时就写入到磁盘中。16个块都排序完后就构造了8个两块长度的初始归并段。
• 接着继续构造4个4块长度的归并段。
• 以此类推当只有一个归并段时整个磁盘就变得有序了。

在每次构造归并段时都需要把所有的磁盘块读写一遍，并且还要进行内部排序，因此外部排序的时间开销由以下几部分构成：
$$外部排序的时间开销=读写外存的时间+内部排序所需时间+内部归并所需的时间$$
其中读写外存的时间是外部排序的主要开销，因此可以使用多路归并的方式来减少归并的趟数从而减少读写外存的次数。若对$r$个初始归并段做$k$路归并，则归并树可用$k$叉树表示，若树高为$h$，则归并趟数$n$为：
$$n=h-1=\lceil lo{g}_{k}r\rceil$$
因此归并路数（增加缓冲区的个数）越多，初始归并段（增加缓冲区的长度）越少，读写磁盘的次数就越少。但多路归并同样存在着问题：

• 问题一：$k$路归并时，需要开辟$k$个输入缓冲区，内存开销增大。
• 问题二：每挑选一个关键字需要对比关键字$k-1$次，内部归并所需要的时间增加。

败者树

败者树可视为多一个根结点的完全二叉树，$k$个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的失败者，而让胜者往上继续进行比较，一直到根结点。

可以将败者树用于多路归并从而减少关键字的对比，从而解决问题二。对于$k$路归并，第一次构造败者树需要对比关键字$k-1$次，有了败者树，选出最小元素，只需要对比关键字$\lceil lo{g}_{2}k\rceil$次。

置换——选择排序

对于传统归并段构造的方法，如果用于内部排序的输入缓冲区可容纳$l$个记录，则每个初始归并段也只能包含$l$个记录，若文件共有$n$个记录，则初始归并段的数量为$r=\frac{n}{l}$。而置换——选择排序可以构造比内存缓冲区长度长的归并段。置换——选择排序的思想为：

• 假设输入缓冲区的大小为三，读入代排文件中的三个记录。
• 每次将缓冲区的最小记录放到归并段一的末尾（并在内存中记录这个最小记录miniMax），接着读入待排文件的下一记录填充输入缓冲区。
• 若当前缓冲区的最小记录小于miniMax，那么就不可能将其放到归并段一的末尾，此时找到第二小且大于miniMax的记录放到归并段。
• 当某一时刻输入缓冲区的所有记录都小于miniMax时，第一个初始归并段就构造结束。
• 接着以同样的方式构造初始归并段二，依次类推直到待排文件为空。

最佳归并树

如果采用置换——选择排序构造初始归并段，并将每一个初始归并段看作一个叶子结点，归并段的长度作为结点的权值，则归并树的带权路径长度$WSL$有以下公式成立：
$$WSL=读磁盘的次数=写磁盘的次数$$

那么$WSL$最小的树就是一棵哈夫曼树，从而可以通过构造一棵哈夫曼树以使存盘存取次数最小。在构造哈夫曼树树的过程中，如果初始归并段的数量无法构成严格的$k$叉哈夫曼树，那么就需要补充长度为0的虚段，再进行构造。对于一棵$k$叉归并树：

• 如果$(初始归并段的数量-1)\%(k-1)=0$，则说明刚好可以构成严格$k$叉哈夫曼树，此时不需要添加虚段。
• 如果$(初始归并段的数量-1)\%(k-1)=u\ne 0$，则需要补充$(k-1)-u$个虚段。