排序算法大集合上排序算法大集合上

1. 插入排序

时间复杂度：最好是n-1，最坏是n(n-1)/2，平均为O(n^2)。
空间复杂度： O(1)
多作为快排的补充，适用于少量的数据排序。
该算法是稳定的，依赖初始排序顺序。

过程：

以第一个数为已经排好的队列，将第二个数从队列的右向左比较。
如果比它大，那么，该队列里的元素就往右边移动一位，接着比较该元素左边的元素；比它小，那么，就把他存入该队列里的元素的右边一位。
形成一个新的队列，再走1，2。
更多

# 插入排序 def insert(nums): for i in range(1, len(nums)): temp = nums[i] # 是否找到一个合适的位置插入 label = False for j in range(i-1,-1,-1): # 找到位置了，插入 if nums[j] < temp: nums[j+1] = temp label = True break else: # 右移一位 nums[j+1] = nums[j]if not label: nums[0] = tempnums = [2,3,4,5,1,9,3,0,2,1] insert(nums) print(nums)

【排序算法大集合上】感觉上面这个方法有些复杂了，改进了一下：

def insert(nums): for i in range(1, len(nums)): j = i while j > 0: if nums[j] < nums[j - 1]: nums[j], nums[j - 1] = nums[j - 1], nums[j] j -= 1 else: break

2. 二分插入排序

时间复杂度：最好情况下：O(nlogn)；最坏情况下：O(n^2)
分析：最外层有n次循环；最内侧分为两个部分，一个是二叉搜索（logn），一个是for循环（n）；所以，最好的情况是元素所在的位置就是插入位置（nlogn）；最坏情况和平均的情况就是不断在查找，即为：n(logn+n)->n^2。
空间复杂度维O(1)。
是稳定的，依赖初始排序顺序。

过程：

在插入第i个元素时，对前面的0～i-1元素进行折半，
先跟他们中间的那个元素比，如果小，则对前半再进行折半。
否则对后半进行折半。回归2
直到left(左边缘)>right(右边缘)，再把第i个元素前1位与目标位置之间的所有元素后移。
最后，把第i个元素放在目标位置上。

def insert_2_sort(nums): for i in range(1, len(nums)): left = 0 right = i - 1 key = nums[i]while left <= right: middle = (left+right)//2 if key > nums[middle]: left = middle + 1 else: right = middle - 1for j in range(i, left, -1): nums[j] = nums[j-1]nums[left] = keya = [2,3,4,5,1,9,7,6,2,0,6] insert_2_sort(a)

3. 希尔排序

空间复杂度为O(1)
时间复杂度则由增量（步长）而定。
只要最终步长为1任何步长序列都可以工作。
一个好的步长序列评价时间复杂度可以达到O(n^1.5)
shell排序是非稳定排序
提高效率的思想：
因为插入排序的时间复杂度依赖初始序列的顺序，所以通过大步长的排序（时间复杂度低），使序列部分有序，这样当进行小步长排序时，时间复杂度也低。

过程

把记录按下标的一定增量分组
对每组使用直接插入排序算法排序。
减小增量n，若n > 0,进入1；反之，算法终止

def shell(nums): gaps = 3 for gap in range(1, gaps+1): for i in range(gap, len(nums)): key = nums[i] pointer = i - gap while key < nums[pointer] and pointer >= 0: nums[pointer+gap] = nums[pointer] pointer -= gapnums[pointer+gap] = key

4. 选择排序

空间复杂度为O(1)
时间复杂度为O(n^2)
对比冒泡排序，它少了很多的交换步骤。
不稳定的排序方式

过程：

从待排序的数据元素中选出最小（或最大）的一个元素。
存放在序列的起始位置，直到全部待排序的数据元素排完。
类似冒泡排序。

def selection_sort(nums): for i in range(0, len(nums)): lowest = i for j in range(i, len(nums)): if nums[j] < nums[lowest]: lowest = j nums[lowest], nums[i] = nums[i], nums[lowest]

5. 冒泡排序

时间复杂度为O(n^2)
空间复杂度为O(1)
稳定的排序方法
优化：
如果一个forloop没有发生一次交换，说明已经排好了，可以停止了后面的循环了。
在一次loop中记录最后一次交换的位置，那么该位置后面数一定都是排好了的。所以这一部分就不用参与下面的比较了。

过程：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
------百度百科

def bubble_sort(nums): for i in range(1, len(nums)): for j in range(0, len(nums)-i): if nums[j+1] < nums[j]: nums[j+1], nums[j] = nums[j], nums[j+1]a = [9,3,2,7,1,8,0,4,10,6] bubble_sort(a) print(a)

6. 鸡尾酒排序/双向冒泡排序

空间复杂度为：O(1)
平均和最差的时间复杂度为O(n^2)，但如果序列在一开始已经大部分排序过的话，趋近于O(n)。
原因：双向排序可以避免大量小的数在最右边而小数移动缓慢的情况（升序）

过程：

传统冒泡气泡排序的双向进行，先让气泡排序由左向右进行
再来让气泡排序由右往左进行，如此完成一次排序的动作
使用left与right两个旗标来记录左右两端已排序的元素位置：
当left = right时：结束
否则：继续1

def bubble_sort(nums): left = 1 right = len(nums) while left < right: for i in range(0, len(nums)-left): if nums[i+1] < nums[i]: nums[i+1], nums[i] = nums[i], nums[i+1] left += 1 for j in range(len(nums)-1, len(nums)-right, -1): if nums[j] < nums[j-1]: nums[j], nums[j-1] = nums[j-1], nums[j] right -= 1