排序算法的统一视角
本系列文章尝试从'问题拆分 + 基准情况 + 组合解'这个统一视角出发，理解各种排序。
问题求解流程
- 第一步：原问题怎么拆分？
- 第二步：最小的子问题是什么？
- 第三步：如何组合子问题的解得到原问题的解？
选择排序
子问题定义
selectionSort(arr, start)：表示当前要排序的子区间是 arr[start...n-1]
初始子问题 (原问题)
selectionSort(arr, 0)：表示当前要排序的子区间是 arr[0...n-1]
基准情况
start >= n-1 表示当前要排序的子区间是 arr[start...n-1] 的长度为 0 或者 1。因为单个元素或者空集是有序的，所以该问题已解决，不用继续拆分了。
问题拆分
拆分前：selectionSort(arr, start)
目标：保证位置 start 对应的元素已在其最终位置上。
操作：从左向右遍历未排序区间，找到最小值，与未排序区间的首个元素交换
拆分后：selectionSort(arr, start+1)
组合子问题的解
无
冒泡排序
子问题定义
bubbleSort(arr, start)：表示当前要排序的子区间是 arr[start...n-1]
初始子问题 (原问题)
bubbleSort(arr, 0)：表示当前要排序的子区间是 arr[0...n-1]
基准情况
start >= n-1 表示当前要排序的子区间是 arr[start...n-1] 的长度为 0 或者 1。因为单个元素或者空集是有序的，所以该问题已解决，不用继续拆分了。
问题拆分
拆分前：bubbleSort(arr, start)
目标：保证位置 start 对应的元素已在其最终位置上。
操作：从右向左遍历未排序区间 arr[start...n-1]，不断比较相邻元素，如果逆序就交换，最终使得最小值冒泡到该区间的左侧。
拆分后：bubbleSort(arr, start+1)
组合子问题的解
无
插入排序
子问题定义
insertSort(arr, start)：
- 表示当前要排序的子区间是
arr[start...n-1] - 区间
arr[0...start-1]已有序
初始子问题 (原问题)：
insertSort(arr, 1)：
- 表示当前要排序的子区间是
arr[1...n-1] - 区间
arr[0...0]已有序，因为此时该区间只有 1 个元素。
基准情况
start >= n 表示当前要排序的子区间是 arr[n...n-1] 的长度为 0，且区间 arr[0...start-1] 已有序。因为空集是有序的，所以该问题已解决，不用继续拆分了。
问题拆分
拆分前：insertSort(arr, start)
目标：保证位置 start 对应的元素已在其最终位置上。
操作：取未排序区间 arr[start...n-1] 的首个元素 arr[start]，从已有序区间 arr[0...start-1] 中找到其正确的插入位置，将其插入。
拆分后：insertSort(arr, start+1)
组合子问题的解
无
归并排序
子问题定义
mergeSort(arr, left, right)：表示当前要排序的子区间是 arr[left...right]
初始子问题 (原问题)
mergeSort(arr, 0, n-1)：表示当前要排序的子区间是 arr[0...n-1]
基准情况
left >= right：表示当前要排序的子区间是 arr[left...right]，它的长度为 1 或者 0，因为单个元素或者空集是有序的，不用继续拆分了。
问题拆分
拆分前：mergeSort(arr, left, right)
操作：取区间的中点 mid = left + (right-left)/2。
拆分后：mergeSort(arr, left, mid) 和 mergeSort(arr, mid+1, right)
组合子问题的解
合并，即两个有序的子区间 arr[left...mid] 和 arr[mid+1...right] 合并成一个整体有序的区间 arr[left...right]。
堆排序
子问题定义
heapSort(arr, heapSize)：
- 当前要排序的子区间是
arr[0...heapSize-1]
区间划分状态：
- 区间
arr[0...heapSize-1]已经是一个合法的堆 - 区间
arr[heapSize..n-1]已有序，且每个元素都在最终位置上
初始子问题 (原问题)
heapSort(arr, n)：
- 当前要排序的子区间是
arr[0...n-1]
区间划分状态：
- 区间
arr[0...n-1]已经是一个合法的堆 - 区间
arr[n..n-1]已有序，且每个元素都在最终位置上
基准情况
heapSize<=1
heapSort(arr, 1)：
- 当前要排序的子区间是
arr[0...0]
区间划分状态：
- 区间
arr[0...0]已经是一个合法的堆 - 区间
arr[1..n-1]已有序，且每个元素都在最终位置上
问题拆分
拆分前：heapSort(arr, heapSize)
目标：将当前堆区间的最大值放在其最终位置 heapSize-1 上
操作：
- 将当前堆区间
arr[0, heapSize-1]的最大值跟arr[heapSize-1]交换 heapSize--;- 对缩小后的堆区间
arr[0,heapSize-1]执行下沉操作，以恢复堆性质
拆分后：heapSort(arr, heapSize-1)
组合子问题的解
无
快速排序
子问题定义
quickSort(arr, left, right)：表示当前要排序的子区间是 arr[left...right]
初始子问题 (原问题)
quickSort(arr, 0, n-1)：表示当前要排序的子区间是 arr[0...n-1]
基准情况
left >= right：表示当前要排序的子区间是 arr[left...right]，它的长度为 1 或者 0，因为单个元素或者空集是有序的，不用继续拆分了。
问题拆分
拆分前：quickSort(arr, left, right)
目标：先让区间中的一个元素 (基准元素) 归位到其最终有序位置，后再拆分
操作：
- 选择
arr[right]为基准元素pivot。 - 借助某种高效的划分机制，使得基准元素归位到其最终有序位置
pivotIndex。 - 使得所有小于等于
pivot的元素都在其左侧，所有大于pivot的元素都在其右侧。
拆分后：quickSort(arr, left, pivotIndex-1) 和 quickSort(arr, pivotIndex+1, right)
组合子问题的解
无
