算法复杂度速查：https://www.jianshu.com/p/2bae94d4ea9b
快速排序是二叉树的前序遍历，归并排序是二叉树的后序遍历
排序算法的稳定性指的是在排序过程中，能够保证相等元素在排序后的相对位置与排序前一致。
一、稳定排序算法
- 冒泡排序：
- 重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
- 在这个过程中，相等元素不会交换位置，所以是稳定排序。
- 插入排序：
- 对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
- 当遇到相等元素时，会插入到相等元素的后面，不会改变相等元素的相对顺序，所以是稳定排序。
- 归并排序：
- 采用分治的思想，将数列分成两部分，分别排序后再进行合并。
- 在合并过程中，如果两个元素相等，会按照它们在原始数列中的顺序依次放入结果数列中，所以是稳定排序。
二、不稳定排序算法
- 选择排序：
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 每次选择最小元素时，可能会改变相等元素的相对位置，所以是不稳定排序。
- 快速排序：
- 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。
- 在分区过程中，可能会改变相等元素的相对位置，所以是不稳定排序。
- 希尔排序：
- 也称递减增量排序算法，是插入排序的一种更高效的改进版本。
- 由于多次插入排序，不同的步长可能会导致相等元素的相对位置发生变化，所以是不稳定排序。
遍历顺序
1、遍历的过程中，所需的状态必须是已经计算出来的。
2、遍历结束后，存储结果的那个位置必须已经被计算出来。
归并排序
分治法
- mergesort()： 分，从中间分离array，分别排序（递归），最后调用merge合并
- merge()：治，将2个array合并为一个有序array，返回有序array
- 若2个array都还有，依次填入
- 若有一个遍历结束，按序填入
def mergesort(arr):
if len(arr)<=1:
return arr
mid = int(len(arr)/2)
left = mergesort(arr[0:mid])
right = mergesort(arr[mid:])
return merge(left,right)
def merge(left,right):
l = 0
r = 0
res = []
while( l<len(left) and r < len(right)):
if left[l]<= right[r]:
res.append(left[l])
l +=1
else:
res.append(right[r])
r +=1
if ( l<len(left) ):
res.extend(left[l:])
if ( r<len(right) ):
res.extend(right[r:])
return res
快速排序
快速排序的过程是一个构造二叉搜索树的过程。 快排是不稳定排序。
为了避免最坏情况，引入随机 pivot。
更快的做法：
在 partition 过程中，把 left 作为 pivot，左右同时交换，最终，把l=r 后，r 和pivot（left）交换，返回 r。
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return self.quickselect(nums, 0, len(nums)-1, k-1)
def partition(self, nums, left, right):
pivot = nums[left]
l = left+1
r = right
while (l <=r):
if (nums[l]< pivot and nums[r]> pivot):
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
if nums[l]>= pivot:
l += 1
if nums[r] <= pivot:
r -= 1
nums[left], nums[r] = nums[r], nums[left]
return r
def quickselect(self, nums, left, right, k):
index = self.partition(nums, left, right)
if index==k:
return nums[k]
elif index<k:
return self.quickselect(nums, index+1, right, k)
elif index >k:
return self.quickselect(nums, left, index-1, k )
做法：此算法较慢，无法通过leetcode
在l和r之间，把较小的数换在前面，然后放置pivot，返回pivot的index。
- 把right定位pivot
- 从left到i之间，为小于pivot的数
- j遍历left～right，如果违背，将j处的小数换到前边i的位置。
def quicksort(arr,left,right):
if left<right:
if len(arr)<=1:
return
idx = partition(arr,left, right)
quicksort(arr,left,idx-1)
quicksort(arr,idx+1,right)
def partition(arr,left,right):
pivot = arr[right]
index = left
for j in range(left,right):
if arr[j]<pivot:
arr[i], arr[j] = arr[j], arr[i]
index+=1
arr[index], arr[right] = arr[right], arr[index]
return i+1
arr = [12,1,7,3,5,6]
quicksort(arr,0,len(arr)-1)
print(arr)
quickselect算法
class Solution:
def smallestK(self, arr: List[int], k: int) -> List[int]:
if len(arr)==0 or k==0:
return list()
return self.quicksort(arr, 0, len(arr)-1, k)
def partition(self, arr, left, right, k):
pivot_value = arr[right]
index = left
for j in range(left, right):
if arr[j] < pivot_value:
arr[index], arr[j] = arr[j], arr[index]
index +=1
arr[index], arr[right] = arr[right], arr[index]
return index
def quickselect(self,arr, left,right, k):
if left==right:
return arr[:k]
index = self.partition(arr, left, right, k)
if index ==k:
return arr[:k]
elif index<k:
return self.quicksort(arr, index+1, right, k)
elif index>k:
return self.quicksort(arr, left, index-1, k)
堆排序
步骤（以升序排序为例）：
- 构造一个大顶堆
- 再将大顶堆的的头尾元素互换（此步骤是为了模拟逐个出队的过程）
def max_heapify(heap,heapSize,root): # 调整列表中的元素并保证以root为根的堆是一个大根堆
'''
给定某个节点的下标root，这个节点的父节点、左子节点、右子节点的下标都可以被计算出来。
父节点：(root-1)//2
左子节点：2*root + 1
右子节点：2*root + 2 即：左子节点 + 1
'''
left = 2*root + 1
right = left + 1
larger = root
if left < heapSize and heap[larger] < heap[left]:
larger = left
if right < heapSize and heap[larger] < heap[right]:
larger = right
if larger != root: # 如果做了堆调整则larger的值等于左节点或者右节点的值，这个时候做堆调整操作
heap[larger], heap[root] = heap[root], heap[larger]
# 递归的对子树做调整
max_heapify(heap, heapSize, larger)
def build_max_heap(heap): # 构造一个堆，将堆中所有数据重新排序
heapSize = len(heap)
for i in range((heapSize -2)//2,-1,-1): # 自底向上建堆
max_heapify(heap, heapSize, i)
import random
def heap_sort(heap): # 将根节点取出与最后一位做对调，对前面len-1个节点继续进行堆调整过程。
build_max_heap(heap)
# 调整后列表的第一个元素就是这个列表中最大的元素，将其与最后一个元素交换，然后将剩余的列表再递归的调整为最大堆
for i in range(len(heap)-1, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
max_heapify(heap, i, 0)
# 测试
if __name__ == '__main__':
a = [30, 50, 57, 77, 62, 78, 94, 80, 84]
print(a)
heap_sort(a)
print(a)
b = [random.randint(1,1000) for i in range(1000)]
print(b)
heap_sort(b)
print(b)
python中 heapq 的使用
注意默认为小顶堆，如果需要大顶堆，需要用负值。
import heapq
# 创建一个列表
data = [5, 7, 9, 1, 3]
# 将列表转换为堆
heapq.heapify(data)
print("Heapified data:", data) # 输出: [1, 3, 9, 7, 5]
# 向堆中添加元素
heapq.heappush(data, 4)
print("After heappush(4):", data) # 输出: [1, 3, 4, 7, 5, 9]
# 从堆中删除并返回最小元素
smallest = heapq.heappop(data)
print("Popped smallest element:", smallest) # 输出: 1
print("After heappop():", data) # 输出: [3, 5, 4, 7, 9]
# 获取堆中的最小元素，但不删除
smallest_peek = data[0]
print("Peek smallest element:", smallest_peek) # 输出: 3
# 从堆中删除并返回最小元素，推入新的元素
smallest_replaced = heapq.heapreplace(data, 2)
print("Replaced smallest element:", smallest_replaced) # 输出: 3
print("After heapreplace(2):", data) # 输出: [2, 5, 4, 7, 9]
# 获取前 n 个最小的元素
three_smallest = heapq.nsmallest(3, data)
print("Three smallest elements:", three_smallest) # 输出: [2, 4, 5]
# 获取前 n 个最大的元素
three_largest = heapq.nlargest(3, data)
print("Three largest elements:", three_largest) # 输出: [9, 7, 5]
