排序的相关概念
排序的分类
- 根据在排序过程中带排序的记录是否全部被放置在内存中，排序分为：
- 内排序
- 外排序
1.内排序
内排序是在排序整个过程中，带排序的所有记录全部放置在内存中。
影响内排序的主要因素
- 时间性能。（主要受比较和移动两种操作的影响）
- 辅助空间。
- 算法的复杂性。
内排序的分类
根据排序过程中借助的主要操作，内排序分为：
- 插入排序
- 交换排序
- 选择排序
- 归并排序
2.外排序
外排序是由于排序的记录个数太多，不能同时放置在内存中，整个排序过程需要在内外存之间多次交换数据才能进行。
按照算法的复杂度分类
- 简单算法：冒泡排序、简单选择排序、直接插入排序。
- 复杂排序：希尔排序、堆排序、归并排序、快速排序。
一、冒泡排序算法
因为在冒泡排序中要用到顺序表结构和数组两元素的交换，先把这些写成函数
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0
typedef struct {
int r[MAXSIZE + 1]; // 用于存储要排序的数组， r[0]用作哨兵或者临时变量
int length; // 用于记录顺序表的长度
}SqList;
/**
* 交换数组r中下标i和j的值
*/
void swap(SqList *L, int i, int j){
int temp = L->r[i];
L->r[i] = L->r[j];
L->r[j] = temp;
}
1.1 冒泡排序的初级版实现
冒泡排序（Bubble Sort）是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
/**
* 1.1 对顺序表L作交换排序 (冒泡排序初级版)
*/
void BubblSort0(SqList *L){
int i,j;
for (i = 1; i < L->length; i++)
for (j = i+1; j <= L->length; j++)
if (L->r[i] > L->r[j])
swap(L, i, j);
}
对于这段代码，是最简单的冒泡，其实就是最简单的交换排序而已。它的思路就是让每一个关键字，都和它后面的每一个关键字比较，如果大则交换，这样第一位置的关键字在第一次循环后一定变成最小值。
假设我们待排序的关键字序列是{9，1，5，8，3，7，4，6，2}
- 当
i = 1时，9与1交换后，在第一位置的1与后面的关键字比较都小，因此它就只最小值。 - 当
i = 2时，第二位置先后由9换成5，换成3，换成2，完成了第二小的数字交换。 -
后面数字依次比较和交换，得到最终结果。
1.2 冒泡排序的实现
对于上面的算法，代码虽然简单易懂，但是效率非常低。可以改进成接下来的代码
/**
* 1.2 对顺序表作L冒泡排序
*/
void BubbleSort(SqList *L){
int i,j;
for (i = 1; i < L->length; i++)
for (j = L->length - 1; j >= i; j--)
if (L->r[j] > L->r[j+1])
swap(L, j, j+1);
}
代码解释
假设我们待排序的关键字序列是{9，1，5，8，3，7，4，6，2}
- 当
i = 1时，变量j由8反向循环到1，逐个比较，将较小值交换到前面，直到最后找到最小值放置在了第1的位置。 - 当
i = 1、j = 8时，6 > 2 ，因此交换了它们的位置，j = 7时，4 > 2， 所以交换......直到j = 2时，因为 1 < 2， 所以不交换。j = 1 时，9 > 1，交换，最终得到最小值1放置第一的位置。 - 在不断循环的过程中，除了将关键字1放到第一的位置，还将关键字2从第九位置提到了第三的位置，显然比前面的算法有进步。
- 当
i = 2时，变量j由8反向循环到2，逐个比较，在将关键字2交换到第二位置的同时，也将关键字4和3有所提升。
1.3 冒泡排序的优化
- 在排序的过程中，增加一个标记变量flag来记录位置是否发生了变化
- 如果没有发生交换，说明数组已经有序了。
/**
* 1.3 对冒泡排序的优化
* 设置一个标记来标志一趟比较是否发生交换
* 如果没有发生交换，则数组已经有序
*/
void BubbleSort1(SqList *L){
int i,j;
int flag = TRUE; // flag 用来作为标记
for (i = 1; i < L->length && flag; i++) { // 若flag为true 则说明数据交换过，否则说明没交换过(数组已经有序) 则停止循环
flag = FALSE;
for (j = L->length - 1; j >= i; j--) {
if (L->r[j] > L->r[j+1]) {
swap(L, j, j+1);
flag = TRUE; // 如果有数据交换 flag为true
}
}
}
}
测试
#define N 9
int main(int argc, const char * argv[]) {
int i;
int d[N] = {9,1,5,8,3,7,4,6,2};
SqList l0;
for (i = 0; i < N; i++)
l0.r[i+1] = d[i];
l0.length = N;
printf("排序前：\n");
for (i = 0; i < l0.length; i++) {
printf("%d ", l0.r[i+1]);
}
printf("\n");
printf("1.0 初级冒泡排序结果:\n");
BubblSort0(&l0);
for (i = 0; i < l0.length; i++) {
printf("%d ", l0.r[i+1]);
}
printf("\n");
printf("1.1 冒泡排序结果:\n");
BubbleSort(&l0);
for (i = 0; i < l0.length; i++) {
printf("%d ", l0.r[i+1]);
}
printf("\n");
printf("1.2 优化后冒泡排序结果:\n");
BubbleSort1(&l0);
for (i = 0; i < l0.length; i++) {
printf("%d ", l0.r[i+1]);
}
printf("\n");
return 0;
}
测试结果
二、简单选择排序
简单选择排序法(Simple Selection Sort)是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1<=i<=n)个记录交换。
简单选择排序法的工作原理是：每一次从无序组的数据元素中选出最小（或最大）的一个元素，存放在无序组的起始位置，无序组元素减少，有序组元素增加，直到全部待排序的数据元素排完。
/**
* 2.对顺序表L作简单选择排序
*/
void SelectSort(SqList *L){
int i, j, min;
for (i = 1; i < L->length; i++) {
min = i; // 将当前下标定义为最小值下标
for (j = i + 1; j <= L->length; j++) {
if (L->r[min] > L->r[j])
min = j;
}
if (i != min) // 若min不等于 i 说明找到最小值， 交换
swap(L, i, min);
}
}
代码说明
- 简单选择排序相对简单，交换移动数据的次数相当少，节约时间。
- 简单选择排序的时间复杂度为
O(n^2)。
三、直接插入排序
直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录增1的有序表。
直接插入排序的核心思想：将一个记录插入到一个已经排序好的表中，以得到一个记录增加1的有序表。并且它把当前元素大的记录都往后移动，用以腾出“自己”该插入的位置。当n-1趟插入完成后该记录就是有序序列。
/**
* 3. 对顺序表作直接插入排序
*/
void InsertSort(SqList *L){
int i, j;
for (i = 2; i < L->length; i++) {
if (L->r[i] < L->r[i-1]) { // 需要将 L->r[i] 插入有序子表
L->r[0] = L->r[i]; // 设置哨兵
for (j = i-1; L->r[j] > L->r[0]; j++)
L->r[j+1] = L->r[i]; // 记录后移
L->r[j+1] = L->r[0]; // 插入到正确位置
}
}
}
代码说明
- 直接插入排序的时间复杂度为
O(n^2)。 - 直接插入排序比冒泡和简单选择排序的性能要好一些。
四、希尔排序
希尔排序是对直接插入排序的改进：
- 将原本有大量记录数的记录进行分组。分割成若干个子序列；
- 对子序列分别进行直接插入排序；
- 当整个序列都基本有序时（注意是基本有序），再对全体记录进行一次直接插入排序。
- 所谓的基本有序，就是小的关键字基本在前，大的基本在后面，不大不小的基本在中间，如{9,1,5,8,3,7,5,6,2}，变成{2,1,3,6,4,7,8,9}这样就是基本有序，但是像{1,5,9,7,8,2,4,6}这样9在第三位，2在倒数第三位就不是基本有序。
- 对于分割子序列，采取跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。
- 增量的选取非常关键，但是现在还是一个数学难题(迄今没有找到一种最好的增量序列),大量研究表明，增量序列为
dlta[k] = 2^(t-k+1) - 1时，可以获得不错的效果。
希尔排序的核心思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
/**
* 4. 对顺序表作L希尔排序
*/
void ShellSort(SqList *L){
int i,j;
int increment = L->length; // 增量初始值等于排序记录
do {
increment = increment /3 +1; // 增量序列
for (i = increment + 1; i < L->length; i++) {
if (L->r[i] < L->r[i-increment]) { // 需要将 L->r[i] 插入有序增量子表
L->r[0] = L->r[i]; // 用哨兵暂时存放 L->r[i]
for (j = i - increment; i >0 && L->r[0] < L->r[j]; j -= increment)
L->r[j+increment] = L->r[j]; // 记录后移， 查找插入位置
L->r[j+increment] = L->r[0]; // 插入
}
}
} while (increment > 1); // 增量不大于 1 时停止循环
}
代码说明
- 希尔排序的时间复杂度为
O(n^(3/2))，要好于直接插入排序的O(n^2); - 增量的最后一个增量之必须等于1才行。
- 由于记录是跳跃式的移动，所以希尔排序不是一种稳定的排序算法。
五、堆排序
堆的概念
堆是具有如下性质的完全二叉树：
- 每个结点的值都大于或等于其其左右孩子结点的值，为大顶堆。
- 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
- 因此根节点一定是堆中所有结点最大（小）者。
-
如图左边为大顶堆，右边为小顶堆：
左边为大顶堆，右边为小顶堆
堆排序算法
堆排序（Heap Sort）是利用堆（假设是大顶堆）进行排序。
堆排序的核心思想：
- 将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。
- 将根节点移走(其实就是将它与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的
n-1个序列重新构造成一个堆，这样就会得到n个元素的次小值。 -
重复上诉操作，便能得到一个有序序列。
堆排序算法核心
- 如何由一个无序序列构建成一个堆
- 如何在输出堆顶元素后，调整剩余元素成一个新的堆
堆排序算法代码实现
/**
* 已知 L->r[s..m] 中记录的关键字除L->r[s]之外均满足堆的定义
* 该函数调整L->r[s] 的关键字，使L->r[s..m]成为一个大顶堆
*/
void HeadAdjust(SqList *L, int s, int m){
int temp, j;
temp = L->r[s];
for (j = 2 *s; j <= m; j *= 2) { // 沿关键字较大的孩子结点向下筛选 这里循环的条件j从 2*s 开始是因为利用了二叉树的性质5：由于这颗是完全二叉树，当前节点序号是 s ，其左孩子的序号一定是 2s， 右孩子的序号一定是 2s+1，它们的孩子当然也是以 2 的位数序号增加，因此 j 变量才这样循环。
if (j < m && L->r[j] < L->r[j+1]) // 1. j < m 说明它不是最后一个节点 2. L->r[j] < L->r[j+1]) 说明左孩子小于右孩子
j++; // j 为关键字中较大的记录的下标
if (temp >= L->r[j])
break; // rc应插入在位置s上
L->r[s] = L->r[j];
s = j;
}
L->r[s] = temp; // 插入
}
/**
* 对顺序表L进行堆排序
*/
void HeapSort(SqList *L){
int i;
for (i = L->length / 2; i>0; i--) // 把L中的r构建成一个大顶堆
HeadAdjust(L, i, L->length);
for (i = L->length; i > 1; i--) {
swap(L, 1, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
HeadAdjust(L, 1, i-1); // 将L->r[1..i-1]重新调整为大顶堆
}
}
堆排序算法代码说明
- 堆排序方法
HeapSort中有两个for循环：第一个for循环完成将现在的待排序序列构建成一个大顶堆；第二个for循环完成逐渐将每个最大值的根节点与末尾元素交换，并且再调整其成为大顶堆。- 第一个for循环中的
i = L->length / 2,i从[9/2]=4开始，4->3->2->1的变化量。（这里赋值的原因是这些都是有孩子的结点） - 构建好有孩子的结点之后，就可以从上到下、从左到右，将每个将每个非终端结点（非叶子结点）当做根节点,将其和子树调整成大顶堆。
- 第一个for循环中的
- 函数
HeadAdjust的作用是将数组构建成一个大顶堆，在构建的时候利用了二叉树的性质。 - 构建堆的时间复杂度为
O(n)，重建堆的时间复杂度为O(nlogn)，所以总体来说堆排序的时间复杂度为O(nlogn)，性能上远好于冒泡、简单选择、直接插入的时间复杂度。 - 在空间复杂度上，由于记录的交换和比较是跳跃式进行的，所以堆排序是一种不稳定的排序方法。
六、归并排序
归并排序(Merging Sort)是利用归并的思想实现的。2路归并排序的核心思想如下：
- 假设初始序列有
n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或者1的有序子序列 - 再两两归并...如此重复，直至得到一个长度为
n的有序序列为止。
6.1归并排序的实现思路（递归实现）
- 将序列平均分成两部分
- 分别对这两部分用递归来归并
- 将这两部分归并到一起
归并排序的代码实现（递归实现）
#pragma - 6.归并排序(递归实现)
/**
* 6.1 将有序的 SR[i..m] 和 SR[m+1..n]归并为有序的 TR[i..n]
*/
void Merge(int SR[], int TR[], int i, int m, int n){
int j, k, l;
for (j = m+1, k = i; i <= m && j <= n; k++) { // 将SR中记录有小到大归并入TR
if (SR[i] < SR[j])
TR[k] = SR[i++];
else
TR[k] = SR[j++];
}
if (i <= m) {
for (l=0; l <= m-i; l++)
TR[k+l] = SR[i+l]; // 将剩余的SR[i..m]复制到TR
}
if (j <= n) {
for (l=0; l <= n-j; l++)
TR[k+l] = SR[j+l]; // 将剩余的SR[j..n]复制到TR
}
}
/**
* 6.2 将SR[s..t]归并排序为TR1[s..t]
*/
void MSort(int SR[], int TR1[], int s, int t){
int m;
int TR2[MAXSIZE+1];
if (s == t) {
TR1[s] = SR[s];
}else{
m = (s+t)/2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
MSort(SR, TR2, s, m); // 递归将SR[s..m]归并为有序的TR2[s..m]
MSort(SR, TR2, m+1, t); // 递归将SR[m+1..t]归并为有序的TR2[m+1..t]
Merge(TR2, TR1, s, m, t); // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
}
}
/**
* 6.3 对顺序表L作归并排序
*/
void MergeSort(SqList *L){
MSort(L->r, L->r, 1, L->length);
}
归并排序的总结（递归实现）
- 归并排序总的时间复杂度为
O(nlogn)，并且这是归并排序算法中最好、最坏、平均的时间性能。 - 归并排序的空间复杂度为
O(n+logn) - 归并排序是一种比较占内存，但是效率高且稳定的算法。
6.2归并排序的实现（迭代非递归实现）
用迭代实现的话，可以从最小的序列开始归并直到完成。
#pragma - 7.归并排序（迭代实现）
/**
* 7.1 将 SR[] 中相邻长度为 s 的子序列来两两归并到 TR[]
*/
void MergePass(int SR[], int TR[], int s, int n){
int i = 1;
int j;
while (i <= n-2*s+1) {
Merge(SR, TR, i, i+s-1, i+2*s-1); // 两两归并
i = i+2*s;
}
if (i < n-s+1) // 归并都最后两个序列
Merge(SR, TR, i, i+s-1, n);
else
for (j = i; j <= n; j++)
TR[j] = SR[j];
}
/**
* 对顺序表 L 作归并非递归排序
*/
void MergeSort2(SqList *L){
int * TR = (int *)malloc(sizeof(L->length*sizeof(int))); // 申请额外空间
int k = 1;
while (k < L->length) {
MergePass(L->r, TR, k, L->length);
k = 2*k; // 子序列长度加倍
MergePass(TR, L->r, k, L->length);
k = 2*k; // 子序列长度加倍
}
}
归并的迭代实现总结
- 非递归的迭代方法，避免了递归时深度为
log2n的栈空间，空间只是用到申请归并临时用的TR数组，因此空间复杂度为O(n). - 并且相对于递归，在时间性能上也有一定的提升，所以使用归并时，尽量使用非递归实现。
七、快速排序
快速排序(Quick Sort)的基本思想是：
- 通过一趟排序将待排序记录分割成独立的两部分
- 其中一部分记录的关键字均比另一部分记录的关键字小；
- 则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
**
快速排序的实现思路
- 选取一个关键字，放到一个位置，使得它的左边的值都比它小，右边的值都比它大，这个关键字叫做枢轴（pivot)
- 然后分别对左边和右边进行排序。
快速排序的代码实现
#pragma - 8.快速排序
/**
* 交换顺序表 L 中子表的记录，使轴记录到位，并返回其所在位置
* 此时在它之前的记录均不大于它，在它之后的记录均不小于它
*/
int Partition(SqList * L, int low, int high){
int pivotkey;
pivotkey = L->r[low]; // 用子表的第一个记录作为枢轴记录
while (low < high) { // 从表的两端交替地向中间扫描
while (low < high && L->r[high] >= pivotkey)
high --;
swap(L, low, high); // 将比枢轴小的记录交换到低端
while (low < high && L->r[low] <= pivotkey)
high++;
swap(L, low, high); // 将比枢轴大的记录交换到高端
}
return low; // 返回枢轴所在位置
}
/**
* 对顺序表 L 中的子序列 L->r[low..high] 作快速排序
*/
void QSort(SqList *L, int low, int high){
int pivot;
if (low < high) {
pivot = Partition(L, low, high); // 将L->r[low..high]一分为二，算出枢轴值pivot
QSort(L, low, pivot-1); // 对 低子表递归排序
QSort(L, pivot+1, high); // 对 高子表递归排序
}
}
/**
* 对顺序表 L 作快速排序
*/
void QuickSort(SqList *L){
QSort(L, 1, L->length);
}
快速排序的代码说明
-
Partition函数就是将选取的pivotkey不断交换，将比它小的换到它的左边，比它大的交换到它的右边，它也在交换中不断更改自己的位置，直到完全满足这个要求为止。 - 快速排序的时间性能取决于快速递归的深度，快排的时间复杂度为
O(nlogn)。 - 快速排序的空间复杂度主要是递归造成的栈空间的使用，平均情况下空间复杂度为
O(nlogn)。 - 由于关键字的比较和交换是跳跃进行的，因此，快排是一种不稳定的排序算法
快速排序的优化
-
优化选取枢轴
在上面的代码中，选取枢轴的方式为：pivotkey = L->r[low]，即用序列的第一个元素作为枢轴，这是理想情况下L->r[low]是中间数。但是对于其他情况，这种固定选取第一个关键子作为首个枢轴的方法就不是很合理。于是可以用下面的方法优化：- 三数取中(median-of-three)法：取三个关键子进行排序，将中间数作为枢轴，一般取左端、右端和中间三个数，也可以随机选取。
- 九数取中(median-of-nine)法：先从数组中分三次取样，每次取三个数，三个样品各取中数，然后从这三个数当中再取出一个中数作为枢轴。
三数取中(median-of-three)法代码：
int pivotkey;
int m = low + (high - low)/2; // 计算数组中间元素的小标
if (L->r[low] > L->r[high])
swap(L, low, high); // 交换左端与右端数据， 保证左端较小
if (L->r[m] > L->r[high])
swap(L, high, m); // 交换中间与右端数据， 保证中间较小
if (L->r[m] > L->r[low])
swap(L, m, low); // 交换中间与左端数据， 保证左端较小
pivotkey = L->r[low]; // 用子表的第一个记录作枢轴记录
- 优化不必要的交换
- 优化小数组时的排序方案
- 优化递归操作
快速排序优化后的代码
#pragma - 9.快速排序(优化)
// 优化方式：1.优化选取枢轴 2.优化不必要的交换 3.优化小组时的排序方案 4.优化递归操作
/**
* 交换顺序表 L 中子表的记录，使轴记录到位，并返回其所在位置
* 此时在它之前的记录均不大于它，在它之后的记录均不小于它
*/
int Partition1(SqList * L, int low, int high){
int pivotkey;
int m = low + (high - low)/2; // 计算数组中间元素的小标
if (L->r[low] > L->r[high])
swap(L, low, high); // 交换左端与右端数据， 保证左端较小
if (L->r[m] > L->r[high])
swap(L, high, m); // 交换中间与右端数据， 保证中间较小
if (L->r[m] > L->r[low])
swap(L, m, low); // 交换中间与左端数据， 保证左端较小
pivotkey = L->r[low]; // 用子表的第一个记录作枢轴记录
L->r[0] = pivotkey; // 将枢轴关键字备份到 L->r[0]
while (low < high) { // 从表的两端交替地向中间扫描
while (low < high && L->r[high] >= pivotkey)
high--;
L->r[low] = L->r[high];
while (low < high && L->r[low] <= pivotkey)
low++;
L->r[high] = L->r[low];
}
L->r[low] = L->r[0];
return low; // 返回枢轴所在位置
}
#define MAX_LINEGIH_INSERT_SORT 7 // 数组长度阈值
/**
* 对顺序表 L 中的子序列 L.r[low..high]作快速排序
*/
void QSort1(SqList *L, int low, int high){
int pivot;
if ((high -low) > MAX_LINEGIH_INSERT_SORT) {
while (low < high) {
pivot = Partition1(L, low, high); // 将L->r[low..high]一分为二，算出枢轴值pivot
QSort1(L, low, pivot-1); // 对 低子表递归排序
// QSort1(L, pivot+1, high); // 对 高子表递归排序
low = pivot+1; // 尾递归
}
}else // 当 high-low 小于等于常数时直接插入排序
InsertSort(L);
}
/**
* 对顺序表 L 作快速排序
*/
void QuickSort1(SqList *L){
QSort1(L, 1, L->length);
}
排序总结
1. 排序分类
- 希尔排序相当于直接插入排序的升级，同属于插入排序类
- 堆排序相当于简单选择排序的升级，同属于选择排序类
- 快速排序相当于冒泡排序的升级，同属于交换排序类
排序分类
2. 性能比较
性能比较
