数据结构与算法
排序
2017年春
本次课内容
排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素(或记录)集合或序列重新排列成一个按关键字有序的序列。
为了便于查找，通常希望计算机中的数据表示按关键字有序的。如有序的则折半查找，查找效率较高。还有，二叉排序树的构造过程本身就是一个排序的过程。因此，学习和研究各种排序方法是计算机工作者的重要课题之一。
排序基本概念
为了便于讨论，在此首先要对排序下一个确切地定义：
假设含\(n\)个记录的序列为
其相应的关键字序列为
\[\lbrace K_1, K_2, … , K_n\rbrace\]
需确定\(1, 2,\cdots, n\)的一种排列\(p1, p2,\cdots, pn\)，使其相应的关键字满
如下的非递减(或非递增)关系
\[K_{p1}\leq K_{p2}\leq … \leq K_{pn}\]
或\[(K_{p1}\geq K_{p2}\geq …\geq K_{pn})\]
即使公式的序列成为一个按关键字有序的序列
\[\lbrace R_{p1}, R_{p2},…,R_{pn}\rbrace\]
这样一种操作称为排序。
排序基本概念二
若关键字是主关键字，则对任意待排序序列，经排序后得到的结果是唯一的；若关键字是次关键字，排序结果可能不唯一，这是因为待排序的序列中可能存在两个或者两个以上具有相同关键字的值得记录。
假设\(K_i=K_j(1\leq i \leq n,1\leq j \leq n,i \neq j)\)，且在排序前的序列中\(R_i\)领先于\(R_j\)，(即\(i<j\))。若能保证在排序后的序列中\(R_i\)仍领先于\(R_j\)，则称此方法是稳定的；反之，若可能使排序后的序列中\(R_j\)领先于\(R_i\)，则称此排序方法是不稳定的。
排序基本概念三
排序分为两类：内排序和外排序
内排序：指待排序序列完全存放在内存中所进行得排序过程。适合不太大的元素排序。
外排序：指排序过程中还需要访问外存储器。非常大的元素序列，因不能完全放入内存，只能使用外排序。如大的数据库记录的排序一般需要外排序，但内排序方法是外排序方法的基础。
直接插入排序
插入排序基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，是稳定的排序方法。
基本思路
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
假设有\(n\)个记录，存放在数组\(r\)中，重新安排记录在数组中的存放顺序，使得按关键字有序。即
\[r[1].key \leq r[2].key \leq \cdots \leq r[n].key\]
设\(1<j \leq n\)，\(r[1].key \leq r[2].key \leq \cdots \leq r[j-1].key\)，将\(r[j]\)插入，重新安排存放顺序，使得\(r[1].key \leq r[2].key \leq \cdots \leq r[j].key\)，得到新的有序表，记录数增1。
直接插入排序步骤
第一步：
$r[0]=r[j]$；//$r[j]$送$r[0]$中，使$r[j]$为待插入记录空位
$i=j-1$； //从第$i$个记录向前测试插入位置，用$r[0]$为辅助单元可以免掉测试$i<1$第二步：
若$r[0].key \geq r[i].key$，转第四步。//插入位置确定第三步：
若$r[0].key<r[i].key$时，$r[i+1]=r[i];i=i-1$，转第二步。//调整待插入位置第四步：
$r[i+1]=r[0]$；结束。//存放待插入记录直接插入排序实现
算法如下：
void insert_sort(StructTable *p){
int i, j;
for (i = 2; i <= p->length; i++) { /* p->length即为表长度n */
/* 小于时，需将r[i]插入有序表 */
if (p->r[i].key < p->r[i - 1].key) {
p->r[0] = p->r[i]; /* 为统一算法设置监测 */
for (j = i - 1; p->r[0].key < p->r[j].key; j--)
p->r[j + 1] = p->r[j]; /* 记录后移 */
p->r[j + 1] = p->r[0]; /* 插入到正确的位置 */
}
}
}直接插入排序算法分析
算法采用的是查找比较操作和记录移动操作交替进行得方法。具体的做法是将插入记录\(R[i]\)的关键字依次与有序区中记录\(R[j](j=i-1,i-2,\cdots,1)\)的关键字进行比较，若\(R[j]\)的关键字大于\(R[i]\)，则将\(R[j]\)后移一个位置。若\(R[j]\)的关键字小于或等于\(R[i]\)，则查找过程结束\(j+1\)即为\(R[i]\)的插入位置。因为关键字比\(R[i]\)大的记录均已后移，故只要将\(R[i]\)插入该位置即可。
算法中借助了一个附加记录\(R[0]\)，其作用有两个：一是进入查找循环之前，它保存了\(R[i]\)的副本，使得不至于因为记录的后移而丢失\(R[i]\)中的内容；二是在for循环中，“监视”下标变量\(j\)是否越界。因此我们将\(R[0]\)称为“监视哨”，这使得测试循环条件的时间减少一半。
从排序过程中不难看出，它是一个稳定的排序方法。
直接插入排序性能分析
空间效率：仅用了一个辅助单元。
时间效率：向有序表中逐个插入记录的操作，进行了\(n-1\)趟，每趟操作分为比较关键字和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键字的初始排序。
直接插入排序时间复杂度
最好的情况下：即待排序列已按照关键字有序，每趟操作只需1次比较和2次移动。总比较次数\(n-1\)次；总移动次数\(2(n-1)\)次
最坏的情况下：即第\(j\)趟操作，插入记录需要同前面的\(j\)个记录进行\(j\)次关键字比较，移动记录的次数为\(j+2\)次。总比较次数\(\sum_{j=1}^{n-1} j=\frac {1}{2} n(n-1)\)次；总移动次数\(\sum_{j=1}^{n-1} (j+2)=\frac {1}{2}(n-1)(n+4)\)次
平均情况下：即第\(j\)趟操作，插入记录大约同前面的\(j/2\)个记录进行关键码比较，移动记录的次数为\(j/2+2\)次。
总比较次数： \[\sum_{j=1}^{n-1} {\frac {j}{2}}=\frac {1}{4} n(n-1) \approx \frac {1}{4}n^{2}\]
总移动次数： \[\sum_{j=1}^{n-1} (\frac {j}{2}+2)=\frac {1}{4} n(n-1)+2(n-1) \approx \frac {1}{4} n^{2}\]
直接插入排序图示
直接插入排序的时间复杂度为\(O(n^2)\)。但在待排序序列基本有序的情况下，复杂度可以大大降低。这是本方法的重要优点。下一节的希尔排序就是利用这个优点改进的方法。
希尔排序
插入排序基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，是稳定的排序方法。
基本思路
希尔排序的基本思想是：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序又称缩小增量排序，是直接插入排序算法的一种更高效的改进版本，是1959年由D.L.Shell提出来的。它的做法是：
- 选择一个步长序列\(t_1,t_2,\cdots,t_k\)，其中\(t_i>t_j(i<j)\)，\(t_k=1\);
- 按步长序列个数\(k\)，对序列进行\(k\)趟排序；
- 每趟排序，根据对应步长\(t_i\)，将待排序分割成若干长度为\(m\)的子序列，分别对各子表进行插入排序。仅步长因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
希尔排序实例
对下面数组进行排序的时候，首先以4为步长，这是元素分为了LMPT，EHSS，ELOX，AELR几个序列，我们对这几个独立的序列进行插入排序，排序完成之后，我们减小步长继续排序，最后直到步长为1，步长为1即为一般的插入排序，他保证了元素一定会被排序。希尔排序的增量递减算法可以随意指定，可以以N/2递减，只要保证最后的步长为1即可。
希尔排序算法实现
/* 一趟增量为dk的插入排序，dk为步长因子 */
void shell_insert(StructTable *p, int dk){
int i, j;
for (i = dk + 1; i <= p->length; i++)
if (p->r[i].key < p->r[i - dk].key) { /* 小于时，需将r[i]插入有序表 */
p->r[0] = p->r[i]; /* 为统一算法设置监测 */
for (j = i - dk; j > 0 && p->r[0].key < p->r[j].key; j = j - dk)
p->r[j + dk] = p->r[j]; /* 记录后移 */
p->r[j + dk] = p->r[0]; /* 插入到正确的位置 */
}
}
/* 按增量序列dlta[0,1...,t-1]队顺序表*p作希尔排序 */
void shell_sort(StructTable *p, int dlta[], int t) {
int k;
for (k = 0; k < t; k++)
shell_insert(p, dlta[k]); /* 一趟增量为dlta[k]的插入排序 */
}希尔排序特点
子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列。
希尔排序可提高排序速度，因为分组后\(n\)值减小，\(n^2\)更小，而\(T(n)=O(n^2)\),所以\(T(n)\)从总体上看是减小了。
关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序。
增量序列取法：无除1以外的公因子，最后一个增量值必须为1。
对希尔排序的分析
希尔排序时效分析很难，关键字的比较次数与记录移动次数依赖于步长因子序列的选取，特定情况下可以确估算出关键字的比较次数和记录的移动次数。目前还没有人给出选取最好的步长因子序列的方法。步长因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：步长因子中除1外没有公因子，且最后一个步长因子必须为1。
希尔排序方法是一个不稳定的排序方法。
交换排序
交换排序主要是通过两两比较待排记录的关键字，若发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。介绍两种交换排序：冒泡排序和快速排序。
冒泡排序
基本思路
设想被排序的记录数组\(R[1 ..n]\)垂直竖立，将每个记录\(R[i]\)看作是重量为\(R[i].key\)的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组\(R\)，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。
冒泡排序图示
对任一祖记录进行冒泡排序时，至多要进行\(n-1\)趟排序过程。但是，若在某一趟排序中没有记录需要交换，则说明待排序记录已按关键字有序，因此，冒泡排序过程便可以提前终止。
冒泡排序算法实现
引入一个布尔量noswap，在每趟结束之前，先将它置为TRUE，在排序过程中有交换发生时改为FALSE。在一趟排序结束时，我们再检查noswap，若未曾交换过算法便终止算法。
void bubble_sort(StructTable *p){
int i, j, n, noswap = 0;
ElementType swap;
n = p->length;
/* 每次循环初始化noswap，如果一次循环结束后仍然为TRUE，说明表完成排序 */
for (i = 1; i <= n - 1 && !noswap; i++) {
noswap = TRUE;
for (j = n - 1; j >= i; j--)
/* 如果相邻两个数不是按从小到大排列，交换两数 */
if (p->r[j].key > p->r[j + 1].key) {
swap = p->r[j];
p->r[j] = p->r[j + 1];
p->r[j + 1] = swap;
noswap = FALSE; /* 进入下一次循环 */
}
}
}对冒泡排序的分析
时间效率：总共要进行\(n-1\)趟冒泡，对\(j\)个记录进行一趟冒泡需要\(j-1\)次关键字比较。
总比较次数：\(\sum_{j=2}^{n} (j-1)=\frac {1}{2}n(n-1)\)
移动次数：
最好的情况下，待排序已有序，不需要移动；
最坏的情况下，每次比较后均要进行三次移动(数据交换)，移动次数=\(\sum_{j=2}^{n} 3(j-1)=\frac {3}{2}n(n-1)\)因此，冒泡排序的最坏时间复杂度为\(O(n^2)\)，排序的平均时间的复杂度也是\(O(n^2)\)。
冒泡排序是就地排序，它是稳定的。
快速排序
基本思路
快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序图示
“6 1 2 7 9 3 4 5 10 8”
快速排序实现
/* 递归形式的快速排列 */
/* 对顺序表tbl中的子序列tbl->[low...high]作快速排列 */
void quick_sort(SturctTable *tbl, int low, int high) {
int pivotloc;
if(low < high) {
pivotloc = partition(tbl, low, high); /* 将表一分为二 */
quick_sort(tbl, low, pivotloc - 1); /* 对低子表递归排序 */
quick_sort(tbl, pivotloc + 1, high); /* 对高子表递归排序 */
}
}
/* 一趟快速排序 */
/* 交换顺序表tbl中子表tbl->[low...high]的记录，使支点记录到位，并返回其所在位置，此时在它之前（后）的记录均不大（小）于它 */
int partition(StructTable *tbl, int low, int high) {
int pivotkey;
tbl->r[0] = tbl->r[low]; /* 以子表的第一个记录作为支点记录 */
pivotkey = tbl->r[low].key; /* 取支点记录关键字 */
while(low < high) { /* 从表的两端交替地向中间扫描 */
while(low < high && tbl->r[high].key >= pivotkey)
high--;
tbl->r[low] = tbl->r[high]; /* 将比支点记录小的交换到低端 */
while(low < high && tbl->r[low].key <= pivotkey)
low++;
tbl->r[high] = tbl->r[low]; /* 将比支点记录大的交换到高端 */
}
tbl->r[low] = tbl->r[0]; /* 支点记录到位 */
return low; /* 返回支点记录所在位置 */
}对快速排序的分析
对快速排序的效率进行分析可知：
空间效率：快速排序是递归的，每层递归调用时的指针和参数均要求用栈来存放，递归调用层次数和上述二叉树的深度一致。因而，存储开销在理想情况下为\(O(\log_2 n)\)，即深度递归；在最坏的情况下，即是一个单链，为\(O(n)\)。
时间效率：在\(n\)个记录的待排序列中，一次划分需要约\(n\)次关键字比较，时效为\(O(n)\)，若设\(T(n)\)为对\(n\)个记录待排序进行快速排序所需要的时间。
快速排序是一个不稳定的排序方法。
快速排序的特点
快速排序是通常被认为在同数量级\((O(n\log_2 n))\)的排序方法中平均性能最好的。但若初始序列按关键字有序或基本有序时，快速排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取支点记录，即排序区间的两个端点与重点三个记录关键字居中的调整为支点记录。
选择排序
基本思路
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
下面介绍一种简单的选择排序方法——简单选择排序（或直接选择排序）
操作方法：第一趟，从\(n\)个记录中找出关键字最小的记录与第一个记录交换；第二趟，从第二个记录开始的\(n-1\)个记录中再选出关键字最小的记录与第二个记录交换；如此，第\(i\)趟，则从第\(i\)个记录开始的\(n-i+1\)个记录中选出关键字最小的记录与第\(i\)个记录交换，直到整个序列按关键字有序。
简单选择排序
简单选择排序一句话概括：每次选择无序数列中最小的将其放在有序数列的最前面。
简单选择排序算法实现
void select_sort(StructTable *s) {
int i, j, t;
ElementType swap;
/* 作length - 1趟选取 */
for(i = 1; i < s->length; i++) {
/* 在i开始的length - i + 1个记录中选关键码最小的记录 */
for (j = i + 1, t = i; j <= s->length; j++) {
if(s->r[t].key > s->r[j].key)
t = j; /* t中存放关键码最小记录的下标 */
}
/* 关键码最小的记录与第i个记录交换 */
swap = s->r[t];
s->r[t] = s->r[i];
s->r[i] = swap;
}
}对简单选择排序的分析
简单选择排序移动次数较少，但关键字的比较次数依然是\(\frac {1}{2}n(n+1)\)，所以时间复杂度仍为\(O(n)\)。
直接选择排序是一个不稳定的排序方法。
归并排序
归并排序是又一类不同的排序方法。“归并” 的含义是将两个或者两个以上的有序表组合成一个新的有序表。它的实现方法早已为读者所熟悉，无论是顺序存储结构还是链表存储结构，都可在\(O(m+n)\)的时间量级上实现。利用归并的思想容易实现排序。假设初始序列含有\(n\)个记录，则可以看成是\(n\)个有序的子序列，每个子序列的长度为1，然后两两归并，得到\([\frac {n}{2}]\)个长度为2或1的有序子序列；再两两归并，……，如此重复，直到得到 一个长度为\(n\)的有序序列为止，其核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。
二路归并排序
基本思路
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。
若将两个有序表合并成一个有序表，称为二路归并。
二路归并排序的基本操作是将两个有序表合并为一个有序表。设\(r[u\cdots t]\)由两个有序子表\(r[u\cdots v-1]\)和\(r[v\cdots t]\)组成，两个子表长度分别为\(v-u\)、\(t-v+1\)。要将它们合并为一个有序表\(vf[u\cdots t]\)，只要设置三个指示器\(i\)、\(j\)和\(k\)，其初值分别是这三个记录区的首位置。合并时依次比较\(r[i]\)和\(r[j]\)的关键字，取关键字较小的记录复制到\(rf[k]\)中，然后将指向被复制记录的指示器和指向复制位置的指示器\(k\)分别加1，重复这一过程，直到全部记录被复制到\(rf[u\cdots t]\)为止。
二路归并排序图示
对二路归并排序的分析
由于归并排序需要一个与表等长的辅助元素数组空间，所以空间复杂度为\(O(n)\)
对\(n\)各元素的表，将这\(n\)个元素看作叶节点，若将两两归并生成的子表看作它们的父节点，则归并过程对应由叶向根生成一颗二叉树的过程。所以归并趟数约等于二叉树的高度-1，即\(\log_{2} n\)，每趟归并需移动记录\(n\)次，故时间复杂度为\(O(n\log_{2} n)\)。
二路归并排序是一个稳定的排序方法。
基数排序
基数排序(radix sorting)是和前面所述各类排序方法完全不相同的一种排序方法。从之前的讨论中可以看出，实现排序主要是通过关键字之间的比较和移动记录这两种操作，而实现基数排序不需要进行记录关键字之间的比较。基数排序是一种借助多关键字排序的思想，对单逻辑关键字进行排序的方法。
基本思路
基数排序将所有待比较数值(正整数)统一为同样的数位长度，数位较短的数前面补零。 然后 从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后， 数列就变成一个有序序列。
多关键字的排序
为实现多关键字排序，通常有两种方法：
第一种方法是：先对最主位关键字\(K_0\)进行排序，将序列分为若干子序列，每个子序列中的记录都具有相同的\(K_0\)值，然后就每个子序列对关键字\(K_1\)进行排序，按照\(K_1\)值不同分成若干更小的子序列，一次重复，直到对\(K_{d-2}\)进行排序后得到的每一子序列中的记录都具有相同关键字\((K_0,K_0,\cdots,K_{d-2})\)，而后分别对每个子序列对\(K_{d-1}\)进行排序，最后将所有子序列依次连接在一起成为一个有序序列，这个方法称之为最高位优先(Most Significanct Digit first)法，简称MSD法；
第二种方法是从最次位关键字\(K_{d-1}\)起进行排序。然后再对高一位的关键字\(K_{d-2}\)进行排序，依次重复，直至对\(K_0\)进行排序后便称为一个有序序列。这种方法称之为最低位优先(Least Significanct Digit first)法，简称LSD法。
基数排序图示
基数排序是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。
T = [ 2314, 5428, 373, 2222, 17 ]
基数排序发展历史
早在计算机出现之前，利用卡片分类机对穿孔卡上的记录进行排序就是用的这种方法。然而，在计算机出现之后却长期得不到应用，原因是所需的辅助存储量（\(RADIX \times N\)个记录空间）太大。直到1954年有人提出用“计数”代替“分配”才使基数排序得以在计算机上实现，但此时仍需要\(n\)个记录和\(2\times RADIX\)个计数单元的辅助空间。此后，有人提出用链表作存储结构，则又省去了\(n\)个记录的辅助空间。
基数排序算法实现
void radix_sort(StaticList &list) {
/* list是采用静态链表表示的顺序法 */
/* 对list作基数排序，使得list成为按关键字自小到大的有序静态链表，list.r[0]为头结点 */
for(i = 0; i < list.recnum; i++)
list.r[i].next = i + 1;
list.r[recnum].next = 0; /* 将list改造为静态链表 */
for(i = 0; i < list.keynum; i++) { /* 按最低位优先依次各关键字进行分配和收集 */
distribute(list.r, i, f, e); /* 第i趟分配 */
collect(list.r, i, f, e); /* 第i趟收集 */
}
}/* radix_sort */
void distribute(StaticListNode &r, int i, ArrType &f, ArrType &e) {
/* 静态链表list的r域中记录已按(keys[0],...,keys[i-1])有序 */
/* 本算法按第i个关键字keys[i]建立RADIX个子表，使同一子表中记录keys[i]相同 */
/* f[0...RADIX-1]和e[0...RADIX-1]分别指向各子表中第一个和最后一个记录 */
for(j = 0; j < Radix; j++)
f[j] = 0; /* 各子表初始化为空表 */
for(p = r[0].next; p; p = r[p].next) {
j = ord(r[p].keys[i]); /* ord将记录中第i个关键字映射到[0...RADIX-1] */
if(!f[j])
f[j] = p;
else
r[e[j]].next = p;
e[j] = p; /* 将p所指的结点插入第j个子表中 */
}
}/* distribute */
void collect(StaticListNode &r, int i, ArrType f, ArrType e) {
/* 本算法按keys[i]自小至大地将f[0...RADIX-1]所指各子表依次链接成一个链表 */
/* e[0...RADIX]为各子表的尾指针 */
for (j = 0; !f[j]; j = succ(j)); /* 找第一个非空子表，succ为求后继函数 */
r[0].next = f[j]; /* r[0].next指向第一个非空子表中第一个结点 */
t = e[j];
while (j < RADIX) {
for (j = succ(j); j < RADIX-1 && !f[j];j = succ(j)); /* 找下一个非空子集 */
/* 链接两个非空子表 */
if (f[j]) {
r[t].next = f[j];
t = e[j];
}
}
r[t].next = 0; /* t指向最后一个非空子表中的最后一个结点 */
}/* collect *排序算法总览
实验内容
对于之前实现的链表和ArrayList，分别添加一个函数sort
- 能够对线性表中存储的数据进行排序
- 函数要有单元测试
- 思考：哪些排序方法适合链表