todo: 疑问：本文实现的快排的时间复杂度是O(n*log2(n))吗
特别鸣谢：来自夸夸群的 醉笑陪公看落花@知乎，王不懂不懂@知乎，QFIUNE@csdn
感谢醉笑陪公看落花@知乎 倾囊相授，感谢小伙伴们督促学习，一起进步
tips
- 稳定排序
- 冒泡排序
- 归并排序
- 插入排序
- 不稳定的排序
- 快排排序
- 选择排序
上图来源 https://www.cnblogs.com/xiaochun126/p/5086037.html
下面介绍集中排序算法的实现，从小到大排序
归并排序 O(n*log2(n))
- 分：把列表一分为二，得到两个有序列表
- 治：合并两个有序列表
递归地拆分列表，当拆分出来的列表只含有单个元素的时候，自然是有序的，可以作为递归的终止条件
'''
归并排序
'''
def mergeSort(nums):
if len(nums)==1:
return nums
s = len(nums)//2
sa,sb = mergeSort(nums[:s]),mergeSort(nums[s:])
ans = doMerge(sa,sb)
return ans
def doMerge(sa,sb):
ans = []
i = j = 0
while(i<len(sa) and j <len(sb)):
if sa[i]<=sb[j]: # 等号保证排序稳定（元素相等的时候，sb中的元素插在后面）
elem = sa[i]
i+=1
else:
elem = sb[j]
j+=1
ans.append(elem)
ans.extend(sa[i:])
ans.extend(sb[j:])
return ans
堆排序
堆的性质
堆的实现通过构造二叉堆（binary
heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质。
- 任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
- 堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
来源维基百科 堆积 性质
由此可知，大根堆的子树也是大根堆
用数组存一棵完全二叉树，通过下标获取某个已知节点的关联节点
若数组下标从0开始
- 已知父节点为
i, 则左孩子为：2i+1，右孩子为2i+2 - 已知孩子节点为
j，则父节点为(j-1)//2
若数组下标从1开始
- 已知父节点为
i, 则左孩子为：2i，右孩子为2i+1 - 已知孩子节点为
j，则父节点为j//2
本文大根堆数组下标都从0开始
方案1 自底向上调整大根堆O(n^2)
从最后一个非叶结点开始调整，让这个节点比后裔大，一直到root节点比后裔大，再将root节点放在末尾。 这样，最大的数就排在了数组的末尾。再把倒数第二大的数字，放在数组倒数第二的位置，依此类推。
'''
堆排序 -- 自底向上调整
目前时间复杂度：O(n^2)
'''
def heapSort(nums):
for end in range(len(nums)-1,-1,-1):
doheapSort(nums,end)
return nums
def doheapSort(nums,end):
root = (end-1) // 2 # 最后一个非叶节点的下标
while(root>=0):
left = root*2+1
right = root*2+2
if nums[left]>nums[root]:
nums[left], nums[root] = nums[root],nums[left]
if nums[right] > nums[root] and right<=end:
nums[right], nums[root] = nums[root], nums[right]
root-=1
# root -1 # 倒数第二个非叶节点的下标
nums[0], nums[end] = nums[end], nums[0]
方案2 自顶向下调整大根堆O(n*log2(n))
先构建一个大根堆（每一个节点都大于等于后裔），把root和数组末尾的值交换，再自顶向下调整（末尾这个数字已经是确保是最大值，因此下一次大根堆的数组不包括原来数组基础上的末尾元素）
'''
O(n*log2(n))
'''
def heapSort(nums): # O(n * log2(n))
generateBigheap(nums) # O(n * log2(n))
for end in range(len(nums)-1,-1,-1): # O(n * log2(n))
nums[0], nums[end] = nums[end], nums[0]
down_adjust(nums,0,end-1)
return nums
def generateBigheap(nums): # O(n * log2(n))
for root in range((len(nums)-2)//2,-1,-1):
print(root)
left = root*2+1
right = left+1
maxelem = left if right>len(nums)-1 or nums[right]<nums[left] else right
if nums[root]>nums[maxelem]:continue
nums[maxelem], nums[root] = nums[root], nums[maxelem]
down_adjust(nums, maxelem,len(nums)-1)
def down_adjust(nums,root,end): # O(log2(n))
while root * 2 + 1 <end:
left = root * 2 + 1
right = left + 1
maxelem = left if right>end or nums[right]<nums[left] else right
if nums[root] > nums[maxelem]: break
nums[maxelem], nums[root] = nums[root], nums[maxelem]
root = maxelem
快排 O(n*log2(n))
主要用到了基准元素和双指针，以及递归思想
- 双指针移动和 leetcode 11,42,407, 容器，接雨水，二维雨水，坑 文中对墙的移动相似。本文中每次数组被修改位置的指针，向着另一个指针的方向挪动1位
- 双指针每一次碰头的时候，基准元素到达了最终位置。草图中展示了双指针一次碰头的过程。
- 找到了最终位置的基准元素将列表一分为二，下一步需要递归地去找下一个基准元素的位置，直到找到所有的基准元素
快排草图
def quickSort(nums,start,end):
i = start
j = end
if start>=end:return
base = i
b = nums[base]
while i<j:
while nums[j] >= b and i<j:j-=1
nums[i] = nums[j]
while nums[i]<=b and i<j:i+=1
nums[j] = nums[i]
nums[i] = b
quickSort(nums,start,j-1)
quickSort(nums,j+1,end)
ans = quickSort(nums,0,len(nums)-1)