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

《几种常见内部排序算法比较》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、常见内部排序算法比较　　排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。　　问题分析和总体设计ADTOrderableList{数据对象：D={ai

2、ai∈IntegerSet,i=1,2,…,n,n≥0}数据关系：R1={〈ai-1，ai〉

3、ai-1,ai∈D,i=1,2,…,n}基本操作：InitList(n)操作结果：构造一个长度为n

4、，元素值依次为1，2，…，n的有序表。Randomizel(d,isInverseOrser)操作结果：随机打乱BubbleSort()操作结果：进行起泡排序InserSort()操作结果：进行插入排序SelectSort()操作结果：进行选择排序QuickSort()操作结果：进行快速排序HeapSort()操作结果：进行堆排序ListTraverse(visit())操作结果：依次对L种的每个元素调用函数visit()}ADTOrderableList　　待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据

5、做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果.要求对结果进行分析.详细设计　　1、起泡排序　算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。bubblesort(structrecr[],intn){inti,j;structrecw;unsignedlon

6、gintcompare=0,move=0;for(i=1;i<=n-1;i++)for(j=n;j>=i+1;j--){if(r[j].key

7、..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;for(i=2;i<=n;i++){compare++;r[0]=r[

8、i];move++;j=i-1;while(r[0].key{r[j+1]=r[j];j--;move++;++compare;}r[j+1]=r[0];move++;}printf("InsertSortcompare=%ld,move=%ld",compare,move);}　　3、简单选择排序　　算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。selectsort(structrecr[],intn){unsignedlong

9、intcompare=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].key>r[k].key){k=j;compare++;}w=r[i];r[i]=r[k];r[k]=w;move=move+3;}}printf("SelectSortcompare=%ld,move=%ld",compare,move);}　　4、快速排序　　算法：首先检查数据列表中的数据数，如果小于两个，则直接退出程序。如果有超过

10、两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序。通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过，你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多。q(structrecr[],ints