各种排序方法的比较与讨论

各种排序方法的比较与讨论

ID:8266232

大小:54.00 KB

页数:11页

时间:2018-03-15

各种排序方法的比较与讨论_第1页
各种排序方法的比较与讨论_第2页
各种排序方法的比较与讨论_第3页
各种排序方法的比较与讨论_第4页
各种排序方法的比较与讨论_第5页
资源描述:

《各种排序方法的比较与讨论》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、各种排序方法的比较与讨论现在流行的排序有:选择排序、直接插入排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、基数排序。一、选择排序1.基本思想:  每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。2.排序过程:【示例】:初始关键字[4938659776132749]第一趟排序后13[38659776492749]第二趟排序后1327[659776493849]第三趟排序后132738[9776496549]第四趟排序后13273849[4997

2、6576]第五趟排序后1327384949[979776]第六趟排序后132738494976[7697]第七趟排序后13273849497676[97]最后排序结果13273849497676973.voidselectionSort(Type*arr,longlen){longi=0,j=0;/*iteratorvalue*/longmaxPos;assertF(arr!=NULL,"InInsertSortsort,arrisNULL");for(i=len-1;i>=1;i--){maxPos=i;for

3、(j=0;jif(arr[maxPos]if(maxPos!=i)swapArrData(arr,maxPos,i);}}选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换.二.直接插入排序插入排序(InsertionSort)的基本思想是:每

4、次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。直接插入排序 直接插入排序(StraightInsertionSort):将一个记录插入到排好序的有序表中,从而得到一个新的、记录数增1的有序表。直接插入排序算法哨兵(监视哨)有两个作用:一是作为临变量存放R[i](当前要进行比较的关键字)的副本;二是在查找循环中用来监视下标变量j是否越界。当文件的初始状态不同时,直接插入排序所耗费的时间是有很大差异的。最好情况是文件初态为正序,此时算法的时间复杂度为O(n),最坏

5、情况是文件初态为反序,相应的时间复杂度为O(n2),算法的平均时间复杂度是O(n2)。算法的辅助空间复杂度是O(1),是一个就地排序。直接插入排序是稳定的排序方法。三.冒泡排序[算法思想]:将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。[算法]:voidBubbleSort(SeqListR){//R(l..

6、n)是待排序的文件,采用自下向上扫描,对R做冒泡排序inti,j;Booleanexchange;//交换标志for(i=1;iexchange=FALSE;//本趟排序开始前,交换标志应为假for(j=n-1;j>=i;j--)//对当前无序区R[i..n]自下向上扫描if(R[j+1].keyR[0]=R[j+1];//R[0]不是哨兵,仅做暂存单元R[j+1]=R[j];R[j]=R[0];exchange=TRUE;//发生了交换,故将交换标志置为真}if(!exchange)return;//本趟排序未发生

7、交换,提前终止算法}//endfor(外循环)}//BubbleSort[分析]:起泡排序的结束条件为:最后一趟没有进行“交换”。从起泡排序的过程可见,起泡排序是一个增加有序序列长度的过程,也是一个缩小无序序列长度的过程,每经过一趟起泡,无序序列的长度只缩小1。[算法思想]:将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重

8、者在下为止。[算法]:voidBubbleSort(SeqListR){//R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序inti,j;Booleanexchange;//交换标志for(i=1;iexchange=FALSE;//本趟排序开始前,交换标志应为假for(j=n-1;j>=i;j--)//对当前无序区R[i..n]

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。