[数据结构与算法] 排序算法

文章目录

排序1. 冒泡排序2. 插入排序3. 选择排序4. 希尔排序5. [归并排序](https://zh.wikipedia.org/wiki/归并排序)6. 快速排序7. [堆排序](https://zh.wikipedia.org/wiki/堆排序)8. 计数排序 显卡拿去修理这段时间就复习下数据结构与算法吧. = =! 不然要失业了!

参考资料: [1] 数据结构与算法 python语言描述 裘宗燕 [2] 维基百科 排序算法

排序

1. 冒泡排序

每一步都通过交换，把大的数后移。每一轮都有一个大的数字就位。

def bubble_sort(list): n = len(list) # 每一轮选出一个最大的数值的沉入数组的尾端 for i in range(n-1): flag = True # 在第i轮，剩余数组的长度为n-i，由于两两比较，所以比较次数为剩余数组长度再减一。 for j in range(n-i-1): # 严格大于才会调序，保证算法的稳定性 if list[j] > list[j+1]: list[j], list[j+1] = list[j+1], list[j] # 若发生了调整，则说明当前排序仍未完成 flag = False if flag: return list return list 最坏时间复杂度平均时间复杂度最好时间复杂度空间复杂度稳定性适应性$O(n^2)$$O(n^2)$$O(n)$$O(1)$有有

2. 插入排序

从未排序的序列中选一个数值插入到已排序的序列中

def insert_sort(list): n = len(list) for i in range(n): temp = list[i] empty = i # 取出数值，认为该位置为空 # 空位置左侧的数字大于temp时，右移数字 while empty > 0 and list[empty-1] > temp list[empty] = list[empty-1] # 数字后移后，空位置前移 empty -= 1 # 在空缺位置填入值 list[empty] = temp return list 最坏时间复杂度平均时间复杂度最好时间复杂度空间复杂度稳定性适应性$O(n^2)$$O(n^2)$$O(n)$$O(1)$有有

3. 选择排序

每次从无序的序列中选择一个最小数值，放到已排序序列的末尾

def select_sort(list): n = len(list) for i in range(n): for j in range(i, n): if list[j] < list[i]: list[j], list[i] = list[i], list[j] return list 最坏时间复杂度平均时间复杂度最好时间复杂度空间复杂度稳定性适应性$O(n^2)$$O(n^2)$$O(n^2)$$O(1)$无无

4. 希尔排序

希尔排序以不同的gap进行插入排序.

def shell_sort(list): n = len(list) gap = n // 2 while gap > 0: for i in range(gap, n): temp = list[i] empty = i while empty > gap and list[empty - gap] > temp: list[empty] = list[empty - gap] empty -= gap gap = gap // 2 return list 最坏时间复杂度平均时间复杂度最好时间复杂度空间复杂度稳定性适应性随步长而定随步长而定$O(n)$$O(1)$无有 步长序列最坏时间复杂度$n/2^i$$O(n^2)$$2^k-1$$O(n^{3/2})$$2^i{3}^j$$O(nlo{g}^{2}n)$

5. 归并排序

递归实现

def merge(left, right): result = [] while left and right: if left[0] <= right[0]: result.append(left.pop(0)) else: result.append(right.pop(0)) if left: result += left if right: result += right return result def merge_sort(list): if len(list) <= 1: return list mid = len(list) // 2 left = list[:mid] right = list[mid:] left = merge_sort(left) right = merge_sort(right) return merge(left, right)

迭代实现

def merge(lfrom, lto, low, mid, high): i = low j = mid k = low while i < mid and j < high: if lfrom[i] <= lfrom[j]: lto[k] = lfrom[i] i += 1 else: lto[k] = lfrom[j] j += 1 k += 1 while i < mid: lto[k] = lfrom[i] i += 1 k += 1 while j < high: lto[k] = lfrom[j] j += 1 k += 1 return lfrom, lto def merge_pass(lfrom, llen, slen): i = 0 lto = [None] * len(lfrom) while i + 2 * slen < llen: lfrom, lto = merge(lfrom, lto, i, i+slen, i+2*slen) i += 2 * slen # 剩余两段,第二段长度小鱼slen if i + slen < llen: lfrom, lto = merge(lfrom, lto, i, i+slen, llen) # 只剩余一段,直接复制 else: while i < llen: lto[i] = lfrom[i] i+=1 return lto def merge_sort(lst): slen = 1 llen = len(lst) while slen < llen: lst = merge_pass(lst, llen, slen) slen *= 2 return lst

每经过一遍归并,有序子序列的长度将变成$2^k$,因此归并的遍数不会超过$lo{g}_{2}n+1$,而每遍归并时,比较次数为$O(n)$,因此时间复杂度为$O(nlogn)$

最坏时间复杂度平均时间复杂度最好时间复杂度空间复杂度稳定性适应性$O(nlogn)$$O(nlogn)$$O(nlogn)$$O(n)$有无

6. 快速排序

def quick_rec(lst, b, e): if e <= b: return lst temp = lst[b] i = b j = e while i < j: # 严格加上i<j,否则会侵入已经分好的区域 while i < j and lst[j] > temp: j -= 1 if i < j: lst[i] = lst[j] i += 1 while i < j and lst[i] < temp: i += 1 if i < j: lst[j] = lst[i] j -= 1 lst[i] = temp lst = quick_rec(lst, b, i-1) lst = quick_rec(lst, i+1, e) return lst def quick_sort(lst): return quick_rec(lst, 0, len(lst)-1) 最坏时间复杂度平均时间复杂度最好时间复杂度空间复杂度稳定性适应性$O(n^2)$$O(nlogn)$$O(nlogn)$$O(1)$无无

7. 堆排序

构建一个最大堆,每次从最大堆中去除最大元素,放到数组的末尾,完成排序.

def heap_sort(lst): def sift_down(start, end): """ 从上到下调整节点,若父节点的值小于子节点,交换位置. """ root = start child = 2 * root + 1 while child < end: if child+1 < end and lst[child] < lst[child+1]: child += 1 if lst[child] > lst[root]: lst[root], lst[child] = lst[child], lst[root] root, child = child, 2*child + 1 else: break n = len(lst) # 建最大堆 # len(lst)//2 -1 为最后一个树节点,其子节点都为叶节点 for start in range(n//2-1, -1, -1): sift_down(start, n-1) # 从最大堆中取值 for i in range(n-1, 0, -1): lst[i], lst[0] = lst[0], lst[i] sift_down(0, i-1) return lst 最坏时间复杂度平均时间复杂度最好时间复杂度空间复杂度稳定性适应性$O(nlogn)$$O(nlogn)$$O(nlogn)$$O(1)$无无

8. 计数排序

当待排序序列中,不同数字的个数较少时(例如0-k之间的整数),计数排序是最快的方法.

def count_sort(lst): min_ = min(lst) max_ = max(lst) count = [0] * (max_ - min_ + 1) # 统计每一个数字出现的次数 for num in lst: count[num-min_] += 1 index = 0 # 根据统计的结果,将数值回填到原来的list中 for i, times in enumerate(count): for j in range(times): lst[index] = i + min_ index += 1 return lst 最坏时间复杂度平均时间复杂度最好时间复杂度空间复杂度稳定性适应性$O(n+k)$$O(n+k)$$O(n+k)$$O(n+k)$无无