几种常见内部排序算法比较

第第页几种常见内部排序算法比较这是在我高校期间学习C语言时学到的几种常见的内部排序算法的。在高校期间,计算机相关专业的同学,只要掌控这几种排序算法就已经足够了!

常见内部排序算法比较

排序算法是数据结构学科经典的内容，其中内部排序现有的算法有许多种，到底各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，径直插入排序，简约选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。

问题分析和总体设计

ADTOrderableList

{

数据对象：D={ai|ai∈IntegerSet,i=1,2,…,n,n≥0}

数据关系：R1={〈ai-1，ai〉|ai-1,ai∈D,i=1,2,…,n}

基本操作：

InitList(n)

操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d,isInverseOrser)

操作结果：随机打乱

BubbleSort()

操作结果：进行起泡排序

InserSort()

操作结果：进行插入排序

SelectSort()

操作结果：进行选择排序

QuickSort()

操作结果：进行快速排序

HeapSort()

操作结果：进行堆排序

ListTraverse(visit())

操作结果：依次对L种的每个元素调用函数visit()

}ADTOrderableList

待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果.

要求对结果进行分析.

这是在我高校期间学习C语言时学到的几种常见的内部排序算法的。在高校期间,计算机相关专业的同学,只要掌控这几种排序算法就已经足够了!

具体设计

1、起泡排序

算法：核心思想是扫描数据清单，查找涌现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到全部的项目都按顺次排好。

bubblesort(structrecr[],intn)

{

inti,j;

structrecw;

unsignedlongintcompare=0,move=0;

for(i=1;i=n-1;i++)

for(j=n;j=i+1;j--)

{

if(r[j].keyr[j-1].key)

{

w=r[j];

r[j]=r[j-1];

r[j-1]=w;

move=move+3;

}

compare++;

}

printf(\nBubbleSortcompare=%ld,move=%ld\n,compare,move);}

2、径直插入排序

算法：经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺次比较的方法。首先比较L[i]和L[i-1]，假如L[i-1]≤L[i]，那么L[1..i]已排好序，第i遍处理就结束了；否那么交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j]≤L[j+1]时为止。

insertsort(structrecr[],intn)

{

inti,j;

unsignedlongintcompare=0,move=0;

这是在我高校期间学习C语言时学到的几种常见的内部排序算法的。在高校期间,计算机相关专业的同学,只要掌控这几种排序算法就已经足够了!

for(i=2;i=n;i++)

{compare++;

r[0]=r[i];

move++;

j=i-1;

while(r[0].key{r[j+1]=r[j];

j--;

move++;

++compare;}

r[j+1]=r[0];

move++;

}

printf(\nInsertSortcompare=%ld,move=%ld\n,compare,move);}

3、简约选择排序

算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。

selectsort(structrecr[],intn)

{

unsignedlongintcompare=0,move=0;

inti,j,k;

structrecw;

for(i=1;i=n-1;i++)

{k=i;

for(j=i+1;j=n;j++)

{if(r[j].keyr[k].key){k=j;compare++;}

w=r[i];

r[i]=r[k];

r[k]=w;

move=move+3;

}

}

printf(\nSelectSortcompare=%ld,move=%ld\n,compare,move);}

4、快速排序

这是在我高校期间学习C语言时学到的几种常见的内部排序算法的。在高校期间,计算机相关专业的同学,只要掌控这几种排序算法就已经足够了!

算法：首先检查数据列表中的数据数，假如小于两个，那么径直退出程序。假如有超过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序。通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过，你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多。

q(structrecr[],ints,intt)

{

inti=s,j=t;

if(st)

{

r[0]=r[s];++a;c++;

do{

while(jir[j].key=r[0].key)

{j--;

++a;}

if(ij)

{r[i]=r[j];

i++;

c++;}

while(ijr[i].key=r[0].key)

{i++;

++a;}

if(ij)

{r[j]=r[i];

j--;

c++;}

}while(ij);

r[i]=r[0];

c++;

q(r,s,j-1);

q(r,j+1,t);

}

}

5.堆排序

基本思想：堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺次存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

(2)堆的定义:N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满意特性：

这是在我高校期间学习C语言时学到的几种常见的内部排序算法的。在高校期间,计算机相关专业的同学,只要掌控这几种排序算法就已经足够了!

Ki≤K2iKi≤K2i+1(1≤I≤[N/2])

sift(structrecr[],intl,intm)

{

inti,j;

structrecw;

i=l;j=2*i;

w=r[i];

while(j=m)

{

if(jmr[j].keyr[j+1].key){j++;

}

if(w.keyr[j].key)

{

r[i]=r[j];

i=j;

j=2*i;

}

elsej=m+1;

}

r[i]=w;

}

heapsort(structrecr[],intn)

{

unsignedlongintcompare=-1,move=-1;

structrecw;

inti;

inta;

for(i=n/2;i=1;i--)a=sift(r,i,n);

compare++;

move++;

for(i=n;i=2;i--)

{

w=r[i];

r[i]=r[1];

r[1]=w;

a=sift(r,1,i-1);

compare+=a;

move+=a;

}

}

这是在我高校期间学习C语言时学到的几种常见的内部排序算法的。在高校期间,计算机相关专业的同学,只要掌控这几种排序算法就已经足够了!

小结：

1.学会运用随机函数randomize()为数组赋初值要在头文件中添加#include。

2．在做此程序之前基本上是在理解了各种排序过程以后完成的。

3.对排序算法的总结：

(1)假设n较小(如n≤50)，可采纳径直插入或径直选择排序。当记录规模较小时，径直插入排序较好；否那么由于径直选择移动的记录数少于径直插人，应选径直选择排序为宜。

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

(3)假设n较大，那么应采纳时间繁复度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的帮助空间少于快速排序，并且不会涌现快速排序可能涌现的最坏状况。这两种排序都是不稳定的。

这是在我高校期间学习C语言时学到的几种常见的内部排序算法的。在高校期间,计算机相关专业的同学,只要掌控这几种排序算法就已经足够了!

常见内部排序算法比较

排序算法是数据结构学科经典的内容，其中内部排序现有的算法有许多种，到底各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，径直插入排序，简约选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。

问题分析和总体设计

ADTOrderableList

{

数据对象：D={ai|ai∈IntegerSet,i=1,2,…,n,n≥0}

数据关系：R1={〈ai-1，ai〉|ai-1,ai∈D,i=1,2,…,n}

基本操作：

InitList(n)

操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d,isInverseOrser)

操作结果：随机打乱

BubbleSort()

操作结果：进行起泡排序

InserSort()

操作结果：进行插入排序

SelectSort()

操作结果：进行选择排序

QuickSort()

操作结果：进行快速排序

HeapSort()

操作结果：