阅读量:0
目录
1.基本概念和排序方法概述
排序：将一组杂乱无章的数据按一定规律顺次排列起来。
即，将无序序列排成一个有序序列（由小到大或由大到小）的运算。
注意：如果参加排序的数据结点包含多个数据域，那么排序往往是针对其中某个域而言。
排序方法的分类
按数据存储介质：
内部排序和外部排序
内部排序：数据量不大、数据在内存，无需内外存交换数据
外部排序：数据量较大、数据在外存(文件排序)
外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。
按比较器个数：
串行排序和并行排序
串行排序：单处理机（同一时刻比较一对元素）
并行排序：多处理机（同一时刻比较多对元素）
按主要操作：
比较排序和基数排序
比较排序：比较的方法，插入排序、交换排序、选择排序、归并排序
基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序位置。
按辅助空间：
原地排序和非原地排序
原地排序：辅助空间用量为O(1)的排序方法。(所占的辅助存储空间与参加排序的数据量大小无关)
非原地排序：辅助空间用量超过O(1)的排序方法。
按稳定性：
稳定排序和非稳定排序
稳定排序：能够使任何数值相等的元素，排序以后相对次序不变。
非稳定性排序：不是稳定排序的方法。
排序的稳定性只对结构类型数据排序有意义。
按自然性：
自然排序和非自然排序
自然排序：输入数据越有序，排序的速度越快的排序方法。
非自然排序：不是自然排序的方法。
按排依据原则
插入排序：直接插入排序、折半插入排序、希尔排序
交换排序：冒泡排序、快速排序
选择排序：简单选择排序、堆排序
归并排序：2-路归并排序
基数排序
按排序所需工作量
简单的排序方法：T(n)=O(n^2)
基数排序：T(n)=O(d.n)
先进的排序方法：T(n)=O(nlogn)
存储结构—记录序列以顺序表存储:
#define MAXSIZE 20 //设记录不超过20个 typedef int KeyType; // 设关键字为整型量（int型） Typedef struct{ //定义每一个记录（数据元素）的结构 KeyType key;//关键字 InfoType otherinfo;//其他数据项 }RedType;//Record Type Typedef struct{ //定义顺序表的结构 RedType r[MAXSIZE+1];//存储顺序表的向量 int length;//顺序表的长度 }SqList;2.插入排序
1.直接插入排序
基本操作：有序插入
在有序序列中插入一个元素，保持序列有序，有序长度不断增加。
起初，a[0]是长度为1的子序列。然后，逐一将a[1]至a[n-1]插入到有序子序列中。
在插入a[i]前，数组a的前半段(a[0] ~ a[i-1])是有序断，后半段(a[i] ~ a[n-1])是停留在输入次序的“无序段”。
插入a[i]输入使得a[0] ~ a[i-1]有序，也就是要为a[i]找到有序位置j (0≤j≤i)，将a[i]插入在a[j]的位置上。
顺序表查找法
从后往前找就可以了。
赋值插入元素
记录后移，查找插入元素
插入到正确位置
x = a[i]; for(j = i - 1;j >= 0 && x < a[j]; j--) { a[j+1] = a[j]; } a[j-1] = x;或者使用“哨兵”来辅助实现插入的工作，
复制哨兵
记录后移，查找插入位置
插入到正确位置
L.r[0] = L.r[i]; for(j = i - 1;L.r[0].key < L.r[j].key; --j) { L.r[j+1] = L.r[j]; } L.r[j+1] = L.r[0]【直接插入算法】
void InsertSort(SqList &L) { int i, j; for(i = 2;i <= L.length; ++i) { if(L.r[i].key < L.r[i-1]) { //如小于，则将L.r[i]插入有序子表 L.r[0] = L.r[i];//复制哨兵 for(j = i-1;L.r[0].key < L.r[i].key; --j) { L.r[j+1] = L.r[j];//记录后移 } L.r[j+1] = L.r[0];//插入到正确位置 } } }实现排序的基本操作有两个：
“比较”序列中两个关键字的大小；
“移动”记录；
最好的情况（关键字在记录序列中顺序有序）
最坏的情况（关键字在记录序列中逆序有序）
时间复杂度：
原始数据越接近有序，排序速度越快
最坏情况下（输入数据是逆有序的）Tw(n) = O(n^2)
平均情况下，耗时差不多是最坏情况的一半 Te(n) = O(n^2)
要提高查找速度
减少元素的比较次数
减少元素的移动次数
2.折半插入排序
前提是对已经排过序的数据进行插入操作
【折半插入排序算法】
void BInsertSort(SqList &L) { for(i = 2;i <= L.length; ++i) { //依次插入第2个~第n个元素 L.r[0] = L.r[i];//当前插入元素存到“哨兵”位置 low = 1; high = i - 1;//采用二分查找法插入位置 while(low <= high) { mid = (low+high) / 2; if(L.r[0].key < L.r[mid].key) high = mid - 1; else low = mid + 1; }//循环结束，high+1则为插入位置 for(j = i - 1;j >= high+1; --j) { //移动元素 L.r[j+1] = L.r[j]; } L.r[high+1] = L.r[0];//插入到正确位置 } }折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快；
它所需要的关键码比较次数与待排序对像序列的初始排列无关，仅依赖于对象个数。在插入第i个对象时，需要经过|Iog2 i|+1次关键码比较，才能确定它应插入的位置；
当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差；
在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少：
3.希尔排序
基本思想：
先将整个待排记录序列分割成若子序刻，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
特点：1. 缩小增量 2. 多遍插入排序
一次移动，移动位置较大，跳跃式地接近排序后的最终位置
最后一次只需要少量移动
增量序列必须是递减的，最后一个必须是1
增量序列应该是互质的
void ShellInsert(SqList &L, int dk) { //对顺序表L进行增量为dk的Shell排序，dk为步长因子 for(i = dk+k;i <= L.length; ++i) { if(r[i].key < r[i-dk].key) { r[0] = r[i]; for(j = i-dk;j > 0 && (r[0].key < r[i].key); j = j-dk) { r[j+dk] = r[j]; } r[j+dk] = r[0]; } } } void ShellSort(SqList &L, int dlta[], int t) { //按增量序列dlta[0……t-1]对顺序表L作希尔排序 for(k = 0;k < t; ++k) { ShellInsert(L, dlta[k]);//一趟增量为dlta[k]的插入排序 } }希尔排序算法效率与增量序列的取值有关
Hibbard增量序列
Dk=2k-1——相邻元素互质
最坏情况：Tworst=O(n3/2)
猜想：Tavg=O(n5/4)
Sedgewick增量序列 {1, 5, 19, 41, 109, …}
——9* 4i-9 * 2i+1 或 4-3 * 2i + 1
猜想：Tavg=O(n7/6) Tworst=O(n4/3)
希尔排序法是一种不稳定的排序算法
我们发现有两个值是相等的，它们两个数的位置发生了变化
时间复杂度是n和d的函数：
O(n1.25) ~ O(1.6n1.25) 一 经验公式
空间复杂度为O(1)
如何选择最佳d序列，目前尚未解决
最后一个增量值必须为1，无除了1之外的公因子
3.交换排序
基本思想：两两比较，如果发生逆序则交换，知道所有记录都排好序为止。
常见的交换排序方法：
冒泡排序 O(n2)
快速排序 O(nlog2n)
1.冒泡排序
基本思想：每趟不断将记录两两比较，并按照“前小后大”规则交换
例：6个记录 21, 25, 49, 25* , 16, 08
第1趟结束：21, 25, 25* , 16, 08, 49
第2趟结束：21, 25, 16, 08, 25* , 49
第3趟结束：21, 16, 08, 25, 25* , 49
第4趟结束：16, 08, 21, 25, 25* , 49
第5趟结束：08, 16, 21, 25, 25* , 49
void bubble_sort(SqList &L) { //冒泡排序算法 int m,i,j; Redtype x;//交换时临时存储 for(m = 1;m < n; m++) { if(L.r[j].key > L.r[j+1].key) { //发生逆序 x = L.r[j]; L.r[j] = L.r[j+1]; L.r[j+1] = x; } } }优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；
提高效率：一旦某一趟比较时不出现记录交换，说明已经排好序，就可以结束算法。
改进算法：
void bubble_sort(SqList &L) { //改进 int m,i,j,flag = 1; RedType x; for(m = 1;m <= n-1 && flag == 1; m++) { if(L.r[j].key > L.r[j+1].key) { flag = 1; x = L.r[j]; L.r[j] = L.r[j+1]; L.r[j+1] = x; } } }时间复杂度：
最好情况（正序）比较次数：n-1 移动次数：0
最坏情况（逆序）比较次数：(n-1)(n)/2 移动次数：3/2(n2-n)
冒泡排序算法的评价：
冒泡排序最好时间复杂度是O(n)
冒泡排序最坏时间复杂度为O(n2)
冒泡排序平均时间复杂度为O(n2)
冒泡排序算法中增加一个辅助空间temp,辅助空间为S(n)=O(1)
冒泡排序是稳定的
2.快速排序
改进的交换排序
基本思想：
任取一个元素（如：第一个）为中心（pivot：枢轴、中心点）
所有比它小的元素一律前方，比它大的一律后放，形成两个子表；
对各个子表重新选择中心元素并以此规则调整；
直到每个子表的元素只剩下一个
基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序
具体实现：选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边。
(枢轴)中间数：可以是第一个数、最后一个数、最中间一个数、任选一个数等。
每一趟的子表的形成是采用从两头向中间交替式逼近法；
由于每趟中对各子表的操作都相似，可采用递归算法。
例子：
对49, 38, 20, 97, 76进行快速排序，先取定49作为分类中间数，左右两边进行排序
第一次：38, 20, 49, 97, 76
第二次：20, 38, 49, 76, 97
void QSort(SqList &L, int low, int high) { //对顺序表L快速排序 if(low < high) { //长度大于1 pivotloc = Partition(L, low, high); //将L.r[low.high]一分为二，pivotloc为枢轴元素排好序的位置 QSort(L, low, pivotloc-1);//对低子表递归排序 QSort(L, pivotloc-1, high);//对高子表递归排序 } } void Partition(SqList &L, int low, int high) { L.r[0] = L.r[low]; pivotkey = L.r[low].key; while(low < high) { while(low < high && L.r[high].key >= pivotkey) --high; L.r[low] = L.r[high]; while(low < high && L.r[low].key <= pivotkey) ++low; L.r[high] = L.r[low]; } L.r[low] = L.r[0]; return low; } void main() { QSort(L, 1, L.length); }时间复杂度：
可以证明，平均计算时间是O(nlog2n)
Qsort():O(log2n)
Partition():O(n)
实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。
空间复杂度：
快速排序不是原地排序
由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度。（即使不用递归，也需要用用户栈）
在平均情况下：需要O(logn)的栈空间
最坏情况下：栈空间可达O(n)。
稳定性：
快速排序是一种不稳定的排序算法。
再对(46,50,68,74,79,85,90)进行快速排序划分呢？
由于每次枢轴记录的关键字都是大于其它所有记录的关键字，致使一次划分之后得到的子序列()的长度为0，这时已经退化成为没有改进措施的冒泡排序。
快速排序不适于对原本有序或基本有序的记录序列进行排序。
提升快速排序
划分元素的选取是影响时间性能的关键
输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序方法。
改变分元素的选取方法，至多只能改变算法平均情况的下的世界性能，无法改变最坏情况下的时间性能。即最坏情况下，快速排序的时间复杂性总是O(n2)
3.简单选择排序
基本思想：在待排序的数据中选出最大（小）的元素放在其最终的位置。
基本操作：
首先通过n-1次关键字比较，从n个记泰中找出关键字最小的记录，将它与第一个记录交换
再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将 它与第二个记录交换
重复上述操作，共进行-1趟排序后，排序结束
【算法】
void SelectSort(SqList &K) { for(i = 1;i < L.length; ++i) { k = i; for(j = i+1;j <= length; j++) { if(L.r[j].key < L.r[k].key) k = j;//记录最小值位置 } if(k != i) { int temp = L.r[i]; L.r[i] = L.r[k]; L.r[k] = temp; } } }时间复杂度
记录移动次数
最好情况：0
最坏情况：3(n-1)
比较次数：无论待排序列处于什么状态，选择排序所需进行的"比较”次数都相同
算法稳定性：
简单选择排序是不稳定排序
4.堆排序
堆的定义：
若n个元素的序列{a1 , a2 , …an}满足
ai ≤ a2i ai ≤ a2i+1 或者 ai ≥ a2i ai ≥ a2i+1
则分别称该序列{a1, a2, …an}为小根堆和大根堆。
从堆的定义可以看出，堆实质是满足如下性质的完全仁叉树；二叉树中任一非叶子结点均小于（大于）它的孩子结点
判断是否是堆：
{98 77 35 62 55 14 35 48}
{14 48 35 62 55 98 35 77}
满足完全二叉树排列形式，所以是堆
堆的调整：
小根堆：
输出堆顶元素，以堆中最后一个元素替代之；
然后将根节点值与左右子树的根节点进行比较，并从其中小者进行交换；
重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。
堆排序思想
若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列又建成一个堆，则得到n个元素的次小值（次大值）如此反复，便能得到一个有序序列，这个过程称之为堆排序。
堆的调整：
如何在输出堆顶元素后，调整剩余元素为一个新的堆？
小根堆：
输出堆顶元素之后，以堆中最后一个元素替代之：
然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行 交换；
重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的 调整过程为“筛选”
大根堆则排序方法相似。
堆的建立：
显然：单节点的二叉树是堆；在完全二叉树中所有以叶子结点（序号i ＞ n/2）为根的子树是堆。
由于堆的实质上是一个线性表，那么我们就可以顺序存储一个堆。
用一个示例来介绍小根堆的过程：
有关键字为49, 38, 65, 97, 76, 13, 27, 49的一组数据，将其按照关键字调整为一个小根堆。
从最后一个非叶子结点开始，从此向前调整：
调整从第n/2个元素开始，将以该元素为根的二叉树调整为堆；
将以序号为n/2-1的结点为根的二叉树调整为堆；
再以序号为n/2-2的结点为根的二叉树调整为堆；
再以序号为n/2-3的结点为根的二叉树调整为堆；
//将初始无序的R[1]到R[n]建成一个小根堆 for(i = n/2;i >= 1; i--) { HeapAdjust(R, i, n); }由以上分析知：
若对一无序序列建堆，然后输出根；重复该过程就可以由一个无需序列输出有序序列。
实质上，堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的。
堆排序算法：
void HeadSort(elem R[]) { //R[1]到R[n]进行堆排序 int i; for(i = n/2;i >= 1; i--) { HeapAdjust(R, i, n);//创建初始堆 } for(i = n;i >= 1; i--) { Swap(R[1], R[i]);//根与最后一个元素交换 HeapAdjust(R, 1, i-1);//对R[1]到R[i-1]重新建堆 } }算法性能分析
堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。堆排序在最坏情况下，其时间复杂度也为O(log2n)，这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列，都不会使堆排序处于"最好"或"最坏"的状态。
另外，堆排序仅需个记录大小供交换用的辅助存储空间。
然而堆排序是一种不稳定的排序方法，它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。
4.归并排序
基本思想：将两个或两个以上的有序子序列”归并“为一个有序序列
在内部排序中，通常采用的是2-路归并排序
即：将两个位置相邻的有序子序列R[L...m]和R[m+1...n]归并为一个有序序列R[l...n]
示例：
设初始关键字序列为[48 34 60 80 75 12 26 *48]
整个归并排序仅需log2n趟
设R[low]-R[mid]和R[mid+1]-R[high]为相邻，归并成一个有序序列R1[low]-R1[high]。
若SR[i].key <= SR[j].key，则TR[k] = RS[i]; k++; i++;
否则，TR[k] = SR[j]; k++; j++;
归并排序算法分析
时间效率：O(nlog2n)
空间效率：O(n)
因为需要一个与原始序列同样大小的辅助序列(R1)。这正是此算法的缺点。
稳定性：稳定
5.基数排序
基本思想：分配+收集
也叫桶排序或箱排序：设置若干个箱子，将关键字为k的记录放入第k个箱子，然后再按序号将非空的连接。
基数排序：数字是有范围的，均由0~9十个数字组成，则只需要设置十个箱子，相继按照个十百千……进行排序。
时间效率：O(k*(n+m))，k：关键字个数，m：关键字取值范围为m个值
基数排序是一个稳定的排序
例如：10000个人按照生日排序
年 月 日 3个关键字
假设取值范围分别是：1930~2018 1~ 12 1~31 0(n2)≈108 O(nlogn)≈105
0(k*(n+m)) ≈ (10000+89)+(10000+12)+(10000+31) ≈ 104
6.外部排序
在内存中进行的排序是内部排序，而在许多应用中，经常需要对大文件进行排序，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存中，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间地交换。这种排序方法就称为外部排序。
文件通常是按块存储在磁盘上的，操作系统也是按块对磁盘上的信息进行读写的。因为磁盘读 / 写的机械动作所需的时间远远超过内存运算的时间（相对而言可以忽略不记），因此在外部排序过程中的时间代价主要考虑访问磁盘的次数，即I/O次数。
外部排序通常采用归并排序法。它包括两个相对独立的阶段：
根据内存缓冲区大小，将外存上的文件分成若干长度为t的子文件，依次读入内存并利用内部排序方法对他们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串。
对这些归并段进行逐趟归并，是归并段逐渐由小到大，直至得到整个有序文件位置。
在外部排序中实现两两归并时，由于不可能将两个有序段及归并结果段同时存放在内存中，因此需要不停地将数据读出、写入磁盘，而这会耗费大量的时间。一般情况下：
外部排序的总时间 = 内存排序所需的时间 + 外存信息读取的时间 + 内部归并所需的时间
显然，外村信息读取地时间远大于内部排序和内部归并地的时间，因此应着力减少I/O次数。由于外村信息的读/写是以“磁盘块”为单位进行的，以8个归并段为例，可知每一趟归并需进行16次读和16次写，3趟归并并加上内部排序时所需进行的读/写，使得总共需进行128次读写。若改用4路归并排序，则只需2趟排序，外部排序时的总读写次数便减少为96。
因此增大归并路数可以减少归并趟数，进而减少总的磁盘I/O次数。
如果内存可以容纳n个元素的话，那么平均每个子串的长度为2m，也就是说，使用置换选择算法我们可以减少一半的子串数。
这种方法适合要排序的数据太多，以至于内存一次性装载不下。只能通过把数据分几次的方式来排序，把这种方法称为外部排序。
7.各类排序方法的综合比较
1.时间性能
按平均的时间性能来分，有三类排序方法：
时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；
时间复杂度为O(n2)的有：直接插入排序、冒泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；
时间复杂度为O(n)的排序方法只有：基数排序。
当待排记录序列按关键关顺序有序时，直接插入排序和冒泡排序能达到O(n)的时间复杂度；而对于快速排序而言，这是最不好的情况，此时的时间性能退化为O(n2),因此是应该尽量避免的情况。
简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的 分布而改变。
2.空间性能
指的是排序过程中所需的辅助空间大小
所有的简单排序方法（包括：直接插入、冒泡和简单选择）和堆排序的空间复杂度为O(1)
快速排序为O(logn)，为栈所需的辅助空间
归并排序所需辅助空间最多，其空间复杂度为O(n)
链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)
3.排序方法的稳定性能
稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。
当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序法。
对于不稳定的排序方法，只要能举出一个实例说明即可。
快速排序和堆排序是不稳定的排序方法。
4.关于“排序方法的时间复杂度的下限“
本章讨论的各种排序方法，除基数排序外，其它方法都是基于“"比较关键字”进行排序的排序方法，可以证明，这类排序法可能达到的最快的时间复杂度为O(nlogn)。(基数排序不是基于“比较关键字”的排序方法，所以它不受这个限制)。
可以用一棵判定树来描述这类基于“比较关键字”进行排序的排序方法
