- 背景介绍
- 排序
- 冒泡排序
- 简单选择排序
- 直接插入排序
- 希尔排序
- 堆排序
- 归并排序
- 非递归实现归并排序
- 快速排序
- 快速排序优化
最近重新看了一遍查找的相关算法，在这里进行一些总结。另外提醒读者，看文章时，一定首重思路，搞清楚思路，至于代码，不过是思路的具体化而已。
排序定义：使序列成为按关键字有序的序列，这样的操作称为排序。
多个关键字可以转化为单个关键字的排序，因此在这里我们主要讨论单个关键字的排序。
排序的稳定性：假设在原始序列中任意两个数据元素ri在rj前，且排序过程中ri=rj,排序后ri依旧在rj前，则该排序是稳定的，否则该排序是不稳定的
排序算法的性能
- 时间性能：尽可能减少关键字的比较次数和记录的移动次数。排序算法基本都是围绕这一点设计的
- 辅助空间：除了待排序数据元素本身占用的存储空间之外，执行算法所需要的其他存储空间。
- 算法的复杂度：算法本身的复杂度。
本文主要讲解七种排序算法：
- 冒泡排序
- 简单选择排序
- 直接插入排序
- 希尔排序
- 堆排序
- 归并排序
- 快速排序
前提
排序用到的数据结构：
typedef int Status;
#define MAXSIZE 10000
typedef struct
{
int r[MAXSIZE+1];
int length;
}SqList;
void swap(SqList *L,int i,int j)
{
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}
void print(SqList L)
{
int i;
for(i=1;i
PS：数组为r[MAXSIZE+1]， 用于存储要排序数组，r[0]用作哨兵或临时变量
冒泡排序
定义：冒泡排序的是一种交换排序，它的基本思想是，两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
代码如下：
void BubbleSort(SqList *L)
{
int i,j;
for(i=1;ilength;i++)
{
for(j=L->length-1;j>=i;j--)
{
if(L->r[j]>L->r[j+1])
{
swap(L,j,j+1);
}
}
}
}
冒泡排序改进版：
void BubbleSort2(SqList *L)
{
int i,j;
Status flag=TRUE;
for(i=1;ilength && flag;i++)
{
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;
}
}
}
}
PS： 在改进版中增加了一个flag向量，当j的for循环中不再交换数据，则证明序列已经有序，则令flag为false，打破i的for循环。
复杂度分析为O（n2）
简单选择排序
选择排序的思路：每一趟在n-i+1(i=1,2…n-1)个关键字中选取关键字最小的记录作为有序排列的第i个记录。
简单选择排序的思路：每一趟通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，将它与第i个记录交换。
代码如下：
void SelectSort(SqList *L)
{
int i,j,min;
for(i=1;ilength;i++)
{
min = i;
for (j = i+1;j<=L->length;j++)
{
if (L->r[min]>L->r[j])
min = j;
}
if(i!=min)
swap(L,i,min);
}
}
时间复杂度为O（n2）,但需要移动的次数较少，所以它的性能较优于冒泡排序
直接插入排序
思路：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
代码如下：
void InsertSort(SqList *L)
{
int i,j;
for(i=2;i<=L->length;i++)
{
if (L->r[i]r[i-1])
{
L->r[0]=L->r[i];
for(j=i-1;L->r[j]>L->r[0];j--)
L->r[j+1]=L->r[j];
L->r[j+1]=L->r[0];
}
}
}
时间复杂度为O（n2），只需要一个记录的辅助空间。平均比较和移动次数约为n2/4，由此看出直接插入排序的性能比冒泡排序和简单选择排序要好一些
希尔排序
直接插入排序在某些时候的效率是很高的，比如序列中记录本身是基本有序的，或者记录数较少的时候，直接插入的优势也很明显，希尔排序就是在这个基础上对直接插入排序的改进版。
思路：将序列分割成若干个子序列，在各个子序列中进行直接插入排序当整个序列都基本有序时，对整体进行一个直接插入排序。
注意：基本有序指整个序列中，最小的关键字基本在前面，大的基本在后面，不大不小的基本在中间。因此怎样使整个序列可以基本有序，是希尔排序的关键。
跳跃分割：将相距某个“增量”的记录组成一个子序列，这样才能保证子序列内分别进行的直接插入排序得到的结果是基本有序而不是局部有序。
需要注意的是：增量序列的最后一个增量值必须等于1才行，当增量值为1时，其实就是对整个序列进行一个直接插入排序。
时间复杂度为O（n3/2）,突破了O（n2）的限制。
看了一篇文章，觉得对希尔排序写的很详细，附上链接。
理解希尔排序的排序过程
堆排序
堆：堆是具有以下性质的完全二叉树，每个结点的值都大于或等于其左右孩子的值，称为大顶堆，每个结点的值都小于或等于其左右孩子的值，称为小顶堆。
PS：可以看出堆允许出现相同的结点。
堆排序：将待排序的序列构造成一个大顶堆，此时根节点为最大值，移去跟结点，使剩下的n-1个结点仍为大顶堆，重复该操作，直到树为空，此时得到一个有序序列。
分两步，第一将待排序序列构造成大顶堆，第二步将最大值与末尾结点交换（保持该树为完全二叉树），调整其为大顶堆。
代码如下：
void HeapSort(SqList *L)
{
int i;
for(i=L->length/2;i>0;i--)
HeapAdjust(L,i,L->length);
for(i=L->length;i>1;i--)
{
swap(L,1,i);
HeapAdjust(L,1,i-1);
}
}
可以看出整个排序过程分为两个for循环，第一个循环要完成的就是将现在的待排序序列构造成大顶堆，第二个循环要完成的是将根节点跟末尾元素交换，并且调整树为大顶堆。
将排序序列构造成大顶堆，本质上就是从下往上，从右往左，将每个非终端结点当做根节点，将它和它的子树调整为大顶堆。
void HeapAdjust(SqList *L,int s,int m)
{
int temp,j;
temp=L->r[s];
for(j=2*s;j<=m;j*=2)
{
if(jr[j]r[j+1])
++j;
if(temp>=L->r[j])
break;
L->r[s]=L->r[j];
s=j;
}
L->r[s]=temp;
}
时间复杂度：堆排序的时间消耗主要在于初始构建堆和重构堆时的反复筛选上，对于每个非终端结点而言，其实最多只进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)，重建堆的比较次数为O(n logn)，总体而言，堆排序的时间复杂度为O(n logn)。
注意：初始构建堆所需要的比较次数较多，因此不适合待排序序列个数较少的情况。
归并排序
定义：假设初始序列中含有n个记录，将它看成n个有序的子序列，每个子序列长度为1，两两归并，形成⌈n/2⌉个长度为2或1的子序列，重复该操作，直到得到一个长度为n的有序序列为止，这种方法称为2路归并排序。
思路：先将待排序序列折半分组，重复该操作，直到每个组长度为1，再两两归并，重复该操作，直到得到一个长度为n的有序序列为止。
代码如下：
void MergeSort(SqList *L)
{
MSort(L->r,L->r,1,L->length);
}
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;
MSort(SR,TR2,s,m);
MSort(SR,TR2,m+1,t);
Merge(TR2,TR1,s,m,t);
}
}
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++)
{
if (SR[i]
复杂度分析：从时间上看，每趟归并需要扫描一遍SR[1]~SR[n]，耗费O(n)，由完全二叉树深度可知，需要进行O(logn)轮，因此时间复杂度为O(nlogn)，
需要额外的一个序列去存储排序后的结果，所占空间是n，因此空间复杂度为O(n)。另外，归并排序是一种稳定的排序方法。
非递归实现归并排序
在思路上，可以尽可能的使用递归，清晰思路，但实际编程中，递归会不断的申请函数调用的栈空间，造成时间和空间上的性能损耗，甚至是栈溢出，而循环迭代整个就在主函数的或者在调用函数的栈空间里面，在循环的次数较大的时候，迭代的效率明显高于递归，因此应该尽可能的将递归转换成迭代。
思路：用额外的数量相同的数组A，不需要拆分成n个长度为1的子序列，直接视序列中每个元素为长度为1 的子序列，进行合并到数组A中 ，再视数组A中全是长度为2或1的子序列，进行合并到原数组中，重复操作，直到合并成功。
代码如下：
void MergeSort2(SqList *L)
{
int* TR=(int*)malloc(L->length * sizeof(int));
int k=1;
while(klength)
{
MergePass(L->r,TR,k,L->length);
k=2*k;
MergePass(TR,L->r,k,L->length);
k=2*k;
}
}
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
快速排序
定义：通过一趟排序将待排序记录分割成两个独立的部分，其中一部分的所有记录的关键字均比另一部分的关键字要小，对这两部分重复排序操作，直到整个序列有序。
代码如下：
void QuickSort(SqList *L)
{
QSort(L,1,L->length);
}
void QSort(SqList *L,int low,int high)
{
int pivot;
if(low
可以看出，关键的代码是：pivot=Partition(L,low,high)。作用是选取待排序序列中一个关键字，以该关键字为枢轴值，将L->r[low…high]一分为二，左边的都要比枢轴值小，右边的都要比枢轴值大，它的位置称为枢轴pivot。
int Partition(SqList *L,int low,int high)
{
int pivotkey;
pivotkey=L->r[low];
while(lowr[high]>=pivotkey)
high--;
swap(L,low,high);
while(lowr[low]<=pivotkey)
low++;
swap(L,low,high);
}
return low;
}
利用枢轴实现跳跃交换。
复杂度分析：最优时间复杂度O(nlog n)、平均时间复杂度O(nlog n)、最坏时间复杂度O(n2)。最优空间复杂度O(log n)、平均空间复杂度O(log n)、最坏空间复杂度O(n)。
快速排序优化
- 优化选取枢轴：三数取中间值。
代码如下：
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];
- 优化不必要的交换
思路：在之前的方式中，枢轴的位置不断的跟不符合条件的记录相交换，但这种交换实际上是不需要的，因此我们采用替换的方式取代交换的方式。
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;
while(lowr[high]>=pivotkey)
high--;
L->r[low]=L->r[high];
while(lowr[low]<=pivotkey)
low++;
L->r[high]=L->r[low];
}
L->r[low]=L->r[0];
return low;
}
- 优化小数组的排序方案
思路：快速排序用到了递归操作，在大量数据中，所造成的的性能消耗可以忽略，但少量数据中，直接插入排序的效率反而更高，因此可以提供两种方式进行排序，数据量少时，用直接插入排序，数据量大时，用快速排序。
void QSort1(SqList *L,int low,int high)
{
int pivot;
if((high-low)>MAX_LENGTH_INSERT_SORT)
{
pivot=Partition1(L,low,high);
QSort1(L,low,pivot-1);
QSort1(L,pivot+1,high);
}
else
InsertSort(L);
}
- 优化递归操作
思路：减少不必要的递归，将它转换成迭代的方式。本质上效果是一样的，只不过转成迭代的形式，缩减了申请的栈空间的深度，可以提高整体性能。
void QSort2(SqList *L,int low,int high)
{
int pivot;
if((high-low)>MAX_LENGTH_INSERT_SORT)
{
while(low 
