2018-04-21|2018-04-21 (私货)排序算法小结

前言:去年找工作时整理的,没想到这么快又要拿来用
冒泡排序 复杂度:N^2
遍历列表 每次比较相邻元素大小, if list[i]> list[i+1]:交换元素位置 继续遍历

修改后:识别排序列表和停止的优点
短冒泡排序:加入判断,若某次遍历没有交换,则排序完成
选择排序 复杂度N^2
改进冒泡:相比之减少了交换次数
每次遍历只寻找**最大值**,然后放置在正确的位置

插入排序 N^2,最好的情况下只有N,
基准研究中,插入排序有非常好的性能
在列表较低位置形成有序列表 遍历时插入新的项进入,形成新的有序列表

希尔排序 N~ N^2之间
特点:增量i的选择
若i选择1,则是标准插入排序
对i个子列表进行插入排序 合并i个子列表,进行一次插入排序

归并排序 merge sort 复杂度NLogN,需要额外空间
思路: 1. 二分列表,直到不可拆分;if len(list) >1;logN 2. 对两半排序完成,就执行合并的操作;递归调用merge sort; N 注意:在python里,切片O(K),所以运算需要删除slice运算符

快速排序 NlogN,不需要额外空间
最坏N^2: 如果分割点不在列表中间附近
找pivot值,一般选定mid 拆分成left, mid, right 列表(递归) 最后合并列表

堆排序 NlogN,空间O(1)
相比快排,heap sort “make poor use of cache memory",不适合较少的元素排序
知道概念大根堆(大顶堆)、小根堆(小顶堆)
1,L(i) <= L(2i)且L(i) <= L(2i+1) 即双亲节点都小于孩子节点
2,L(i) >= L(2i)且L(i) >= L(2i+1) 其中i属于[1, n/2],双亲节点都大于孩子节点
思路: 初始化堆:从子节点比较较大的子节点,与父节点交换 将堆顶元素输出:堆顶元素与堆底元素(最后一个元素)交换,重新调整堆

时间复杂度:向下调整的时间与树高有关,为O(h)。可以证明在元素个数为n的序列上建堆,其时间复杂度为O(n)。之后还有n-1次向下调整操作,每次调整的时间为O(h)=O(logN),故在最好,最坏和平均情况下,堆排序的时间复杂度为O(nlogn)。
空间复杂度:仅使用了常数个辅助单元,空间复杂度为O(1)。
参考: 堆排序
https://www.cnblogs.com/wangchaowei/p/8288216.html--# 数据结构——堆(Heap)大根堆、小根堆

(待)!!!侏儒排序
def gnomesort(seq): i = 0 while i < len(seq): if i == 0 or seq[i-1] < = seq[i]: i += 1 else: seq[i], seq[i-1] = seq[i-1] ,seq[i] i - = 1


2018-04-21|2018-04-21 (私货)排序算法小结
文章图片
image.png
2018-04-21|2018-04-21 (私货)排序算法小结
文章图片
image.png
图来源: 八大排序算法
【2018-04-21|2018-04-21 (私货)排序算法小结】???堆排序时间复杂度稳定

    推荐阅读