Box
Box
Posts List
  1. 对比
    1. 快速排序
    2. 归并排序
    3. 堆排序
    4. link

主要排序算法

对比

算法 稳定性 平均时间复杂度 最优时间复杂度 最坏时间复杂度 空间复杂度 备注
快速排序 x NlogN NlogN N^2 logN
归并排序 NlogN NlogN NlogN N
堆排序 x NlogN NlogN NlogN 1 无法利用局部性原理

快速排序

  • 快速排序使用分治法策略来把一个序列分为两个子序列
  • 步骤:
    1. 从数列中挑出一个元素,称为“基准”
    2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分割结束之后,该基准就处于数列的中间位置。这个称为分割操作。
    3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def quick_sort(array):
def sort_recursion(array, left, right):
if left >= right: return # 递归停止
i, j = left, right
flag = array[left] # 取首位为对比标志值
while i < j: # 找flag的最终位置
while i < j and array[j] >= flag: # 用j向左扫描找小于flag的记录
j -= 1
if i < j:
array[i] = array[j] # 小记录移到左边
i += 1
while i < j and array[i] <= flag: # 用i向右扫描找大于flag的记录
i += 1
if i < j:
array[j] = array[i] # 大记录移到右边
j -= 1
array[i] = flag # 将对比的标志位存入其最终位置
sort_recursion(array, left, i - 1) # 左边
sort_recursion(array, i + 1, right) # 右边

sort_recursion(array, 0, len(array) - 1)

归并排序

  • 指的是将两个已经排序的序列合并成一个序列的操作
  • 递归法(自顶向下):
    1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
    2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
    3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
    4. 重复步骤3直到某一指针到达序列尾
    5. 将另一序列剩下的所有元素直接复制到合并序列尾
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def merge_sort(array):
def merge(left, right): # 归并
tmp = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
tmp.append(left[i])
i += 1
else:
tmp.append(right[j])
j += 1
tmp += left[i:]
tmp += right[j:]
return tmp

length = len(array)
if length < 2: # 递归中止
return array
else:
mid = length // 2
left, right = merge_sort(array[:mid]), merge_sort(array[mid:]) # 递归
return merge(left, right) # 归并

堆排序

  • 指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。
  • 在堆的数据结构中,堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作:
    • 最大堆调整:将堆的末端子节点作调整,使得子节点永远小于父节点
    • 创建最大堆:将堆中的所有数据重新排序
    • 堆排序:移除位在第一个数据的根节点,并做最大堆调整的递归运算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def heap_sort(array):
def sift_down(start, end):
root = start
while True:
child = 2 * root + 1
if child > end: break
if child + 1 <= end and array[child] < array[child + 1]: # 找出两个child中较大的那个
child += 1
if array[root] < array[child]: # 最大堆小于较大的child,交换
array[root], array[child] = array[child], array[root]
root = child # 正在调整的节点设置为root
else:
break # 无序调整的时候退出

# 创建最大堆
for start in range(len(array) // 2 - 1, -1, -1):
sift_down(start, len(array) - 1)
# 堆排序
for end in range(len(array) - 1, 0, -1):
array[0], array[end] = array[end], array[0]
sift_down(0, end - 1)
return array

Supporting
Scan, Support Daidai
  • WeChat scan
  • Alipay scan