内部排序算法比较

发布网友发布时间：2022-05-05 08:59

共1个回答

热心网友时间：2022-06-27 05:34

按平均时间将排序分为四类：

（1）平方阶(O(n2))排序一般称为简单排序，例如直接插入、直接选择和冒泡排序；

（2）线性对数阶(O(nlgn))排序如快速、堆和归并排序；

（3）O(n1+￡)阶排序￡是介于0和1之间的常数，即0<￡<1，如希尔排序；

（4）线性阶(O(n))排序如桶、箱和基数排序。

各种排序方法比较简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。影响排序效果的因素因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：

①待排序的记录数目n；

②记录的大小(规模)；

③关键字的结构及其初始状态；

④对稳定性的要求；

⑤语言工具的条件；

⑥存储结构；

⑦时间和辅助空间复杂度等。

不同条件下，排序方法的选择

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；

(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

(4)在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlgn)的时间。

百度文库里也有说明，详见：http://wenku.baidu.com/view/51f3b202de80d4d8d15a4fa6.html

下面是一段测试程序：
用系统计时器算时间复杂度。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define LIST_INIT_SIZE 50000
int bj1,yd1,n;
clock_t start_t,end_t;
typedef struct
{
int key;
}ElemType;
typedef struct
{
ElemType *elem;
int length;
}SqList;
void addlist(SqList &L)
{
int i;
a: printf("请输入你要输入的个数:");
scanf("%d",&n);
if(n>50000)
{
printf("超出范围重新输入!!!\n");
goto a;
}
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)exit(0);
L.length=0;
for(i=1;i<n+1;i++)
{
b: L.elem[i].key=rand();
if(L.elem[i].key>30000)goto b;
++L.length;
}
}
void SelectSort(SqList &L)//选择
{
start_t=clock();
int i,j,k,bj=0,yd=0;
for(i=1;i<L.length;i++)
{
k=i;
for(j=i+1;j<L.length;j++)
{
bj++;
if(L.elem[j].key<L.elem[k].key)k=j;
}
if(i!=k)
{
L.elem[0].key=L.elem[i].key;
L.elem[i].key=L.elem[k].key;
L.elem[k].key=L.elem[0].key;
yd+=3;
}
}
end_t=clock();
printf("比较次数为 %d移动次数为 %d\n",bj,yd);
printf("排序用时为 %f\n",float(end_t-start_t)/CLK_TCK);
}
void qipao(SqList &L)//起泡
{
start_t=clock();
int i=1,j,bj=0,yd=0;
while(i<L.length)
{
for(j=1;j<L.length;j++)
{
bj++;
if(L.elem[j].key>L.elem[j+1].key)
{
L.elem[0].key=L.elem[j].key;
L.elem[j].key=L.elem[j+1].key;
L.elem[j+1].key=L.elem[0].key;
yd+=3;
}
}
i++;
}
end_t=clock();
printf("比较次数为 %d移动次数为 %d\n",bj,yd);
printf("排序用时为 %f\n",float(end_t-start_t)/CLK_TCK);
}
void InsertSort(SqList &L)//直接插入
{
start_t=clock();
int i,j,yd=0,bj=0;
for(i=2;i<=L.length;i++)
{
if(L.elem[i].key<L.elem[i-1].key)
{
L.elem[0].key=L.elem[i].key;
yd++;
j=i-1;
bj++;
while(L.elem[0].key<L.elem[j].key)
{
L.elem[j+1].key=L.elem[j].key;
j--;
yd++;
bj++;
}
L.elem[j+1].key=L.elem[0].key;
yd++;
}
}
end_t=clock();
printf("比较次数为 %d移动次数为 %d\n",bj,yd);
printf("排序用时为 %f\n",float(end_t-start_t)/CLK_TCK);
}
void xier(SqList &L)//希尔
{
start_t=clock();
int i,d=L.length/2,j,w=0,k,yd=0,bj=0;
while(w<d)
{
w=1;
for(i=w;i<L.length;i=i+d)
{
k=i;
for(j=i+d;j<L.length;j=j+d)
{
if(L.elem[i].key>L.elem[j].key)
{
k=j;
bj++;
}
}
if(i!=k)
{
L.elem[0].key=L.elem[i].key;
L.elem[i].key=L.elem[k].key;
L.elem[k].key=L.elem[0].key;
yd+=3;
}
w++;
}
d=d/2;
w=1;
}
end_t=clock();
printf("比较次数为 %d移动次数为 %d\n",bj,yd);
printf("排序用时为 %f\n",float(end_t-start_t)/CLK_TCK);
}

void BeforeSort()
{
yd1=0,bj1=0;
}
void display(int m,int n)
{
printf("比较次数为 %d移动次数为 %d\n",m,n);
}
int Partition(SqList &L,int low,int high)//快速排序
{
int pivotkey;
L.elem[0]=L.elem[low];
yd1++;
pivotkey=L.elem[low].key;
while (low<high)
{
yd1++;
while(low<high&&L.elem[high].key>=pivotkey)
--high;
L.elem[low]=L.elem[high];
bj1++;
yd1++;
while (low<high&&L.elem[low].key<=pivotkey)
++low;
L.elem[high]=L.elem[low];
bj1++;
yd1++;
}
L.elem[low]=L.elem[0];
yd1++;
return low;
}
void QSort(SqList &L,int low,int high)
{
int pivotloc;
if(low<high)
{
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList &L)
{
start_t=clock();
BeforeSort();
QSort(L,1,L.length);
display(yd1,bj1);
end_t=clock();
printf("排序用时为 %f\n",float(end_t-start_t)/CLK_TCK);
}
void Merge(ElemType R[],ElemType R1[],int low,int m,int high)//归并
{
int i=low, j=m+1, k=low;
while(i<=m&&j<=high)
{
if(R[i].key<=R[j].key)
{
bj1++;
R1[k]=R[i];
yd1++;
i++;
k++;
}
else
{
bj1++;
R1[k]=R[j];
yd1++;
j++;
k++;
}
}
while(i<=m)
{
R1[k]=R[i];
yd1++;
i++;
k++;
}
while(j<=high)
{
R1[k]=R[j];
yd1++;
j++;
k++;
}
}
void MergePass(ElemType R[],ElemType R1[],int length, int n)
{
int i=0,j;
while(i+2*length-1<n)
{
Merge(R,R1,i,i+length-1,i+2*length-1);
i=i+2*length;
}
if(i+length-1<n-1)
Merge(R,R1,i,i+length-1,n-1);
else
for(j=i;j<n;j++)
R1[j]=R[j];
}
void MSort(ElemType R[],ElemType R1[],int n)
{
int length=1;
while (length<n)
{
MergePass(R,R1,length,n);
length=2*length;
MergePass(R1,R,length,n);
length=2*length;
}
}
void MergeSort(SqList &L)
{
start_t=clock();
BeforeSort();
MSort(L.elem,L.elem,L.length);
display(yd1,bj1);
end_t=clock();
printf("排序用时为 %f\n",float(end_t-start_t)/CLK_TCK);
}

void main()
{
SqList L;
addlist(L);
printf("起泡排序: \n");
qipao(L);
addlist(L);
printf("直插排序: \n");
InsertSort(L);
addlist(L);
printf("选择排序: \n");
SelectSort(L);
addlist(L);
printf("希尔排序: \n");
xier(L);
addlist(L);
printf("快速排续: \n");
QuickSort(L);
addlist(L);
printf("归并排序: \n");
MergeSort(L);
}

参考资料：http://wenku.baidu.com/view/51f3b202de80d4d8d15a4fa6.html

来自：求助得到的回答