排序算法是非常重要的算法，这里系统的梳理，以下默认得到从小到大的排序结果。
1. 冒泡排序（Bubble Sort）
冒泡排序的思想：
- 每次比较相邻的两个元素，从头两两比较到尾，一次遍历就能最大/小的元素推到最右侧
- 按上述两两比较方式，遍历 n 次，每一次需要遍历的最右侧都累积一个后续遍历不需要参与比较的元素
- 接下来的遍历比较次数逐次减一，如果加入是否已排好序的判断，最佳情况一次遍历即可得到结果
冒泡排序只在不符合大小顺序时才进行元素交换，且交换不影响其他元素，所以属于稳定排序算法。
# -*- coding:utf-8 -*-
# Time Complexity: O(n^2)
# Space Complexity: O(1)
class BubbleSort:
def bubbleSort(self, A, n):
# write code here
for i in range(n):
for j in range(1, n-i):
if A[j-1] > A[j]:
A[j-1], A[j] = A[j], A[j-1]
return A
当然可以在此基础上做一点优化，如果知道数组已经排序完成了，那么后面的交换遍历工作就可以跳过了。这里就在最佳情况下的时候将时间复杂度降到了 $O(n)$。
# -*- coding:utf-8 -*-
# Time Complexity: O(n^2)
# Space Complexity: O(1)
class BubbleSort:
def bubbleSort(self, A, n):
# write code here
for i in range(n):
is_sorted = True
for j in range(1, n-i):
if A[j-1] > A[j]:
A[j-1], A[j] = A[j], A[j-1]
is_sorted = False
if is_sorted:
break
return A
2. 选择排序
选择排序的思想：
- 每次遍历一遍找到最小/最大值，放到最左/最右侧，可以通过记录最小/大值的索引来做比较和交换
- 遍历 n 次，注意每一次遍历对已经找到过的当前极值都避免再次比较和交换
从前往后找最小值的方式：
# -*- coding:utf-8 -*-
# Time Complexity: O(n^2)
# Space Complexity: O(1)
class SelectionSort:
def selectionSort(self, A, n):
# write code here
for i in range(n-1):
min_i = i
for j in range(i+1, n):
if A[min_i] > A[j]:
min_i = j
if min_i != i:
A[i], A[min_i] = A[min_i], A[i]
return A
从后往前找最大值的方式：
# -*- coding:utf-8 -*-
# Time Complexity: O(n^2)
# Space Complexity: O(1)
class SelectionSort:
def selectionSort(self, A, n):
# write code here
for i in range(n-1, 0, -1):
max_i = i
for j in range(i):
if A[max_i] < A[j]:
max_i = j
if max_i != i:
A[i], A[max_i] = A[max_i], A[i]
return A
3. 插入排序
插入排序算法思想：
- 从左到右一个一个取元素，当取到一个新元素时，从跟该元素前一个元素比较开始，也是两两相邻比较交换
- 直到取到最后一个元素位置，需要遍历 n 次
- 遍历过的元素已经是大小排好顺序的，当前元素只是要插入到合适的位置上
因为是相邻元素的比较和交换，所以是稳定的排序算法。
# -*- coding:utf-8 -*-
# Time Complexity: O(n^2)
# Space Complexity: O(1)
class InsertionSort:
def insertionSort(self, A, n):
# write code here
for i in range(1, n):
for j in range(i, 0, -1):
if A[j-1] > A[j]:
A[j-1], A[j] = A[j], A[j-1]
else:
break
return A
4. 归并排序
归并排序的思想：
- 分解：将原问题分解成若干个规模较小、相互独立的子问题，子问题与原问题形式相同
- 解决：子问题相对来说比较容易，此处元级子问题是两个相邻元素进行比较，然后递归扩大子问题规模求解
- 合并：将已解决的子问题结果一层一层递归的合并出最后的结果
其先在子问题中解决后合并，解决时只考虑相邻元素的比较，且合并时不涉及交换，只是按顺序增加，所以稳定
4.1 递归方式
# -*- coding:utf-8 -*-
# Time Complexity: O(nlogn)
# Space Complexity: O(n)
class MergeSort:
def merge(self, left, right):
res = []
while left and right:
if left[0] <= right[0]:
res.append(left.pop(0))
else:
res.append(right.pop(0))
if left:
res += left
if right:
res += right
return res
def mergeSort(self, A, n):
# write code here
if len(A) <= 1:
return A
mid = len(A) >> 1
left = A[:mid]
right = A[mid:]
left = self.mergeSort(left, len(left))
right = self.mergeSort(right, len(right))
return self.merge(left, right)
4.2 迭代方式
比较复杂！
# -*- coding:utf-8 -*-
# Time Complexity: O(nlogn)
# Space Complexity: O(n)
class MergeSort:
def mergeSort(self, A, n):
# write code here
unit = 1
while unit <= len(A):
h = 0
for h in range(0, len(A), unit * 2):
l, r = h, min(len(A), h + 2 * unit)
mid = h + unit
# merge A[h:h + 2 * unit]
p, q = l, mid
while p < mid and q < r:
# use <= for stable merge merge
if A[p] <= A[q]: p += 1
else:
tmp = A[q]
A[p + 1: q + 1] = A[p:q]
A[p] = tmp
p, mid, q = p + 1, mid + 1, q + 1
unit *= 2
return A
5. 快速排序（Quick Sort）
快速排序可以采用分治法：
- 找到一个 pivot，设立两个指针，一个从前往后扫，一个从后往前扫。
- pivot 可以直接选最后一个、第一个或者中间那个值
- 也可以 random 选一个，为了方便要把选的值和数组最后一个数交换位置
- 前指针从前往后扫，直到找到一个比 pivot 大的数，切换到后指针往前扫直到找到一个比 pivot 小的数，此时调换这两个数
- 注意只有当前后指针都找到违反大小顺序的时候才执行
- 重复第二步直到前后指针重合，最后要将 pivot 与汇合的位置点数互换。然后对由 pivot 分隔开的左右两个部分迭代进行排序。
那么这样就可以分成两个部分了，第一是从哪儿切数据，切完之后对两边的数据进行递归求解。
总是遗忘以下几个问题：
- quick_sort 部分忘记
if low < high! - inplace 版本在中间交换时也要判断
low < high。 - 最后忘记 pivot 和标记位置做替换。
写成两个函数的最初版本如下，这个也是 inplace 的版本：
def partition(nums, low, high):
pivot = nums[high]
pos = high
while low < high:
# 这里要含等于 pivot 才能原地
while low < high and nums[low] <= pivot:
low += 1
# 这里注意判断条件是要 low < high，不能是 high > 0，这样会串位置
while low < high and nums[high] >= pivot:
high -= 1
if low < high:
nums[high], nums[low] = nums[low], nums[high]
# 最后这个交换也总忘记
nums[high], nums[pos] = nums[pos], nums[high]
return low
def quick_sort(nums, low, high):
# 总是缺少这个判断条件
if low < high:
pivot = partition(nums, low, high)
quick_sort(nums, low, pivot-1)
quick_sort(nums, pivot+1, high)
上面这种办法在 partition 的时候很明显比较慢，嵌套了两层循环。可以进行优化，我们将两个指针（l 对应 low，h 对应 high）都从最左边开始向右遍历，如果 h 指针所指的数比 pivot 小那么就跟 l 所指的数进行交换，因为 h 遍历时会忽略比 pivot 大的数，l 只在交换后递增，也就是说 l 指向的数应该都是 pivot 大的，如此过程跟上面两重循环的效果一致，可以将 partition 写成下述形式：
def partition(nums, low, high):
i = low
pi = nums[high]
for j in range(low, high):
if nums[j] <= pi:
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[high] = nums[high], nums[i]
return i
为了封装成正常的形式，可以将入口函数改写成如下形式：
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
def _quicksort(arr, low, high):
if low >= high:
return
pivot = partition(arr, low, high)
_quicksort(arr, low, pivot-1)
_quicksort(arr, pivot+1, high)
return _quicksort(arr, low, high)
平均情况下快速排序的时间复杂度是 $O(n\log_2n)$，最坏情况是 $O(n^2)$。
6. 堆排序
堆结构：
- 首先是一个完全二叉树（生成时，从上往下，从左往右）
- 父节点的值大于任一子节点的值（最大堆）
通常堆是通过一维数组来实现的。在数组起始位置为 0 的情形中：
- 父节点 $i$ 的左子节点在位置 ${\displaystyle (2i+1)}$;
- 父节点 $i$ 的右子节点在位置 ${\displaystyle (2i+2)}$;
- 子节点 $i$ 的父节点在位置 ${\displaystyle floor((i-1)/2)}$;
堆排序有如下几步操作：
- 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
- 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
堆排序总是从最后一个元素开始交换、删除、调整，不能保证相同数值元素的相对位置，故不稳定。
6.1 递归方式
# -*- coding:utf-8 -*-
# Time Complexity: O(nlogn)
# Space Complexity: O(n)
class HeapSort:
def heapSort(self, A, n):
# write code here
self.build_heap(A, n)
for i in range(n-1, -1, -1):
A[i], A[0] = A[0], A[i]
self.heapify(A, i, 0)
return A
def heapify(self, A, n, root_i):
# n is the length of A, root_i is the position of parent node
if i >= n:
return
child1 = 2 * root_i + 1
child2 = 2 * root_i + 2
max_i = root_i
if child1 < n and A[child1] > A[max_i]:
max_i = child1
if child2 < n and A[child2] > A[max_i]:
max_i = child2
if max_i != root_i:
A[root_i], A[max_i] = A[max_i], A[root_i]
self.heapify(A, n, max_i)
def build_heap(self, A, n):
last_node = n - 1
parent = (last_node - 1) >> 1
for i in range(parent, -1, -1):
self.heapify(A, n, i)
7. 希尔排序
希尔排序的思想：
- 从元素个数的一半作为间隔开始，每隔这个间距选两个数，比较并交换，使大小顺序符合要求
- 然后再将间隔大小折半，间隔选数比较大小，重复这个过程直到间隔为 1，遍历一遍为止
希尔排序因为两两比较的并非相邻元素，使得相同元素遇到对应不同的比较交换对象，可能发生相对位置的变化。
# -*- coding:utf-8 -*-
# Time Complexity: O(nlogn)
# Space Complexity: O(1)
class ShellSort:
def shellSort(self, A, n):
# write code here
gap = n >> 1
while gap > 0:
for i in range(gap, n):
tmp = A[i]
j = i
# insert sort
while j >= gap and A[j-gap] > tmp:
A[j] = A[j-gap]
j -= gap
A[j] = tmp
gap = gap >> 1
return A
8. 桶排序
桶排序的思想:
- 设置一个定量的数组当作空桶子。
- 寻访序列，并且把项目一个一个放到对应的桶子去。
- 对每个不是空的桶子进行排序。
- 从不是空的桶子里把项目再放回原来的序列中。
复杂度:
- 时间复杂度：最坏 O(n^2)，最佳 O(n+k)
- 空间复杂度：O(n·k)
# -*- coding:utf-8 -*-
# Time Complexity: O(n^2)
# Space Complexity: O(1)
class BucketSort:
def insertionSort(self, A, n):
# write code here
for i in range(1, n):
for j in range(i, 0, -1):
if A[j-1] > A[j]:
A[j-1], A[j] = A[j], A[j-1]
else:
break
return A
def bucketSort(array):
bucket = []
for i in range(len(array)):
bucket.append([])
for j in array:
index_b = int(10 * j)
bucket[index_b].append(j)
for i in range(len(array)):
bucket[i] = self.insertionSort(bucket[i], len(bucket[i]))
k = 0
for i in range(len(array)):
for j in range(len(bucket[i])):
array[k] = bucket[i][j]
k += 1
return array
9. 计数排序
计数排序的思想：
- 找出待排序的数组中最大和最小的元素
- 统计数组中的每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
- 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1
为什么是稳定的？
9.1 只要最大值
# -*- coding:utf-8 -*-
# Time Complexity: O(n)
# Space Complexity: O(n)
class CountingSort:
def countingSort(self, A, n):
# write code here
if not A or len(A) < 2:
return
count_arr = [0 for _ in range(max(A)+1)]
for item in A:
count_arr[item] += 1
idx = 0
for i in range(len(count_arr)):
for cnt in range(count_arr[i]):
A[idx] = i
idx += 1
return A
9.2 最大值-最小值
# -*- coding:utf-8 -*-
# Time Complexity: O(n)
# Space Complexity: O(n)
class CountingSort:
def countingSort(self, A, n):
# write code here
if not A or len(A) < 2:
return
min_val = A[0]
max_val = A[0]
for i in range(1, n):
min_val = min(min_val, A[i])
max_val = max(max_val, A[i])
count_arr = [0 for _ in range(max_val-min_val+1)]
for i in range(n):
count_arr[A[i]-min_val] += 1
idx = 0
for i in range(len(count_arr)):
while count_arr[i] > 0:
count_arr[i] -= 1
A[idx] = i + min_val
idx += 1
return A
10. 基数排序
基数排序的思想：
- 找到最大的数，获取到最大数的数位
- 从低位开始，根据每个数位上数进行排序
- 一个数位一个数位向高位一定，进行每个数位的排序
为什么是稳定的？
# -*- coding:utf-8 -*-
# Time Complexity: O(k*n)
# Space Complexity: O(n)
class RadixSort:
def radixSort(self, A, n):
# write code here
num = max(A)
high = len(str(num))
for k in range(high):
temp = [[] for i in range(10)]
res = []
for i in range(n):
temp[(A[i]/(10**k))%10].append(A[i])
for i in range(10):
for j in range(len(temp[i])):
res.append(temp[i][j])
A = res
return A