排序算法归总

排序的基本概念
所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：
输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
（1）       排序的分类
1．  按是否涉及数据的内、外存交换分
内部排序：内部排序(简称内排序)，是带排序纪录存放在计算机内存中，并进行的排序过程。细分又可为：插入排序、选择排序、归并排序和基数排序；
外部排序：指的是带排序纪录的数量很大，以致内存一次不能容纳全部纪录，在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法。
注意：
1)         内排序适用于记录个数不很多的小文件
2)         外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。
2．  按策略划分内部排序方法
可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。
（2）       排序算法的基本操作
大多数排序算法都有两个基本的操作：
(1)     比较两个关键字的大小；
(2)     改变指向记录的指针或移动记录本身。
注意：第(2)种基本操作的实现依赖于待排序记录的存储方式。
（3）       排序算法性能评价
1.       评价排序算法好坏的标准
评价排序算法好坏的标准主要有两条：
1)        执行时间和所需的辅助空间
2)        算法本身的复杂程度
2.       排序算法的空间复杂度
若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。非就地排序一般要求的辅助空间为O(n)。
3.       排序算法的时间开销
大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。
 
l         插入排序
一)    直接插入排序
定义：直接插入排序（ straight insertion sort ）是一种最简单的排序方法。它的基本操作是将一个记录插入到一个长度为 m （假设）的有序表中，使之仍保持有序，从而得到一个新的长度为m＋1的有序表。
算法思路：设有一组关键字｛ K 1 ， K 2 ，…， K n ｝；排序开始就认为 K 1 是一个有序序列；让 K 2 插入上述表长为 1 的有序序列，使之成为一个表长为 2 的有序序列；然后让 K 3 插入上述表长为 2 的有序序列，使之成为一个表长为 3 的有序序列；依次类推，最后让 K n 插入上述表长为 n-1 的有序序列，得一个表长为 n 的有序序列。
算法时间复杂度：此算法外循环 n-1 次，在一般情况下内循环平均比较次数的数量级为Ｏ(n) ，所以算法总时间复杂度为Ｏ(n2) 。

直接插入排序的稳定性：直接插入排序是稳定的排序方法
具体算法：
/* 比较数据函数模板 */ 
template<class Type>
typedef bool __stdcall (*PFunCustomCompare)(const Type *Data_1,const Type *Data_2);
template<class Type>
void InsertSort (Type Array[], int n, PFunCustomCompare pfCompare){
int i,j;
for (i=2 ;i<=n; i++){          //工进行n-1趟插入
Array[0] = Array[i];    // Array[0]为监视哨，也可作下边循环结束标志
j = i-1;
while (pfCompare (Array[j], Array[0]){
Array[j+1] = Array[j];
j--;
}
Array [j+1]= Array [0];        //将r[0]即原r[i]记录内容，插到r[j]后一位置
}
}    // InsertSort
或者：不需要监视哨
template<class Type>
void __stdcall InsertSort(Type Array[], int Num, PFunCusomCompare pfCompare){
for (int i=1; i<Num; ++i){
Type temp = Array[i];
int j;
for (j=i-1; j>=0 && pfCompare (t, Array[j]); --j){
Array[j+1] = Array[j];
}
Array[j+1] = temp;
}
}
【例】设有一组关键字序列｛55，22，44，11，33｝，这里 n=5，即有5个记录。请将其按由小到大的顺序排序。排序过程如图9.1所示。
第一趟：[55]  22   44   11    33
第二趟：[22   55]  44   11    33
第三趟：[22   44   55]  11    33
第四趟：[11   22   44   55]   33 
第五趟：[11   22   33   44   55]
二)    折半插入排序
定义：当直接插入排序进行到某一趟时，对于 r[i].key 来讲，前边 i-1 个记录已经按关键字有序。此时不用直接插入排序的方法，而改为折半查找，找出 r[i].key 应插的位置，然后插入。这种方法就是折半插入排序（ Binary insertion sort ）。
具体算法：
template<class T>
void BinarySort(T r[],int n){ 
int i,j,l,h,mid;
for (i=2; i<=n; i++){ 
r[0]=r[i];
l=1;
h=i-1;           //认为在r[1]和r[i-1]之间已经有序
while (l<=h) {          //对有序表进行折半查找
mid=(l+h)/2;
if(a[0].key<a[mid].key){
h=mid-1;
}else{
l=mid+1;
}
}

//结果在1位置
for(j=i-1;j>=1;j--){
a[j+1]=a[j];
}
a[1]=a[0];
}
}  // BinarySort
折半插入排序的时间复杂度：折半插入排序，关键字的比较次数由于采用了折半查找而减少，数量级为Ｏ (nlog 2 n) ，但是元素移动次数仍为Ｏ (n 2 ) 。故折半插入排序时间复杂度仍为Ｏ (n 2 ) 。折半插入排序方法是稳定的。
三)    2-路插入排序
 
四)    表插入排序
 
五)    希尔排序
定义：希尔排序（ shell sort ）是 D ．Ｌ．希尔（ D.L.Shell ）提出的“缩小增量”的排序方法。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。
算法思路：
①.         先取一个正整数 d1(d 1 <;n) ，把全部记录分成 d1个组，所有距离为 d1的倍数的记录看成一组，然后在各组内进行插入排序；
②.         然后取 d2( d2 < d1 ) 。
③.         重复上述分组和排序操作；直到取 di=1(i>=1) ，即所有记录成为一个组为止。一般选 d1约为 n/2，d2为 d 1 /2，d3为 d 2 /2，…，d i =1 。
具体算法：
/* 比较数据函数模板 */ 
template<class Type>
typedef bool __stdcall (*PFunCustomCompare)(const Type *Data_1,const Type *Data_2);
template <class Type>
void __stdcall ShellSort(Type Array[], int Num, PFunCusomCompare pfCompare){
d = Num;
do{
d = d/2;//一般增量设置为数组元素个数，不断除以2以取小
for (int i=d+1; i<=Num; ++i){
if (pfCompare(Array[i], Array[i-d])){
Type temp = Array[i];
for (int j=i-d; j>0 && fpCompare(temp, Array[j]); j=j-d){
Array[j-d] = Array[j];    
}
Array[j+d] = temp;
}
}
}while (d>1);
}

【例】有一组关键字｛ 76 ， 81 ， 60 ， 22 ， 98 ， 33 ， 12 ， 79 ｝，将其按由小到大的顺序排序。这里 n=8 ，取 d 1 =4 ， d 2 =2 ， d 3 =1 。排序过程如图9.2所示。
l         交换排序
交换排序主要是根据记录的关键字的大小，将记录交换来进行排序的。交换排序的特点是：将关键字值较大的记录向序列的后部移动，关键字较小的记录向前移动。这里介绍两种交换排序方法，它们是冒泡排序和快速排序。
一)  冒泡排序
将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
1.算法思路
(1)让j取n至2，将r[j].key与r[j-1].key比较，如果r[j].key<r[j-1].key，则把记录r[j]与r[j-1]交换位置，否则不进行交换。最后是r[2].key与r[1].key对比，关键字较小的记录就换到r[1]的位置上，到此第一趟结束。最小关键字的记录就象最轻的气泡冒到顶部一样换到了文件的前边。
(2)让j取n至3，重复上述的比较对换操作，最终r[2]之中存放的是剩余n-1个记录(r[1]除外)中关键字最小的记录。
(3) 让j取n至i+1，经过一系列对联对比交换之后，r[i]之中是剩余若干记录中关键字最小的记录。
(4) 让j取n至n-1，将r[n].key与r[n-1].key对比，把关键字较小的记录交换到r[n-1]之中。
【例】设有一组关键字序列｛ 55 ， 22 ， 44 ， 11 ， 33 ｝，这里 n=5 ，即有 5 个记录。请将其按由小到大的顺序排序。 如图9.3
具体算法
template<class Type>
BubbleSort(Type Array[], int n){
int t=1,tag,j;T x;
do{ 
tag=0;
for(j=n;j>=i;j--)
if(r[j].key<r[j-1].key){x=r[j];r[j]=r[j-1];
r[j-1]=x;tag=1;
}
i++;
}while(tag==1&&i<i<=n);
} // BubbleSort
算法时间复杂度：该算法的时间复杂度为O(n2)。但是，当原始关键字序列已有序时，只进行一趟比较就结束，此时时间复杂度为O(n)。
二)  快速排序
快速排序由霍尔 (Hoare) 提出，它是一种对冒泡排序的改正。由于其排序速度快，故称快速排序 (quick sort) 。快速排序方法的实质是将一组关键字 [K 1 ,K 2 ,…,K n ] 进行分区交换排序。 
算法思路
①      以第一个关键字 K 1 为控制字，将 [K 1 ,K 2 ,…,K n ] 分成两个子区，使左区所有关键字小于等于 K 1 ，右区所有关键字大于等于 K 1 ，最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。 
②     将右区首、尾指针 ( 记录的下标号 ) 保存入栈，对左区进行与第①步相类似的处理，又得到它的左子区和右子区，控制字居中。 

③     重复第①、②步，直到左区处理完毕。然后退栈对一个个右子区进行相类似的处理，直到栈空。 
由以上三步可以看出：快速排序算法总框架是进行多趟的分区处理；而对某一特定子区，则应把它看成又是一个待排序的文件，控制字总是取子区中第一个记录的关键字。现在设计一个函数 hoare ，它仅对某一待排序文件进行左、右子区的划分，使控制字居中；再设计一个主体框架函数 quicksort ，在这里多次调用 hoare 函数以实现对整个文件的排序。 
快速排序算法分析
快速排序的非递归算法引用了辅助栈，它的深度为 log2n 。假设每一次分区处理所得的两个子区长度相近，那么可入栈的子区长度分别为：n/21n/22，n/23 ，n/24 , … ，n/2k ，又因为 n/2k=1, 所以 k= log2n 。分母中 2 的指数恰好反映出需要入栈的子区个数，它就是 log2n ，也即栈的深度。在最坏情况下，比如原文件关键字已经有序，每次分区处理仅能得到一个子区。可入的子区个数接近 n, 此时栈的最大深度为 n. 
快速排序主体算法时间运算量约 O(log2n) ，划分子区函数运算量约 O(n) ，所以总的时间复杂度为 O(nlog2n) ，它显然优于冒泡排序 O(n2). 可是算法的优势并不是绝对的。试分析，当原文件关键字有序时，快速排序时间复杂度是 O(n2), 这种情况下快速排序不快。而这种情况的冒泡排序是 O(n), 反而很快。在原文件记录关键字无序时的多种排序方法中，快速排序被认为是最好的一种排序方法。
【例】: 试用 [6,7,5 1 ,2,5 2 ,8] 进行快速排序。
排序过程简述如下：
6    7   51   2   52  8      初始状态
[52   7   51]  6  [7   8] 
[2]  52  [51]  6   7  [8] 
[2   52   51   6   7   8]     最后状态 
从这个例子可以分析出快速排序法的稳定性问题，其中51和52表示两个关键字的值相同，都是5。51表示排序之前它位于 52的前面。从结果中可以看出原先位于51之后的52在排序之后移到了51的前面，所以说快速排序是不稳定的。
具体算法：
template <class Type>
void __stdcall QuickSort(Type Array[], int Num, PFunCusomCompare pfCompare, PFunCusomSwap pfSwap){
int left = 0; 
int right = Num-1;
do{
int i=left,j=right; 
Type MidData = Array[(left+right)/2];
do{
while (fpCompare (MidData, Array[i]) && i<right){//从左扫描大于中值的数
++i;
}
while (fpCompare (Array[j], MidData) && j>left){//从右扫描大于中值的数
--j;
}
if (i<=j){
pfSwap(Array[i], Array[j]);//交换数据
++i;
--j;
}
}while (i<=j);//如果两边扫描的下标交错，就停止（完成一次）
if (left<j){//当左边部分有值(left<j)，递归左半边
left = left;

right = j;
}
if (right>i){//当右边部分有值(right>i)，递归右半边 
left = i;
right = right;
} 
}while(left<=right);
}
l         选择排序
选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。
一)   简单选择排序
简单选择排序(simple selection sort)也是直接选择排序。此方法在一些高级语言课程中做过介绍，是一种较为容易理解的方法。
算法思想：对于一组关键字{K1,K2,…,Kn}，首先从K1,K2,…,Kn中选择最小值，假如它是 Kz，则将Kz与 K1对换；然后从K2，K3，… ，Kn中选择最小值 Kz，再将Kz与K2对换。如此进行选择和调换n-2趟，第(n-1)趟，从Kn-1、Kn中选择最小值 Kz将Kz与Kn-1对换，最后剩下的就是该序列中的最大值，一个由小到大的有序序列就这样形成。即：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
选择排序是不稳定的。该算法的时间复杂度为 O(n2)。并且排序是稳定的。
具体算法：
/* 比较数据函数模板 */ 
template<class Type>
typedef bool __stdcall (*PFunCustomCompare)(const Type *Data_1,const Type *Data_2); 
/* 交换数据函数模板 */ 
template<class Type> 
typedef void __stdcall (*PFunCusomSwap)(const Type *Data_1,const Type *Data_2);    
template<class Type>
void __stdcall SelectSort(Type Array[], int Num, PFunCusomCompare pfCompare,　PFunCusomSwap pfSwap){
for (int i=0; i<Num-1; ++i){//从i~n-1中选择要选的数据
for (int j=i+1; j<Num; ++j){
if (pfCompare (Array[j], Array[i])){
pfSwap(Array[j],Array[min])
break;
}
}
}
}

出自：恋宇思涵

【例】图9.6是一个有5个关键字{3,4,1,5,2}的简单选择排序过程的示意图。
  
二)    堆排序
定义：树形选择排序(锦标赛排序)，1964年威洛姆斯(J.Willioms)提出了进一步改正的排序方法，即堆排序(heap sort)。
堆是n个元素的有限序列{ K1,K2,…,Kn }，它当且仅当满足如下关系：
           这是一个上小、底大的堆。若是一个上大、底小的堆，只需把“ <= ”改为“ >= ”即可。堆是一种数据元素之间的逻辑关系，常用向量做存储结构。对于满二叉树，当对它的结点由上而下，自左至右编号之后，编号为 i 的结点是编号为 2i 和 2i+1 结点的双亲。反过来讲，结点 2i 是结点 i 的左孩子，结点 2i+1 是结点 i 的右孩子。图 9.7 表示完全二叉树和它在向量中的存储状态。结点编号对应向量中的下标号。 用堆的概念分析向量中的数据，它显然满足（上小、底大）堆的关系。不难看出满足堆的逻辑关系的一组数据，可画成二叉树的形状，并且它是一棵完全二叉树树形。因此，也可借助完全二叉树来描述堆的概念。若完全二叉树中任一非叶子结点的值小于等于（或大于等于）其左、右孩子结点的值，则从根结点开始按结点编号排列所得的结点序列就是一个堆。在图 9.8 中 (a) 、 (c) 是堆， (b) 、 (d) 不是堆。
堆排序的算法思想：堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
（1）用大根堆排序的基本思想
①.   先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
②.   再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
③.   由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
④.   ……
⑤.   直到无序区只有一个元素为止。
（2）大根堆排序算法的基本操作：
①     初始化操作：将R[1..n]构造为初始堆；
②     每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
注意：
①     只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
②     用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
.具体算法：
建堆(BuildHeap)和堆化(Heapify)函数的实现
因为构造初始堆必须使用到调整堆的操作，先讨论Heapify的实现。 

Heapify函数思想方法：每趟排序开始前R[l..i]是以R[1]为根的堆，在R[1]与R交换后，新的无序区R[1..i-1]中只有R[1]的值发生了变化，故除R[1]可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是R[low..high]时，只须调整以R[low]为根的树即可。"筛选法"调整堆 R[low]的左、右子树(若存在)均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆性质，以R[low]为根的树已是堆，无须调整；否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key，R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为"筛选法"。 
BuildHeap的实现
要将初始文件R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。显然只有一个结点的树是堆，而在完全二叉树中，所有序号大于n/2的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为n/2，…，1的结点作为根的子树都调整为堆即可。
//--------------------------------------------------------------------------------------
template <class type> static void HeapIfy (type *arry, int size, int index);
template <class type> inline static void BuildHeap (type *arry, int size); 
template <class type> static void HeapSort (type *arry, int size); 
//--------------------------------------------------------------------------------------
template <class type> 
static void HeapSort (type *arry, int size){
if (size<=1)｛
return;
｝
BuildHeap (arry, size);
int count = size;
while (count>=2){
type temp = arry[count-1];
arry[count-1] = arry[0];
arry[0] = temp;
count--;
BuildHeap (arry, count);
} 
} 
//--------------------------------------------------------------------------------------
template <class type> 
inline static void BuildHeap (type *arry, int size){
#if   _DEBUG
assert (arry && size>0);
#endif
int i = (size-1)/2;
for ( ; i>=0; i--){
HeapIfy (arry, size, i); 
}
} 

template <class type> 
static void HeapIfy (type *arry, int size, int index){ //平衡堆,参数为数组、数组长度、加入的元素下标 
#if  _DEBUG 
assert (arry && size>0 && index>=0 && index<size);   
#endif
int m = index; //本身索引 
int l;
int r;
do{
l = m*2+1; //左儿子索引 
r = l+1; //右儿子索引 
if (l>=size){ //无儿子 
return;
}else if (r>=size){ //无右儿子
if (arry[m]>=arry[l]){
return;
}else{
type temp = arry[m];
arry[m] = arry[l];
arry[l] = temp;
return;
} 
if (arry[l]>=arry[r]){
if (arry[m]>=arry[l]){
return;
}
type temp = arry[m];
arry[m] = arry[l];
arry[l] = temp;
m = l;
continue;
}
}else{
if (arry[m]>=arry[r]){
return;
}
type temp = arry[m];
arry[m] = arry[r];
arry[r] = temp;
m = r;
continue;
}
}while (true); 
}
算法时间复杂度：堆排序中 heap 算法的时间复杂度与堆所对应的完全二叉树的树高度 log2n 相关。而 heapsort 中对 heap 的调用数量级为n，所以堆排序的整个时间复杂度为O(nlog2n) 。并且堆排序是不稳定的。
l         归并排序

归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。
两路归并排序算法思路：
①.   把 n 个记录看成 n 个长度为 l 的有序子表；
②.   进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表；
③.   重复第②步直到所有记录归并成一个长度为 n 的有序表为止。
算法实现：此算法的实现不像图示那样简单，现分三步来讨论。首先从宏观上分析，首先让子表表长 L=1 进行处理；不断地使 L=2*L ，进行子表处理，直到 L>=n 为止，把这一过程写成一个主体框架函数 mergesort 。然后对于某确定的子表表长 L ，将 n 个记录分成若干组子表，两两归并，这里显然要循环若干次，把这一步写成一个函数 mergepass ，可由 mergesort 调用。最后再看每一组（一对）子表的归并，其原理是相同的，只是子表表长不同，换句话说，是子表的首记录号与尾记录号不同，把这个归并操作作为核心算法写成函数 merge ，由 mergepass 来调用。
具体算法：
//归并操作
template <class type>
static void Merge (type array[], int p, int q, int r){
int i,k;
int begin1,end1,begin2,end2;
int* temp = (int*)malloc((r-p)*sizeof(int));
begin1 = p;
end1 = q;
begin2 = q+1;
end2 = r;
k = 0;
while (begin1<=end1 && begin2<=end2){
if (array[begin1]<array[begin2]){
temp[k] = array[begin1];  
begin1++;
}else{
temp[k] = array[begin2];  
begin2++;
}
k++;
}
while (begin1<end1){
temp[k++] = array[begin1++];
}
while (begin2<end2){
temp[k++] = array[begin2++];
}
for (i=0; i<(r-p); i++){
array[p+i] = temp;
}
free(temp);
}