各种排序方法的综合比较
结论:
排序方法 平均时间 最坏时间 辅助存储
简单排序 O(n2) O(n2) O(1)
快速排序 O(nlogn) O(n2) O(logn)
堆排序 O(nlogn) O(nlogn) O(1)
归并排序 O(nlogn) O(nlogn) O(n)
基数排序 O(d(n+rd)) O(d(n+rd)) O(rd)
另外:直接插入排序、冒泡排序为简单排序，希尔排序（不稳定）
一、时间性能
按平均的时间性能来分，有三类排序方法：
时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最
好；
时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为
最好，特别是对那些对关键字近似有序的记录序列尤为如此；
时间复杂度为O(n)的排序方法只有，基数排序。
当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂
度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应
该尽量避免的情况。
简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
二、空间性能
指的是排序过程中所需的辅助空间大小。
1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O
(1)；
2. 快速排序为O(logn )，为栈所需的辅助空间;
3. 归并排序所需辅助空间最多，其空间复杂度为O(n );
4.链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。
三、排序方法的稳定性能
1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在
排序之前和经过排序之后，没有改变。
2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。
3. 对于不稳定的排序方法，只要能举出一个实例说明即可。
4. 快速排序和堆排序是不稳定的排序方法
#include <stdio.h>
#include <stdlib.h>
void ss_sort(int e[],int n)
{
int i,j,k,t;
for (i=0;i<n-1;i++) {
for (k=i,j=i+1;j<n;j++)
if (e[k]>e[j]) k=j;
if (k!=i) {
t=e[i]; e[i]=e[k]; e[k]=t;
}
}
}
void si_sort(int e[],int n)
{
int i,j,t;
for (i=1;i<n;i++)
{
for (t=e[i],j=i-1;j>=0 && t<e[j];j--)
e[j+1]=e[j];
e[j+1]=t;
}
}
void sb_sort(int e[],int n)
{
int j,p,h,t;
for (h=n-1;h>0;h=p)
{
for (p=j=0;j<h;j++)
if (e[j]>e[j+1]) {
t=e[j];
e[j]=e[j+1];
e[j+1]=t;
p=j;
}
}
}
void shell(int e[],int n)
{
int j,k,h,y;
for (h=n/2;h>0;h=h/2)
for (j=h;j<n;j++) {
y=e[j];
for (k=j-h;k>=0&&y<e[k];k-=h)
e[k+h]=e[k];
e[k+h]=y;
}
}
void sift(int e[],int n,int s)
{
int t,k,j;
t=e[s];
k=s; j=2*k+1;
while (j<n) {
if (j<n-1&&e[j]<e[j+1])
j++;
if (t<e[j]) {
e[k]=e[j];
k=j;
j=2*k+1;
}
else
break;
}
e[k]=t;
}
void heapsort(int e[],int n)
{
int i,k,t;
for (i=n/2-1;i>=0;i--)
sift(e,n,i);
for (k=n-1;k>=1;k--) {
t=e[0];
e[0]=e[k];
e[k]=t;
sift(e,k,0);
}
}
void r_quick(int e[],int low,int high)
{
int i,j,t;
if (low<high) {
i=low; j=high; t=e[low];
while (i<j) {
while (i<j && e[j]>t) j--;
if (i<j) e[i++]=e[j];
while (i<j && e[i]<=t)i++;
if (i<j) e[j--]=e[i];
}
e[i]=t;
r_quick(e,low,i-1);
r_quick(e,i+1,high);
}
}
void merge_step(int e[],int a[],int s,int m,int n)
{
int i,j,k;
k=i=s; j=m+1;
while (i<=m && j<=n)
if (e[i]<=e[j]) a[k++]=e[i++];
else a[k++]=e[j++];
while (i<=m) a[k++]=e[i++];
while (j<=n) a[k++]=e[j++];
}
void merge_pass(int e[],int a[],int n,int len)
{
int f_s,s_end;
f_s=0;
while (f_s+len<n) {
s_end=f_s+2*len-1;
if (s_end>=n) s_end=n-1;
merge_step(e,a,f_s,f_s+len-1,s_end);
f_s=s_end+1;
}
if (f_s<n)
for (;f_s<n;f_s++)
a[f_s]=e[f_s];
}
void merge(int e[],int n)
{
int *p=(int *)malloc(sizeof(int)*n);
int len=1,f=0;
while (len<n) {
if (f==0) merge_pass(e,p,n,len);
else merge_pass(p,e,n,len);
len *=2;
f=1-f;
}
if (f)
for (f=0;f<n;f++) e[f]=p[f];
free(p);
}
int main(int argc, char *argv[])
{
int a[8]={4,6,2,1,3,9,10,5},*p,i=0;
ss_sort(a,8);
for (p=a;p<a+8;p++)
printf("%d\n",*p);
printf("\n");
si_sort(a,8);
for (p=a;p<a+8;p++)
printf("%d\n",*p);
printf("\n");
sb_sort(a,8);
for (p=a;p<a+8;p++)
printf("%d\n",*p);
printf("\n");
shell(a,8);
for (p=a;p<a+8;p++)
printf("%d\n",*p);
printf("\n");
heapsort(a,8);
for (p=a;p<a+8;p++)
printf("%d\n",*p);
printf("\n");
r_quick(a,0,7);
for (p=a;p<a+8;p++)
printf("%d\n",*p);
printf("\n");
merge(a,8);
for (p=a;p<a+8;p++)
printf("%d\n",*p);
printf("\n");
system("PAUSE");
return 0;
}
