当前位置：文档库 › 数据结构各种排序

数据结构各种排序

希尔排序：将无序数组分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行插入排序；然后再选择一个更小的增量，再将数组分割为多个子序列进行排序......最后选择增量为1，即使用直接插入排序，使最终数组成为有序。
增量的选择：在每趟的排序过程都有一个增量，至少满足一个规则增量关系 d[1] > d[2] > d[3] >..> d[t] = 1 (t趟排序)；根据增量序列的选取其时间复杂度也会有变化，这个不少论文进行了研究，在此处就不再深究；本文采用首选增量为n/2,以此递推，每次增量为原先的1/2，直到增量为1；
/********************************************************
*函数名称：ShellSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明：希尔排序
*********************************************************/
void ShellSort(int* pDataArray, int iDataNum)
{
int d = iDataNum / 2; //初始增量设为数组长度的一半
while(d >= 1)
{
ShellInsert(pDataArray, d, iDataNum);
d = d / 2; //每次增量变为上次的二分之一
}
}

选择排序：
每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

间间断断的将9种排序实现，并且将其以博客笔记的形式记录下来；现在就该来综合的分析这九种排序，让我们先来看看其算法复杂度和稳定性的分析结果：

算法复杂度以及稳定性分析

算法名称平均时间辅助空间稳定性
冒泡排序 O(n2) O(1) 是
选择排序 O(n2) O(1) 否
插入排序 O(n2) O(1) 是
自底向上归并排序 O(nlog2n) O(n) 是
自顶向下归并排序 O(nlog2n) O(n) 是
快速排序 O(nlog2n) O(n) 否
堆排序 O(nlog2n) O(1) 否
基数排序 O(dn) O(rn) 是
希尔排序 \ O(1) 否

排序的时间效率比较

下图表名了各种算法在不同数据规模下，完成排序所消耗的时间（毫秒为单位），从表中可以显然看出O(n2)的排序算法比O(nlog2n)的算法时间多出几百上千倍，而且随着数据数据规模增大时间比也会随着增大；因为排序的数据采用随机数，顺序将被打乱，快速排序算法优于其他排序算法！

算法名称 1万 2万 3万 4万 5万 6万 7万 8万 9万 10万
冒泡排序 1442 5497 12206 21861 34017 49148 67394 88880 111939 139071
选择排序 199 816 1790 3254 5062 7166 9645 12636 16102 19643
插入排序 178 717 1628 2882 4458 6446 8822 11649 14547 17914
自底向上归并排序 3 6 9 12 15 18 22 26 28 33
自顶向下归并排序 3 7 11 15 18 23 27 31 36 40
快速排序 2 5 8 11 14 18 21 25 29 32
堆排序 3 7 12 16 19 23 26 30 34 37
基数排序 9 21 30 40 49 59 66 75 90 98
希尔排序 3 8 11 15 24 24 29 35 40 41

下面采用图表形

式将数据直观展示出来(将O(n2)的算法和O(nlog2n)算法分开，因为完全不是一个数量级的):

上图显示快排速度和自底向上归并排序奇虎相当，接下来是堆排序、希尔排序；出乎意料的是基数排序，号称O(dn)的基数排序却不是那么靠前，个人觉得和冒泡排序速度慢的原因相同，赋值操作太多，降低了时间效率。

堆排序：
堆排序中 heap 算法的时间复杂度与堆所对应的完全二叉树的树高度 log2n 相关。而 heapsort 中对 heap 的调用数量级为n，所以堆排序的整个时间复杂度为O(nlog2n) 。并且堆排序是不稳定的。
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单

#include
using namespace std;
int main()
{
//srand((unsigned)time(NULL));
srand(NULL);
for(int i=1;i<=100;i++)
{
int t=rand()%10000;
cout<if(i%10==0)
cout << endl;
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

const int N=100010;
int howmany,datanum[N]; //全局变量定义数组和用户输入个数
int old[N],a[N],t;
//全局变量定义一个数组用于接受用户输入并保持其不变
int input_num()//数据输入
{
int i,j;
printf("您要给多少个数排序？\n\t\t");
scanf("%d",&howmany);
for(i=1;i<=howmany;i++)
{
printf("请输入第%d个数:\n\t\t",i);
scanf("%d",&datanum[i]);
old[i]=datanum[i]; //old为用户输入数据
}
}

int output_num()//排序前数据输出
{
int olddata[100];//这是用来存放排序前的数的
int x;
for(x=1;x<=howmany;x++)
{
olddata[x]=old[x];//把old中的数据传过去，因为old中的数据没改变过，
}//所以下面一直可以输出前的排序格式
printf("待排序的数据为：\n");
for(x=1;x<=howmany;x++)
{
printf("%d ",olddata[x]);
}
printf("\n");
}

int outnew0()//排序后数据输出从大到小
{
int i,j;
printf("排序后的结果为:\n");
for(i=howmany;i>=1;i--)
{
printf("%d ",datanum[i]);
}
printf("\n\n");
}

int outnew1()//排序后逆序数据输出从小到大
{
int i,j;
printf("排序后的结果为:\n");
for(i=1;i<=howmany;i++)
{
printf("%d ",datanum[i]);
}
printf("\n\n");
}

//下面部分为各种排序的具体实现，算法简单所以不在算法上加注释了。

void charu()//插入排序
{
int i,j;
int temp;
output_num();//显示用户输入数据的顺序
for(i=1;i<=howmany;i++)
{
int temp=datanum[i];
for (j=i;j>0 && temp{
datanum[j]=datanum[j-1];
}
datanum[j]=temp;
}
if(!t)
outnew0();//输出排序

后顺序
else
outnew1();
}

void maopao()//冒泡排序
{
int i,j;
int temp;
output_num();
for(i=1;i<=howmany-1;i++)
{
for(j=1;j<=howmany-i-1;j++)
{
if(datanum[j]>datanum[j+1])
{
temp=datanum[j];
datanum[j]=datanum[j+1];
datanum[j+1]=temp;
}
}
}
if(!t)
outnew0();//输出排序后顺序
else
outnew1();
}

void xuanze()//选择排序
{
int i,j;
int temp,t;
output_num();
for(i=1;i<=howmany-1;i++)
{
t=i;
for(j=i+1;j{
if(datanum[j]if(i!=t)
{
temp=datanum[t];
datanum[t]=datanum[i];
datanum[i]=temp;
}
}
}
if(t)
outnew0();//输出排序后顺序
else
outnew1();
}

//堆操作起点
void HeapAdjust(int *a,int i,int size) //调整堆
{
int lchild=2*i; //i的左孩子节点序号
int rchild=2*i+1; //i的右孩子节点序号
int max=i; //临时变量
if(i<=size/2) //如果i是叶节点就不用进行调整
{
if(lchild<=size&&a[lchild]>a[max])
{
max=lchild;
}
if(rchild<=size&&a[rchild]>a[max])
{
max=rchild;
}
if(max!=i)
{
swap(a[i],a[max]);
HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆
}
}
}

void BuildHeap(int *a,int size) //建立堆
{
int i;
for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2
{
HeapAdjust(a,i,size);
}
}

void HeapSort(int *a,int size) //堆排序
{
int j=1;
//for(int i=0;i// printf("%d ",b[i]);
//for(int i=size-1;i>=0;i--)
// a[i]=a[i-1];
//for(int i=1;i<=size;i++)
// printf("%d ",a[i]);
BuildHeap(a,size);
for(int i=size;i>=1;i--)
{
//cout<swap(a[1],a[i]); //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面
//BuildHeap(a,i-1); //将余下元素重新建立为大顶堆
HeapAdjust(a,1,i-1); //重新调整堆顶节点成为大顶堆
}
}//堆操作终点
/*//快速排序可以选择用algorithm里的sort排序实现
void kuaisu(int datanum[],int first,int end )//快速排序
{
int i,j;
int temp=datanum[first];
i=first;j=end;
while(i{
while(i=temp)
j--;
datanum[i]=datanum[j];
while(ii++;
datanum[j]=datanum[i];
}
datanum[i]=temp;
if(firstkuaisu(datanum,first,i-1);
if(end>i+1)
kuaisu(datanum,i+1,end);
}
*/

void kuaisu1()//快速排序1
{
output_num();
sort(datanum+1,datanum+howmany+1);
if(!t)
outnew0();//输出排序后顺序
else
outnew1();
}

void kuaisu2()//快速排序2
{
sort(datanum+1,datanum+howmany+1);
if(!t)

outnew0();//输出排序后顺序
else
outnew1();
}

int main()//主函数，显示菜单并进行算法选择
{
printf("DATE:May twenty 2014\n");
printf("All Copyright Reserved ?2014-2015 Wang Guangchun \r\n\n\n");
printf("ADDRESS: 604 AYIT\n");
printf("——————————————————— \n");
printf("——————各种排序比较————————— \n");
printf("默认从大到小输出，可以选择9进行切换\n");
printf("——————————————————— \n");
printf(" * * \n");
printf(" * * * \n");
printf(" * * \n");
printf(" * 520 * \n");
printf(" * 欢迎 * \n");
printf(" * 使用 * \n");
printf(" * * \n");
printf(" * \n");
int n;//变量定义用于菜单选择
input_num();//调用输入函数，请求用户输入数据
while(1)
{
//主界面操作实现
printf("——————————————————— \n");
printf("——————请输入指令———————— \n");
printf("————********************————— \n");
printf("————$ 1.排序前的数据 $————— \n");
printf("————$ 2.插入排序 $————— \n");
printf("————$ 3.冒泡排序 $————— \n");
printf("————$ 4.选择排序 $————— \n");
printf("————$ 5.快速排序 $————— \n");
printf("————$ 6.堆排序 $————— \n");
printf("————$ 7.重新输入 $————— \n");
printf("————$ 8.排序后的数据 $————— \n");
printf("————$ 9.选择排序方式 $————— \n");
printf("————********************————— \n");
printf("————— 0.退出 —————— \n");
printf("——————————————————— \n");
printf("请选择：\n");
scanf("%d",&n);
switch(n)
{
case 1:
output_num(); //排序前数据
break;
case 2:
charu(); //直接插入排序
break;
case 3:
maopao(); //冒泡排序
break;
case 4:
xuanze(); //选择排序
break;
case 5:
kuaisu1();//快速排序
//kuaisu(datanum,0,howmany-1);
break;
case 6:
//for(int i=0;i// a[j++]=b[i];
HeapSort(datanum,howmany);
if(!t)
outnew0();//输出排序后顺序
else
outnew1();
break;
case 7:
input_num();
break;
case 8:
kuaisu2();
break;
case 9

:
//副主界面操作实现
printf("——————请输入指令———————— \n");
printf("————********************————— \n");
printf("————$ 1.从小到大 $————— \n");
printf("————$ 0.从大到小 $————— \n");
printf("————********************————— \n");
printf("————— 87.退出 —————— \n");
printf("——————————————————— \n");
printf("请选择：\n");
scanf("%d",&t);
if(t==87)
{
printf("欢迎再次使用!!!\n\r\n");
printf("*******************************************\n");
printf("** . ..... . . ..... **\n");
printf("** . . . . . . **\n");
printf("** . . . . . ..... **\n");
printf("** . . . . . . **\n");
printf("** ..... ..... . ..... **\n");
printf("*******************************************\n");
return 0; //退出
}

//break;
printf("再次输入排序方法！！！\n");
break;
case 0:
printf("欢迎再次使用!!!\n\r\n");
printf("*******************************************\n");
printf("** . ..... . . ..... **\n");
printf("** . . . . . . **\n");
printf("** . . . . . ..... **\n");
printf("** . . . . . . **\n");
printf("** ..... ..... . ..... **\n");
printf("*******************************************\n");
return 0; //退出
break;
default:printf("\n选项输入有误，请重试！\n\n");//输入有误提示
}
}
getchar();

return 0;
}