常见的排序算法
排序算法 (4)
其他排序
简单选择排序
概念
简单选择排序：就是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换
C实现
void SelectSort(int a[],int len)
{
int i,j,min;
for (i=0;i<len;i++)
{
min=i;
for (j=i+1;j<len;j++)
{
if (a[min]>a[j])
min=j;
}
if (i!=min)
swap(&a[min],&a[i]);
}
}
分析
简单选择排序复杂度分析：它的比较次数一定：n(n-1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现，可见对数据的有序性不敏感。它虽然比较次数多，而对于交换次数而言，当最好的时候，交换为0次，最坏的时候交换次数为n-1次，所以数据交换量却很少，基于时间复杂度是比较与交换次数的总和，因此总的时间复杂度依然为O(n^2)。尽管与冒泡排序算法的时间复杂度相同，但是简单选择排序的性能上还是略优于冒泡排序。
堆排序
概念
首先将待排序列构建为大顶堆(大顶堆：每个结点的值大于或等于其左右孩子结点的值)。此时整个序列的最大值就是堆顶的根结点。将它移走（其实就是讲其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个子序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便得到一个有序序列。
C实现
void HeapAdjust(int a[],int s,int m)
{
int temp,j=0;
temp=a[s];
for ( j=2*s+1; j<m; j=j*2+1 )
{
if (j<m && a[j]<a[j+1])
++j;
if (j<m && temp>=a[j])
break;
a[s]=a[j];
s=j;
}
a[s]=temp;
}
void HeapSort(int a[],int len)
{
int i;
for (i=(len)/2-1;i>=0;i--)
HeapAdjust(a,i,len);
for (i=len-1;i>=1;i--)
{
swap(&a[0],&a[i]);
HeapAdjust(a,0,i-1);
}
}
分析
在构建堆的过程中，因为是完全二叉树从最下层最后边的非终端结点开始构建，将它与其孩子进行比较和若有必要的交换，对于每个非终端结点来说，其中最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。.
在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个结点到根节点的距离为[logi]+1），并且需要取n-1次堆顶记录，因此重建堆的时间复杂度为O(nlogn)。
所以总体来说，堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此无论最好、最坏平均时间复杂度均为O(nlogn)。
归并排序
思想
假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度的长度为1，然而两两归并，得到n/2个长度为2或1的有序子序列；再两两归并,…..,如此重复，直至得到一个长度为n的有序序列为止。
C实现
/*将有序的SR归并到TR中*/
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++) /*对1...m与m+1...n中等长的数组比较大小，并且保存较小元素*/
{
if (SR[i]<SR[j])
TR[k]=SR[i++];
else
TR[k]=SR[j++];
}
if (i<=m) /*将SR[1...m]中多余中的部分添加到TR中*/
{
for (l=0;l<=m-i;l++)
TR[k+l]=SR[i+l];
}
if (j<=n) /*将SR[m+1...n]中多余中的部分添加到TR中*/
{
for (l=0;l<=n-j;l++)
TR[k+l]=SR[j+l];
}
}
/*将SR归并排序为TR1*/
void MSort(int SR[],int TR1[],int s,int t)
{
int m=0;
int TR2[length+1]={0};
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);
}
}
分析
一趟归并需要将SR[0]~SR[n-1]中相邻的长度为h的有序序列进行两两归并。并将结果放到TR[0]~TR[n-1]中，这需要将待排序列中的记录扫描一遍，因此耗费O(n)时间，而由完全二叉树的深度可知，整个归并排序需要进行[log(n)]次，因此，总的时间复杂度为O(nlogn)，而且这是归并排序算法中最好、最坏、平均的时间性能。并且归并排序是一种稳定的排序算法。对数据的有序性不敏感。若数据节点数据量大，那将不适合。但可改造成索引操作，效果将非常出色。
按平均时间将排序分为类：
- (1) 平方阶(O(n2))排序 各类简单排序，例如直接插入、简单选择和冒泡排序；
- (2) 线性对数阶(O(nlog2n))排序 如快速排序、堆排序和归并排序；
- (3) O(n1+§))排序 §是介于0和1之间的常数。希尔排序便是一种；
排序方法的选择
- 因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要
(1)若n较小，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数； 但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。 这两种都是稳定排序算法。
(2)若文件初始状态基本有序(指正序)，
则应选用直接插人、冒泡或随机的快速排序为宜 (这里的随机是指基准取值的随机，原因见上的快速排序分析)； 这里快速排序算法将不稳定。
(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法： 快速排序、堆排序或归并排序序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。
归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。