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] = temp
nums = [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 - 1
for j in range(i, left, -1):
nums[j] = nums[j-1]
nums[left] = key
a = [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 -= gap
nums[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
