排序算法的统一视角
本系列文章尝试从'问题拆分 + 基准情况 + 组合解'这个统一视角出发，理解各种排序。
问题求解流程
- 第一步：原问题怎么拆分？
- 第二步：最小的子问题是什么？
- 第三步：如何组合子问题的解得到原问题的解？
选择排序
子问题定义
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 个元素。
基准情况
表示当前要排序的子区间是 的长度为 0，且区间 已有序。因为空集是有序的，所以该问题已解决，不用继续拆分了。
