七大内部排序算法小结（插入排序、希尔排序、冒泡排序、简单选择排序、快速排序、归并排序、堆排序）
写在前面：
1、对下面介绍的各个排序进行一下限定，所有排序的关键字都是整数、对传入函数的参数默认是已经检查好了的。只是简单的描述各个算法并给出了具体实现代码，并未做其他深究探讨。
2、下面给出的排序方法都是内部排序。内部排序指的是待排序记录存放在计算机随机存储器中进行的排序过程。另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
算法分析：
1、直接插入排序：
基本思想：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。
时间复杂度为O(n^2)，若待排记录序列为正序，复杂度可提高至O(n)；空间上只需要一个记录的辅助空间。
示例代码1：
void InsertionSort(ElementType A[], int N)
{
int j, P;
ElementType Tmp;
for(P = 1; P < N; P++){
Tmp = A[P];
for(j = P; j > 0 && A[j - 1] > Tmp; j--)
A[j] = A[j - 1];
A[j] = Tmp;
}
}
示例代码2：
void insertionsort(ElementType A[], int N)
{
for(int i = 1; i < N; i++){
int tmp = A[i];
int j = i - 1;
while(j > -1 && A[j] > A[i]){
A[j+1] = A[j];
--j;
}
A[j+1] = tmp;
}
return;
}
插入排序算法简单，且容易实现。当待排序记录的数量n很小时，这是一种很好的排序方法。但n很大时，则不宜采用直接排序。因为直接排序，主要的时间消耗在“比较”和“移动”上，因此，在直接排序的基础上，从减少“比较”和“移动”这两种操作的次数着眼，可得“折半插入排序”、“2-路插入排序”、“表插入排序”等。
2、希尔排序
基本思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
特点：子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。它通过比较相距一定间隔的元素来工作；各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。
示例代码
void Shellsort(ElementType A[], int N)
{
int i, j, Increment;
ElementType Tmp;
for(Increment = N / 2; Increment > 0; Increment /= 2){
for(i = Increment; i < N; i++){
Tmp = A[i];
for(j = i; j >= Increment; j -= Increment){
if(Tmp < A[j - Increment])
A[j] = A[j - Increment];
else
break;
}
A[j] = Tmp;
}
}
}
上面给出的示例中选择的排序增量是使用shell建议的序列：N/2和Increment/2。使用希尔增量时希尔排序的最坏情形运行时间为O(n^2)。
3、冒泡排序
基本思想：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称做第一趟冒泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。一般地，第i趟冒泡排序是从1到n-i+1依次比较相邻两个关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。判别冒泡排序结束的条件应该是“在一趟排序过程中没有进行过交换记录的操作”。
示例代码1：
void bubblesort(ElementType A[], int N)
{
int i, j;
ElementType tmp;
for(i = 0; i < N; i++)
{
for(j = 0; j < N-i; j++){
if(A[j] > A[j+1]){
tmp = A[j];
A[j] = A[j+1];
A[j+1] = tmp;
}
}
}
}
示例代码2：
void bubblesort(ElementType a[], int n)
{
int j;
bool flag;
ElementType tmp;
flag = true;
while(flag){
flag = false;
for(j = 1; j < n; j++){
if(a[j-1] > a[j]){
tmp = a[j-1];
a[j-1] = a[j];
a[j] = tmp;
flag = true;
}
}
n--;
}
}
冒泡排序的时间复杂度为O(n^2)。效率比较底下，当数据量比较小的时候，可以采用冒泡排序。
4、简单选择排序
基本思想：每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接插入排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。
示例代码：
void Selectsort(int a[], int n)
{
int i, j, nMinIndex, tmp;
for(i = 0; i < n; i++){
nMinIndex = i;
for(j = i + 1; j < n; j++)
if(a[j] < a[nMinIndex])
nMinIndex = j;
tmp = a[i];
a[i] = a[nMinIndex];
a[nMinIndex] = tmp;
}
}
简单选择排序的时间复杂度是O(n^2)。
5、快速排序
基本思想：快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有效。
一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于prvotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于privotkey的记录和枢轴记录互相交换，重复这两步直至low=high为止。
示例代码：
void Swap(ElementType *left, ElementType *right)
{
ElementType temp = *left;
*left = *right;
*right = temp;
}
int Partition(ElementType A[], int low, int high)
{
ElementType pivotkey = A[low];
while(low < high){
while(low < high && A[high] >= pivotkey)
high--;
Swap(&A[low], &A[high]);
while(low < high && A[low] <= pivotkey)
low++;
Swap(&A[low], &A[high]);
}
return low;
}
void QSort(ElementType A[], int low, int high)
{
int pivotloc;
if(low < high){
pivotloc = Partition(A, low, high);
QSort(A, low, pivotloc - 1);
QSort(A, pivotloc + 1, high);
}
}
void QuickSort(ElementType A[], int low, int high)
{
QSort(A, low, high);
}
快速排序的平均时间为O(n) = nlogn;它是目前被认为的最好的一种内部排序方法。
6、归并排序
基本思想：将两个或两个以上的有序表组合成一个新的有序表。2-路归并排序为例：假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2（或n/2+1）个长度为2或1的有序子序列；再两两归并，……如此重复，直至得到一个长度为n的有序序列为止。
示例代码：
void Merge(ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int RightEnd)
{
int i, LeftEnd, NumElements, TmpPos;
LeftEnd = Rpos - 1;
TmpPos = Lpos;
NumElements = RightEnd - Lpos + 1;
/*main loop*/
while(Lpos <= LeftEnd && Rpos <= RightEnd)
if(A[Lpos] <= A[Rpos])
TmpArray[TmpPos++] = A[Lpos++];
else
TmpArray[TmpPos++] = A[Rpos++];
while(Lpos <= LeftEnd) /*Copy rest of first half*/
TmpArray[TmpPos++] = A[Lpos++];
while(Rpos <= RightEnd) /*Copy rest of second half*/
TmpArray[TmpPos++] = A[Rpos++];
/*Copy TmpArray back*/
for(i = 0; i < NumElements; i++, RightEnd--)
A[RightEnd] = TmpArray[RightEnd];
}
void MSort(ElementType A[], ElementType TmpArray[], int Left, int Right)
{
int Center;
if(Left < Right){
Center = (Left + Right) / 2;
MSort(A, TmpArray, Left, Center);
MSort(A, TmpArray, Center + 1, Right);
Merge(A, TmpArray, Left, Center + 1, Right);
}
}
void Mergesort(ElementType A[], int N)
{
ElementType *TmpArray;
TmpArray = (ElementType *)malloc(N*sizeof(ElementType));
if(TmpArray == NULL){
fprintf(stderr, "no space for tmp array!\n");
return;
}
MSort(A, TmpArray, 0, N-1);
free(TmpArray);
return;
}
归并排序的效率比较高，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序的数列的过程，时间复杂度记为O(N)，因此时间复杂度是O(N*LogN)。它很难用于主存排序，主要问题在于合并两个排序的表需要线性附加内存，在整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样一些附加的工作，其结果严重放慢了排序的速度。
7、堆排序
堆是具有下列性质的完全二叉树:每个节点的值都大于或等于其左右孩子节点的值,称为大顶堆；或者每个节点的值都小于或等于其左右孩子节点的值,称为小顶堆。
堆排序就是利用堆进行排序的方法.基本思想是:将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶 的根结点.将它移走(其实就是将其与堆数组的末尾元素交换, 此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次大值.如此反复执行,便能得到一个有序序列了。 时间复杂度为 O(nlogn),好于冒泡,简单选择,直接插入的O(n^2)
示例代码：
#define LeftChild(i) (2*(i) + 1)
void Swap(ElementType *pa, ElementType *pb)
{
ElementType *pc = pa;
pa = pb;
pb = pc;
}
void PercDown(ElementType A[], int i, int N)
{
int Child;
ElementType Tmp;
for(Tmp = A[i]; LeftChild(i) < N; i = Child){
Child = LeftChild(i);
if(Child != N-1 && A[Child + 1] > A[Child])
Child++;
if(Tmp < A[Child])
A[i] = A[Child];
else
break;
}
A[i] = Tmp;
}
void Heapsort(ElementType A[], int N)
{
int i;
for(i = N/2; i >= 0; i--) /*BuildHeap*/
PercDown(A, i, N);
for(i = N - 1; i > 0; i--){
Swap(&A[0], &A[i]); /*DeleteMax*/
PercDown(A, 0, i);
}
}
总结：在排序的过程中需进行下列两种基本操作：1、比较两个关键字的大小；2、将记录从一个位置移动至另一个位置。操作1对大多数排序方法来说都是必要的，而操作2可以通过改变记录的存储方式予以避免。