数据结构内部排序算法
- 2017-09-22 16:47:43
- 2,617 次阅读
- 0
在学习内部排序算法时手工求每种排序的算法时,能够加深对排序算法的了解,并能发现一些算法的排序规律。这样在理解内部排序算法的程序时,能够得到很大的帮助。下面对52,10,13,14,12,80,16,26,88,66十个数据采取比较常用的内部排序算法进行排序:
①直接插入排序:
初始值: 52,10,13,14,12,80,16,26,88,66
第一趟:(10,52),13,14,12,80,16,26,88,66
第二趟:(10,13,52),14,12,80,16,26,88,66
第三趟:(10,13,14,52),12,80,16,26,88,66
第四趟:(10,12,13,14,52),80,16,26,88,66
第五趟:(10,12,13,14,52,80),16,26,88,66
第六趟:(10,12,13,14,16,52,80),26,88,66
第七趟:(10,12,13,14,16,26,52,80),88,66
第八趟:(10,12,13,14,16,26,52,80,88),66
第九趟:(10,12,13,14,16,26,52,66,80,88)
直接插入排序算法思想:每趟将一个待排序的关键字按其值的大小插入到已经排好的部分有序序列的适当位置上,直到所有待排关键字都被插入到有序序列中为止。
②希尔排序:
初始值:52,10,13,14,12,80,16,26,88,66(选取增量d=5,3,1)
第一趟:52,10,13,14,12,80,16,26,88,66
第二趟:14,10,13,16,12,80,52,26,88,66
第三趟:10,12,13,14,16,26,52,66,80,88
希尔排序又叫缩小增量排序,其本质是插入排序,只是将待排序列按某种规则分成几个子序列,分别对这几个子序列进行直接插入排序。这个规则体现了增量的选取,当增量选为1时,就是
直接插入排序。
③冒泡排序
初始值:52,10,13,14,12,80,16,26,88,66
第一趟:10,13,14,12,52,16,26,80,66,88
第二趟:10,13,12,14,16,26,52,66,80,88
第三趟:10,12,13,14,16,26,52,66,80,88
第四趟:10,12,13,14,16,26,52,66,80,88
冒泡排序算法结束的条件是在一趟排序过程中没有发生关键字交换。
④快速排序
初始值:52,10,13,14,12,80,16,26,88,66
第一趟:26,10,13,14,12,16,52,80,88,66
第二趟:16,10,13,14,12,26,52,80,88,66
第三趟:12,10,13,14,16,26,52,80,88,66
第四趟:10,12,13,14,16,26,52,80,88,66
第五趟:10,12,13,14,16,26,52,80,88,66
快速排序是交换类的排序,它通过多次划分操作实现排序。
⑤直接选择排序:
初始值: 52,10,13,14,12,80,16,26,88,66
第一趟:(10),52,13,14,12,80,16,26,88,66
第二趟:(10,12),13,14,52,80,16,26,88,66
第三趟:(10,12,13),14,52,80,16,26,88,26
第四趟:(10,12,13,14),52,80,16,26,88,66
第五趟:(10,12,13,14,16),80,52,26,88,66
第六趟:(10,12,13,14,16,26),52,80,88,66
第七趟:(10,12,13,14,16,26,52),80,88,66
第八趟:(10,12,13,14,16,26,52,66),88,80
第九趟:(10,12,13,14,16,26,52,66,80),90
直接选择排序采用最简单的选择方式,从头到尾顺序扫描序列,找出最小的一个关键字和第一个关键字交换,接着从剩下的关键字中继续这种选择和交换,最终使序列有序。
⑥归并排序
初始值: 52,10,13,14,12,80,16,26,88,66
第一趟:[52],[10],[13],[14],[12],[80],[16],[26],[88],[66]
第二趟:[10,52],[13,14],[12,80],[16,26],[66,88]
第三趟:[10,13,14,52],[12,16,26,80],[66,88]
第四趟:[10,12,13,14,16,26,52,66,80,88]
归并排序先将整个序列分成两半,对每一半分别进行归并排序,将得到两个有序序列,然后将这两个序列归并成一个序列。
⑦基数排序
第一趟:10,80,52,12,13,14,16,26,66,88
第二趟:10,12,13,14,16,26,52,66,80,88
基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。
人生短暂,开心每一天!