各类排序算法及其优化总结

2017-07-07 17:02 阅读 658 次 评论 0 条

本文对各类排序算法的实现、优化、复杂度、稳定性、适用场景作以全面总结,为了突出算法的简洁、易懂,我去除了模板与仿函数的冗余,默认为升序进行模拟。

插入排序

插入排序基本思想:每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序的一组元素的合适位置上去,直到元素插完。

☞ 直接插入排序

基本思想:当我们插入第i(i>=1)个元素时,前面的所有元素已经排好序,此时我们使用当前元素从后向前比较,直到找到一个小于array[i]的节点(若没有,则插在数组下标为0的地方),从下一个节点顺序后移,将array[i]插入进来。

☞ 二分插入排序(优化)

基本思想:在直接插入排序的基础上进行优化,因为待插入元素之前的元素已经有序,我们没必要每个都遍历,借助而二分法的思想可以有效降低查找的时间。

希尔排序

基本思想:希尔排序是插入排序的一个变种。不同之处在于我们按步长gap分组,对每组的记录采用直接插入排序,随着步长的逐渐减少,分组包含的记录越来越多,直到gap=1时,构成了一个有序记录。

下图中为了方便,对gap以gap/2来计算,但最优的算法是gap/3+1。

选择排序

基本思想:每一趟(例如第i趟,i=0,1,…,n-2)在后面n-i个待排序的数据元素集合中选出关键码最小的数据元素,作为有序元素序列的第i个元素,待到第n-2趟做完,待排序元素集合中只剩 下1个元素,排序结束。

☞ 选择排序(单边缩小空间)

基本思想:我们定义一个maxIndex来标记区间内最大值的下标,第一次遍历完数组后,更新maxIndex的指向,与下标为end(最后一个元素)的元素交换,end--缩小空间,继续遍历更新maxIndex。

☞ 选择排序(双边缩小空间1.0)

基本思想:每一趟遍历我们需要找出最大元素的下标与最小元素的下标,然后用处于最小下标的元素与begin(首元素下标)交换,用最大下标的元素与end(尾元素下标),最后begin++,end--同时缩短区间,直到begin与end相等。

注意:如果begin与maxIndex相同,begin与minPos交换之后,maxPos也应该指向minPos。

☞ 选择排序(双边缩小空间2.0)

基本思想:1.0版本中,我们需要考虑最大下标与begin的重合问题,为了避免这样的问题出现,我们将不再使用maxPos和minPos,而改用直接交换数据,然后缩小空间,直到左右空间重合。

堆排序

基本思想:大堆对应升序序列,小堆对应降序队列,我们从最后一个非叶子结点建堆,步骤如下:

⑴ 将堆顶元素与当前最大堆的最后一个节点交换

⑵ 最大堆节点-1,即调整剩下的n-1个节点

⑶ 从堆顶继续向下调整,试之满足最大堆,循环⑴ ⑵ ,直至剩下一个节点。

快速排序

https://github.com/GitToMy1024Dream/Algorithm 先看github上的代码吧,最近忙于复习,抽时间画图。

归并排序

计数排序

基数排序

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:各类排序算法及其优化总结 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情