NYC's Blog 排序算法按照元素所在的位置可以分为内部排序（internal sort）和外部排序（external sort）。这里我们讨论的都是内部排序算法，即整个排序工作都能够在内存中完成。且约定需要排序的数组中元素个数为N。
1. 插入排序
插入排序（insertion sort）是最简单的排序算法之一，其特性如下：
- 插入排序由N-1趟（pass）排序组成；
- 在第P趟，我们将位置P上的元素向左移动到它在前P+1个元素中的正确位置上；
- 对于P=1趟到P=N-1趟，插入排序保证从0到位置P上的元素为已排序状态。
下图显示一个简单的数组在每一趟插入排序后的情况：
插入排序的一种程序实现如下：
void InsertionSort(ElementType A[], int N)
{
unsigned int i, j;
ElementType temp;
for (i = 1; i < N; i++)
{
temp = A[i];
for (j = i; j > 0 && A[j - 1] > temp; j--) // 前j个元素（A[0]~A[j-1])为已排序状态
A[j] = A[j-1];
A[j] = temp;
}
}插入排序的算法复杂度为下界是O（N），上界是O（N2），平均复杂度是O（N2）。
最后附上一个动态图（图片来自网络）：
2. 希尔排序
希尔排序（shellsort）通过比较相距一定间隔的元素来工作；各趟比较所有的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。所以，希尔排序也被称为缩小增量排序（diminishing increment sort）。先看下面一个排序的过程（增量是2）：
希尔排序使用一个序列h1，h2，…，ht，叫做增量序列（increment sequence）。只要h1=1，任何增量序列都是可行的，不过有些增量序列比另外一些好一些。在使用增量hk的一趟排序之后，对于每一个i我们有A[i]≤A[i+hk]；所以相隔hk的元素都被排序，此时称文件是hk-排序（hk-sorted）的。
希尔排序的一种实现如下：
void Shellsort(ElementType A[], int N)
{
unsigned int i, j, increment;
ElementType temp;
for( increment = N/2; increment > 0; increment /= 2)
for( i = increment; i < N; i++)
{
temp = A[i];
for( j = i; j >= increment; j -= increment)
if( temp < A[j - increment] )
A[j] = A[j - increment];
else
break;
A[j] = temp;
}
}希尔排序常用的几个增量序列及其复杂度：
- 希尔建议的序列：ht=N/2（向下取整）和hk=hk+1/2向下取整。上面的算法实现中就使用的是前者。使用该增量时平均复杂度O（N2）。
- Hibbard序列：1,3,7, … , 2k-1。使用该增量的平均时间复杂度为O（N5/4）。
- Sedgewick序列：1,5,19,41, …。该序列中的项是94i-92i+1，或者是4i-3*2i+1。使用该序列的平均复杂度为O(N7/6).
最后附上一张希尔排序的动态图（来自网络）:
3. 归并排序
归并排序（mergesort）：如果N=1，那么只有一个元素需要排序，答案是显然的。否则，递归的将前半部分数据和后半部分数据各自归并排序，得到排序后的两部分数据，然后使用上面描述的合并算法将两部分合并到一起。例如，欲将八元素数组24,13,26,1,2,27,38,15排序，我们递归的将前四个数据和后四个数据分别排序，得到1,13,24,26,2,15,27,38.然后将这两部分合并。最后得到1,2,13,15,24,26,27,38.该算法是经典的分治（divide-and-conquer）策略，它将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段解得到的各个答案修补到一起。
下面的程序是一个归并排序实现的实例：
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;
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++ ];
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 = malloc(N * sizeof(ElementType));
if (TmpArray != NULL)
{
MSort(A, TmpArray, 0, N-1);
free(TmpArray);
}
else
{
printf("No space for tmp array.n");
exit(1);
}
}归并排序的平均时间复杂度为O（NlogN），但是它很难用于主存排序，主要问题在于合并两个排序的表需要线性附加内存，在整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样一些附加的工作，其结果严重放慢了排序的速度。所以对于重要的内存排序应用场景，我们一般选择下面要介绍的快速排序。而归并排序，一般在外部排序算法中会借鉴。
最后附一个归并排序的动态图（来自网络）：
4. 快速排序
快速排序（quicksort）是在实践中最快的已知排序算法，它的平均运行时间是O(Nlog)。该算法之所以快主要是由于非常精炼和高度优化的内部循环。和归并排序一样，快排也是一种分治的递归算法。将数组S排序的基本算法由下列简单的四步组成：
- 如果S中元素个数为0或者1，则返回；
- 取S中任一个元素v，称之为枢纽元（pivot）；
- 将S-{v}（S中其余元素）分成两个不相交的集合：S1={x∈S-{v} | x≤v）和S2={x∈S-{v} | x≥v）；
- 返回{quicksort（S1）后，继随v，继而quicksort（S2）}。
一般快速排序的重点在于枢纽元的选取上，而且不同的选择往往对算法会产生比较大的影响。直观的，我们希望把等于枢纽元大约一半的关键字分到S1中，而另一半分到S2中。而关于如何选择枢纽元也有很多的理论，以后再论述。下面将第一个元素作为枢纽元（这种做法是非常糟糕的，这里仅是为了讲解算法的原理）实现快排算法：
/*
void Qsort(ElementType A[], int Left, int Right)
{
if (Left < Right)
{
int i = Left, j = Right, x = A[Left];
while (i < j)
{
while(i < j && A[j] >= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
A[i++] = A[j];
while(i < j && A[i] < x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
A[j--] = A[i];
}
A[i] = x;
Qsort(A, Left, i - 1); // 递归调用
Qsort(A, i + 1, Right);
}
}
*/
void Qsort(ElementType A[], int Left, int Right)
{
if(Left >= Right)/*如果左边的数组大于或者等于就代表已经整理完成一个组了*/
{
return ;
}
int i = Left;
int j = Right;
int key = A[Left];
while(i < j) /*控制在当组内寻找一遍*/
{
while(i < j && key <= A[j])
/*而寻找结束的条件就是，1，找到一个小余或者大于key的数（大小取决于你想升
序还是降序）2，没有符合的切i与j相遇*/
{
j--;/*向前寻找*/
}
A[i] = A[j];
/*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
A[0]，那么就是给key）*/
while(i < j && key >= A[i])
/*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
{
i++;
}
A[j] = A[i];
}
A[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
Qsort(A, Left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
Qsort(A, i + 1, Right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
/*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}
void Quicksort(ElementType A[], int N)
{
Qsort(A, 0, N-1);
}最后附一张快速排序的图（来自网络）：
5. 完整的程序实例
func.h头文件：
/*
* func.h
*
* Created on: 2015年5月24日
* Author: Allan
*/
#ifndef FUNC_H_
#define FUNC_H_
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
void Display(ElementType A[], int N);
void InsertionSort(ElementType A[], int N);
void Shellsort(ElementType A[], int N);
void MSort(ElementType A[], ElementType TmpArray[], int Left, int Right);
void Mergesort(ElementType A[], int N);
void Merge(ElementType A[], ElementType TmpArray[], int Lpos, int Rpos,
int RightEnd);
void Swap(ElementType *a, ElementType *b);
ElementType Median3(ElementType A[], int Left, int Right);
void LiteQsort(ElementType A[], int Left, int Right);
#define Cutoff (3)
void Qsort(ElementType A[], int Left, int Right);
void Quicksort(ElementType A[], int N);
#endif /* FUNC_H_ */func.c源文件：
/*
* func.c
*
* Created on: 2015年5月24日
* Author: Allan
*/
#include "func.h"
/*
* 显示一个数组
*/
void Display(ElementType A[], int N)
{
int i;
for(i = 0; i < N; i++)
printf("%dt", A[i]);
printf("n");
}
/*
* 插入排序
*/
void InsertionSort(ElementType A[], int N)
{
unsigned int i, j;
ElementType temp;
for (i = 1; i < N; i++)
{
temp = A[i];
for (j = i; j > 0 && A[j - 1] > temp; j--) // 前j个元素（A[0]~A[j-1])为已排序状态
A[j] = A[j-1];
A[j] = temp;
printf("%d pass: ", i);
Display(A, N);
}
}
/*
* 希尔排序
*/
void Shellsort(ElementType A[], int N)
{
unsigned int i, j, increment;
ElementType temp;
for( increment = N/2; increment > 0; increment /= 2)
{
for( i = increment; i < N; i++)
{
temp = A[i];
for( j = i; j >= increment; j -= increment)
if( temp < A[j - increment] )
A[j] = A[j - increment];
else
break;
A[j] = temp;
}
printf("%d-pass: ", increment);
Display(A, 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;
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++ ];
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 = malloc(N * sizeof(ElementType));
if (TmpArray != NULL)
{
MSort(A, TmpArray, 0, N-1);
free(TmpArray);
}
else
{
printf("No space for tmp array.n");
exit(1);
}
}
/*
* 快速排序
*/
/*
void Qsort(ElementType A[], int Left, int Right)
{
if (Left < Right)
{
int i = Left, j = Right, x = A[Left];
while (i < j)
{
while(i < j && A[j] >= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
A[i++] = A[j];
while(i < j && A[i] < x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
A[j--] = A[i];
}
A[i] = x;
Qsort(A, Left, i - 1); // 递归调用
Qsort(A, i + 1, Right);
}
}
*/
void Qsort(ElementType A[], int Left, int Right)
{
if(Left >= Right)/*如果左边的数组大于或者等于就代表已经整理完成一个组了*/
{
return ;
}
int i = Left;
int j = Right;
int key = A[Left];
while(i < j) /*控制在当组内寻找一遍*/
{
while(i < j && key <= A[j])
/*而寻找结束的条件就是，1，找到一个小余或者大于key的数（大小取决于你想升
序还是降序）2，没有符合的切i与j相遇*/
{
j--;/*向前寻找*/
}
A[i] = A[j];
/*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
A[0]，那么就是给key）*/
while(i < j && key >= A[i])
/*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
{
i++;
}
A[j] = A[i];
}
A[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
Qsort(A, Left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
Qsort(A, i + 1, Right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
/*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}
void Quicksort(ElementType A[], int N)
{
Qsort(A, 0, N-1);
}main.c文件：
/*
* main.c
*
* Created on: 2015年5月24日
* Author: Allan
*/
#include "func.h"
int main()
{
unsigned int i, j;
ElementType isa[] =
{ 34, 8, 64, 51, 32, 21 };
puts("Insertion Sort:");
InsertionSort(isa, 6);
Display(isa, 6);
ElementType ssa[] =
{ 81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15 };
puts("nShell sort:");
Shellsort(ssa, 13);
Display(ssa, 13);
ElementType msa[] =
{ 24, 13, 26, 1, 2, 27, 38, 15 };
puts("nMerge sort:");
Mergesort(msa, 8);
Display(msa, 8);
ElementType qsa[] =
{ 8, 1, 4, 9, 6, 3, 5, 2, 7, 0 };
puts("nQuick sort:");
Quicksort(qsa, 10);
Display(qsa, 10);
return 0;
}运行结果如下：
Insertion Sort:
1 pass: 8 34 64 51 32 21
2 pass: 8 34 64 51 32 21
3 pass: 8 34 51 64 32 21
4 pass: 8 32 34 51 64 21
5 pass: 8 21 32 34 51 64
8 21 32 34 51 64
Shell sort:
6-pass: 15 94 11 58 12 35 17 95 28 96 41 75 81
3-pass: 15 12 11 17 41 28 58 94 35 81 95 75 96
1-pass: 11 12 15 17 28 35 41 58 75 81 94 95 96
11 12 15 17 28 35 41 58 75 81 94 95 96
Merge sort:
1 2 13 15 24 26 27 38
Quick sort:
0 1 2 3 4 5 6 7 8 9
评论已关闭