数据结构学习笔记—

数据结构学习笔记——排序

1. 分类

2. 7种内排序算法的各种指标

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性	移动次数的平均情况	移动次数的最好情况	移动次数的最坏情况
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定	O(n²)	0	O(n²)
简单选择排序	O(n²)	O(n²)	O(n²)	O(1)	稳定	O(n)	0	O(n)
直接插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定	O(n²)	O(n)	O(n²)
希尔排序	O(nlogn)~O(n²)	O(n^1.3)	O(n²)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(nlogn)	O(n²)	O(logn)~O(n)	不稳定

3. 分析（“>”表示优于）

从平均情况看：

堆排序、归并排序、快速排序 > 希尔排序 > 简单算法

从最好情况看：

冒泡排序、直接插入排序 > 其它算法

从最坏情况看：

堆排序、归并排序 > 其它算法

从空间复杂度看：

简单算法、希尔排序、堆排序 > 快速排序 > 归并排序

从稳定性看：

简单算法、归并排序 > 希尔排序、堆排序、快速排序

从移动次数的平均情况看：

简单选择排序 > 冒泡排序、直接插入排序

从移动次数的最好情况看：

简单选择排序、冒泡排序 > 直接插入排序

从移动次数的最坏情况看：

简单选择排序 > 冒泡排序、直接插入排序

4. 结论

堆排序和归并排序发挥稳定，快速排序最坏情况时发挥较差；
如果待排序序列总是基本有序，应选择简单算法；
如果对内存使用量有要求（即对空间大小有要求），不应选择归并排序和快速排序；
如果对排序稳定性有要求，应选择简单算法或归并排序；
如果待排序记录的个数n越小，应采用简单算法，反之，n越大，应选择改进算法；
如果数据量不大但记录的关键字信息量较大，应选择简单选择排序（在简单算法中），因为当记录的关键字本身信息量较大时，其占用存储空间较大，在移动记录时所花费的时间就越多，另外，记录的关键字信息量大小对改进算法影响不大；
从综合各项指标来说，经过优化的快速排序是性能最好的排序算法。

5. 具体实现

冒泡排序

正宗冒泡排序

 1 /* 对顺序表L作冒泡排序 */
 2 void BubbleSort(SqList *L)
 3 {
 4     int i,j;
 5     for(i = 1; i < L->length; i++)
 6     {
 7         for(j = L->length - 1; j >= 1; j--) /* 注意j是从后往前循环 */
 8         {
 9             if(L->r[j]>L->[j + 1]) /* 若前者大于后者 */
10             {
11                 swap(L, j, j + 1); /* 变换L->r[j]与L->r[j + 1]的值 */
12             }
13         }
14     }
15 }

改进冒泡排序

 1 void BubbleSort(SqList *L)
 2 {
 3     int i,j;
 4     Status flag = TRUE; /* flag用来作为标记 */
 5     for(i = 1; i < L->length && flag; i++) /* 若flag为true则退出循环 */
 6     {
 7         flag = FALSE; /* 初始为false */
 8         for(j = L->length - 1; j >= 1; j--) /* 注意j是从后往前循环 */
 9         {
10             if(L->r[j]>L->[j + 1]) /* 若前者大于后者 */
11             {
12                 swap(L, j, j + 1); /* 变换L->r[j]与L->r[j + 1]的值 */
13                 flag = TRUE; /* 如果有数据交换，则flag为true */
14             }
15         }
16     }
17 }

简单选择排序

 1 /* 对顺序表L作简单选择排序 */
 2 void SelectSort(SqList *L)
 3 {
 4     int i,j,min;
 5     for(i = 1; i < L->length; i++)
 6     {
 7         min = 1; /* 将当前下标定义为最小值下标 */
 8         for(j = i + 1; j <= L->length; j++) /* 循环之后的数据 */
 9         {
10             if(L->r[min] > L->r[j]) /* 如果有小于当前最小值的关键字 */
11                 min = j; /* 将此关键字的下标赋值给min */
12         }
13         if(i != min) /* 若min不等于i，说明找到最小值，交换 */
14             swap(L,i,min); /* 变换L->r[i]与L->r[min]的值 */
15     }
16 }

直接插入排序

 1 /* 对顺序表L作直接插入排序 */
 2 void InsertSort(SqList *L)
 3 {
 4     int i,j;
 5     for(i = 2; i <= L->length; i++)
 6     {
 7         if(L->r[i] < L->r[i - 1]) /* 需将L->r[i]插入有序子表 */
 8         {
 9             L->r[0] = L->r[i]; /* 设置哨兵 */
10             for(j = i - 1; L->r[j] > L->r[0]; j--)
11                 L->r[j + 1] = L->r[j]; /* 记录后移 */
12             L->r[j + 1] = L->r[0]; /* 插入到正确位置 */
13         }
14     }
15 }

希尔排序

 1 /* 对顺序表L作希尔排序 */
 2 void ShellSort(SqList *L)
 3 {
 4     int i,j;
 5     int increment = L->length;
 6     do
 7     {
 8         increment = increment/3 + 1; /* 增量序列 */
 9         for(i = increment + 1; i <= L->length; i++)
10         {
11             if(L->r[i] < L->r[i - increment])
12             { /* 需将L->r[i]插入有序增量子表 */
13                 L->r[0] = L->r[i]; /* 暂存在L->r[0] */
14                 for(j = i - increment; j > 0 && L->r[0] < L->r[j]; j -= increment)
15                 {
16                     L->r[j + increment] = L->r[j]; /* 记录后移，查找插入位置 */
17                     L->r[j + increment] = L->r[0]; /* 插入 */
18                 }
19             }
20         }
21     }
22     while(increment > 1);
23 }

堆排序

 1 /* 对顺序表L作堆排序 */
 2 void HeapSort(SqList *L)
 3 {
 4     int i;
 5     for(i = L->length / 2; i > 0; i--) /* 把L中的r构建成一个大顶堆 */
 6         HeapAdjust(L,i,L->length);
 7 
 8     for(i = L->length; i > 1; i--)
 9     {
10         swap(L,1,i); /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */
11         HeapAdjust(L,1,i - 1); /* 将L->r[1..i-1]重新调整为大顶堆 */
12     }
13 }
14 
15 /* 已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义 */
16 /* 本函数调整L->r[s]的关键字，使L->r[s..m]成为一个大顶堆 */
17 void HeapAdjust(SqList *L, int s, int m)
18 {
19     int temp,j;
20     temp = L->r[s];
21     for(j = 2 * s; j <= m; j *= 2) /* 沿关键字较大的孩子结点向下筛选 */
22     {
23         if(j < m && L->r[j] < L->r[j + 1])
24             ++j; /* j为关键字中较大的记录的下标 */
25         if(temp >= L->r[j])
26             break; /* rc应插入在位置s上 */
27         L->r[s] = L->r[j];
28         s = j;
29     }
30     L->r[s] = temp; /* 插入 */
31 }

归并排序

递归实现

 1 /* 对顺序表L作归并排序 */
 2 void MergeSort(SqList *L)
 3 {
 4     MSort(L->r, L->r, 1, L->length);
 5 }
 6 
 7 /* 将SR[s..t]归并排序为TR1[s..t] */
 8 void MSort(int SR[], int TR1[], int s, int t)
 9 {
10     int m;
11     int TR2[MAXSIZE + 1];
12     if(s == t)
13         TR1[s] = SR[s];
14     else
15     {
16         m = (s + t) / 2; /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
17         MSort(SR,TR2,s,m); /* 递归将SR[s..m]归并为有序的TR2[s..m] */
18         MSort(SR,TR2,m+1,t); /* 递归将SR[m+1..t]归并为有序的TR2[m+1..t] */
19         Merge(TR2,TR1,s,m,t); /* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
20     }
21 }
22 
23 /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
24 void Merge(int SR[], int TR[], int i, int m, int n)
25 {
26     int j,k,l;
27     for(j = m + 1, k = i; i <= m && j <= n; k++) /* 将SR中记录由小到大归并入TR */
28     {
29         if(SR[i] < SR[j])
30             TR[k] = SR[i++];
31         else
32             TR[k] = SR[j++];
33     }
34     if(i <= m)
35     {
36         for(l = 0; l <= m - i; l++)
37             TR[k + l] = SR[i + l]; /* 将剩余的SR[i..m]复制到TR */
38     }
39     if(j <= n)
40     {
41         for(l = 0; l <= n - j; l++)
42             TR[k + l] = SR[j + l]; /* 将剩余的SR[j..n]复制到TR */
43     }
44 }

非递归实现

 1 /* 对顺序表L作归并非递归排序 */
 2 void MergeSort(SqList *L)
 3 {
 4     int* TR = (int*)malloc(L->length * sizeof(int)); /* 申请额外空间 */
 5     int k = 1;
 6     while(k < L->length)
 7     {
 8         MergePass(L->r, TR, k, L->length);
 9         k = 2 * k; /* 子序列长度加倍 */
10         MergePass(TR, L->r, k, L->length);
11         k = 2 * k; /* 子序列长度加倍 */
12     }
13 }
14 
15 /* 将SR[]中相邻长度为s的子序列两两归并到TR[] */
16 void MergePass(int SR[], int TR[], int s, int n)
17 {
18     int i = 1;
19     int j;
20     while(i <= n - 2 * s + 1)
21     {
22         Merge(SR,TR,i,i+s-1,i+2*s-1); /* 两两归并 */
23         i = i + 2 * s;
24     }
25     if(i < n-s+1) /* 归并最后两个序列 */
26         Merge(SR, TR, i, i+s-1, n);
27     else
28         for(j = i; j <= n; j++)
29             TR[j] = SR[j];
30 }
31 
32 /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
33 void Merge(int SR[], int TR[], int i, int m, int n)
34 {
35     int j,k,l;
36     for(j = m + 1, k = i; i <= m && j <= n; k++) /* 将SR中记录由小到大归并入TR */
37     {
38         if(SR[i] < SR[j])
39             TR[k] = SR[i++];
40         else
41             TR[k] = SR[j++];
42     }
43     if(i <= m)
44     {
45         for(l = 0; l <= m - i; l++)
46             TR[k + l] = SR[i + l]; /* 将剩余的SR[i..m]复制到TR */
47     }
48     if(j <= n)
49     {
50         for(l = 0; l <= n - j; l++)
51             TR[k + l] = SR[j + l]; /* 将剩余的SR[j..n]复制到TR */
52     }
53 }

快速排序

基本实现

 1 /* 对顺序表L作快速排序 */
 2 void QuickSort(SqList *L)
 3 {
 4     QSort(L, 1, L->length);
 5 }
 6 
 7 /* 将顺序表L中的子序列L->r[low..high]作快速排序 */
 8 void QSort(SqList *L, int low, int high)
 9 {
10     int pivot;
11     if(low < higt)
12     {
13         pivot = Partition(L,low,high); /* 将L->r[low..high]一分为二，算出枢轴值pivot */
14         QSort(L,low,pivot-1); /* 对低子表递归排序 */
15         QSort(L,pivot+1,high); /* 对高子表递归排序 */
16     }
17 }
18 
19 /* 变换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置 */
20 /* 此时在它之前（后）的记录均不大（小）于它 */
21 int Partition(SqList *L, int low, int high)
22 {
23     int pivotkey;
24     pivotkey = L->r[low]; /* 用子表的第一个记录作枢轴记录 */
25     while(low < high) /* 从表的两段交替向中间扫描 */
26     {
27         while(low < high && L->[high] >= pivotkey)
28             high--;
29         swap(L,low,high); /* 将比枢轴记录小的记录交换到低端 */
30         while(low < high && L->[low] >= pivotkey)
31             low++;
32         swap(L,low,high); /* 将比枢轴记录大的记录交换到高端 */
33     }
34     return low; /* 返回枢轴所在位置 */
35 }

优化实现

 1 /* 优化1：优化选取枢轴，使用三数取中法或九数取中法 */
 2 /* 优化2：优化不必要的交换，采用替换进行操作 */
 3 /* 优化3：优化小数组时的排序方案，长度小时用直接插入排序，长度大时才使用快速排序 */
 4 /* 优化4：优化递归操作，采用迭代的方法代替可以缩减堆栈深度，提高整体性能 */
 5 
 6 /* 对顺序表L作快速排序 */
 7 void QuickSort(SqList *L)
 8 {
 9     QSort(L, 1, L->length);
10 }
11 
12 #define MAX_LENGTH_INSERT_SORT 7 /* 数组长度阀值 */
13 /* 将顺序表L中的子序列L->r[low..high]作快速排序 */
14 void QSort(SqList *L, int low, int high)
15 {
16     int pivot;
17     if((high - low) > MAX_LENGTH_INSERT_SORT)
18     { /* 当high-low大于常数时用快速排序 */
19         while(low < higt)
20         {
21             pivot = Partition(L,low,high); /* 将L->r[low..high]一分为二，算出枢轴值pivot */
22             QSort(L,low,pivot-1); /* 对低子表递归排序 */
23             low = pivot + 1; /* 尾递归 */
24         }
25     }
26     else /* 当high-low小于等于常数时用直接插入排序 */
27         InsertSort(L);
28 }
29 
30 /* 变换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置 */
31 /* 此时在它之前（后）的记录均不大（小）于它 */
32 int Partition(SqList *L, int low, int high)
33 {
34     int pivotkey;
35 
36     /* 优化选取枢轴，使用三数取中法 */
37     int m = low + (high - low) / 2; /* 计算数组中间的元素的下标 */
38     if(L->r[low] > L->r[high])
39         swap(L,low,high); /* 交换左端与右端数据，保证左端较小 */
40     if(L->r[m] > L->r[high])
41         swap(L,high,m); /* 交换中间与右端数据，保证中间较小 */
42     if(L->r[m] > L->r[low])
43         swap(L,m,low); /* 交换中间与左端数据，保证中间较小 */
44     /* 此时L.r[low]已经为整个序列左中右三个关键字的中间值 */
45 
46     pivotkey = L->r[low]; /* 用子表的第一个记录作枢轴记录 */
47     L->r[0] = pivotkey; /* 将枢轴关键字备份到L->r[0] */
48     while(low < high) /* 从表的两段交替向中间扫描 */
49     {
50         while(low < high && L->[high] >= pivotkey)
51             high--;
52         L->r[low] = L->r[high]; /* 采用替换而不是交换的方式进行操作 */
53         while(low < high && L->[low] >= pivotkey)
54             low++;
55         L->r[high] = L->r[low]; /* 采用替换而不是交换的方式进行操作 */
56     }
57     L->r[low] = L->r[0]; /* 将枢轴数值替换回L.r[low] */
58     return low; /* 返回枢轴所在位置 */
59 }