使用python实现归并排序、快速排序、堆排序
Nolinked 人气:0归并排序
使用分治法:分而治之
分:
- 递归地拆分数组,直到它被分成两对单个元素数组为止.
- 然后,将这些单个元素中的每一个与它的对合并,然后将这些对与它们的对等合并,直到整个列表按照排序顺序合并为止.
治:
- 将2个排序列表合并为另一个排序列表是很简单的.
- 简单地通过比较每个列表的头,删除最小的,以加入新排序的列表.
- O(n) 操作
图示:
动图:
实现
# 合并 def merge(a, b): c = [] while len(a) > 0 and len(b) > 0: if a[0] < b[0]: c.append(a[0]) a.remove(a[0]) else: c.append(b[0]) b.remove(b[0]) if len(a) == 0: c += b else: c += a return c # 排序 def merge_sort(li): if len(li) <= 1: return li # 整除2 m = len(li) // 2 a = merge_sort(li[:m]) b = merge_sort(li[m:]) return merge(a, b)
算法分析
- 平均时间复杂度:O(nlog2n)
- 最好时间复杂度:O(nlog2n)
- 最坏时间复杂度:O(nlog2n)
- 空间复杂度:O(n)
- 稳定性:稳定的
快速排序
从数列中挑出一个元素,称为 “基准”(pivot);
重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。
在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;
实现
简易版
# 快速排序1 def quick_sort_one(li): if len(li) <= 1: return li v = li[0] left = quick_sort_one([i for i in li[1:] if li[i] <= v]) right = quick_sort_one([i for i in li[1:] if li[i] > v]) return left + v + right
partition分区
import random def quick_sort(li, left, right): if left < right: # 待排序的区域至少有两个元素 mid = partition(li, left, right) quick_sort(li, left, mid - 1) quick_sort(li, mid + 1, right) # partition分区 def partition(li, left, right): tmp = li[left] while left < right: while left < right and li[right] >= tmp: right -= 1 li[left] = li[right] while left < right and li[left] <= tmp: left += 1 li[right] = li[left] li[left] = tmp return left li = list(range(100)) random.shuffle(li) quick_sort(li, 0, len(li) - 1) print(li)
算法分析
- 平均时间复杂度:O(nlog2n)
- 最好时间复杂度:O(nlog2n)
- 最坏时间复杂度:O(n2)
- 空间复杂度:O(nlog2n)
- 稳定性:不稳定的
堆排序
- 建立堆
- 得到堆顶元素,为最大元素
- 去掉堆顶,将堆最后一个元素放到堆顶,此时可通过一次调整重新使对有序
- 堆顶元素为第二大元素
- 重复步骤3,直到堆为空,排序结束
实现
import random def sift(li, low, high): # li表示树, low表示树根, high表示树最后一个节点的位置 tmp = li[low] i = low j = 2 * i + 1 # 初识j指向空位的左孩子 # i指向空位,j指向两个孩子 while j <= high: # 循环退出的第二种情况: j>high,说明空位i是叶子节点 if j + 1 <= high and li[j] < li[j + 1]: # 如果右孩子存在并且比左孩子大,指向右孩子 j += 1 if li[j] > tmp: li[i] = li[j] i = j j = 2 * i + 1 else: # 循环退出的第一种情况:j位置的值比tmp小,说明两个孩子都比tmp小 break li[i] = tmp def heap_sort(li): n = len(li) # 1. 构造堆 for low in range(n // 2 - 1, -1, -1): sift(li, low, n - 1) # 2. 挨个出数 for high in range(n - 1, -1, -1): li[0], li[high] = li[high], li[0] # 退出 棋子 sift(li, 0, high - 1) li = list(range(100)) random.shuffle(li) heap_sort(li) print(li)
算法分析
- 平均时间复杂度:O(nlog2n)
- 最好时间复杂度:O(nlog2n)
- 最坏时间复杂度:O(nlog2n)
- 空间复杂度:O(1)
- 稳定性:不稳定的
~>.<~
加载全部内容