sort
几个概念
- 执行效率
- 内存消耗
原地排序/Sorted in place
原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。冒泡、插入、选择，都是原地排序算法。 - 稳定性
仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，我们还有一个重要的度量指标，稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
例如有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9，这组数据里有两个 3。 经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。
冒泡排序
第一轮排序(i = 0)将最大的元素移到最右边
第二轮排序(i = 1)将第二大的元素移到倒数第二个位置
以此类推..
func bubbleSort(arr []int) {
for i := 0; i < len(arr); i++ {
var flag bool
for j := 0; j < len(arr)-1-i; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
flag = true
}
}
// 没有数据交换，提前退出
if !flag {
return
}
}
}
insertion sort
左边是已排序区间，右边是未排序区间。 取
arr[j]与已排序区间[0, j-1]进行比较，插入相应位置
func insertionSort(arr []int) {
for i := 1; i < len(arr); i++ {
for j := i; j > 0; j-- {
if arr[j] >= arr[j-1] {
break
}
arr[j], arr[j-1] = arr[j-1], arr[j]
}
}
}
选择排序
第一轮排序(i = 0)找出最小的元素放到 a[0]
第二轮排序(i = 1)从未排序区间找出最小的元素放到 a[i]
func selectionSort(arr []int) {
for i := 0; i < len(arr)-1; i++ {
minIndex := i
for j := i + 1; j < len(arr); j++ {
if arr[j] < arr[minIndex] {
minIndex = j
}
}
arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
}
冒泡排序、插入排序是稳定排序，选择排序是不稳定排序。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。 虽然冒泡排序和插入排序在时间复杂度上是一样的，都是 O(n2)，但是如果我们希望把性能优化做到极致，那肯定首选插入排序。
插入排序的算法思路也有很大的优化空间，希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
冒泡排序、插入排序、选择排序这三种排序算法，它们的时间复杂度都是 O(n2)，比较高，适合小规模数据的排序。
归并排序和快速排序时间复杂度为 O(nlogn)，这两种排序算法适合大规模的数据排序，比上述三种排序算法要更常用。
merge sort
func mergeSort(arr []int) {
var dfs func(int, int)
dfs = func(left, right int) {
if left < right {
mid := left + (right-left)/2
dfs(left, mid)
dfs(mid+1, right)
merge(arr, left, mid, right)
}
}
dfs(0, len(arr)-1)
}
func merge(arr []int, left, mid, right int) {
i, j, k := left, mid+1, 0
temp := make([]int, right-left+1)
for i <= mid && j <= right {
if arr[i] <= arr[j] {
temp[k] = arr[i]
i++
} else {
temp[k] = arr[j]
j++
}
k++
}
// 判断哪个子数组中有剩余的数据
for ; i <= mid; i++ {
temp[k] = arr[i]
k++
}
for ; j <= right; j++ {
temp[k] = arr[j]
k++
}
// 将temp中的数据写入arr
for idx := 0; idx < len(temp); idx++ {
arr[idx+left] = temp[idx]
}
}
归并排序的时间复杂度任何情况下都是 O(nlogn)，但它不是原地排序算法，空间复杂度比较高，是 O(n)。因此，归并排序没有快排应用广泛。
归并是稳定排序，快排是不稳定排序。
quick sort
func quickSort(arr []int) {
var dfs func(int, int)
dfs = func(start, end int) {
if start < end {
p := partition(arr, start, end)
dfs(start, p-1)
dfs(p+1, end)
}
}
dfs(0, len(arr)-1)
}
func partition(arr []int, start, end int) int {
pivot := arr[start]
i, j := start+1, end
for i <= j {
// i 往右走，直到遇到大于主元的元素
for ; i <= j && arr[i] <= pivot; i++ {
}
// j 往左走，直到遇到小于主元的元素
for ; i <= j && arr[j] >= pivot; j-- {
}
if i < j {
arr[i], arr[j] = arr[j], arr[i]
}
}
arr[start], arr[j] = arr[j], arr[start]
return j
}
快排利用的也是分治思想。
快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
归并排序由下到上，先处理子问题，然后合并。
而快排是由上到下，先分区，然后再处理子问题。
快排虽然最坏情况下的时间复杂度是 O(n2)，但是平均情况下时间复杂度都是 O(nlogn)。 不仅如此，快排时间复杂度退化到 O(n2) 的概率非常小，我们可以通过合理地选择 pivot 来避免这种情况。
合理选择分区点
如果数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数据，那快速排序算法就会变得非常糟糕，时间复杂度就会退化为 O(n2)。 最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。
三数取中法
从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点。这样每间隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。
但是，如果要排序的数组比较大，那“三数取中”可能就不够了，可能要“五数取中”或者“十数取中”。
随机法
每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选的很差的情况，所以平均情况下，这样选的分区点是比较好的。时间复杂度退化为最糟糕的 O(n2) 的情况，出现的可能性不大。
警惕堆栈溢出
快排是用递归实现的，递归要警惕堆栈溢出。为了避免快速排序里，递归过深而堆栈过小，导致堆栈溢出，我们有两种解决办法：
第一种是限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归。
第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制。
TimSort
查看了下 Arrays.sort 的源码，主要采用 TimSort 算法, 大致思路是这样的：
- 元素个数 < 32, 采用二分查找插入排序(Binary Sort)
- 元素个数 >= 32, 采用归并排序，归并的核心是分区(Run)
- 找连续升或降的序列作为分区，分区最终被调整为升序后压入栈
- 如果分区长度太小，通过二分插入排序扩充分区长度到分区最小阙值
- 每次压入栈，都要检查栈内已存在的分区是否满足合并条件，满足则进行合并
- 最终栈内的分区被全部合并，得到一个排序好的数组
Timsort 的合并算法非常巧妙：
- 找出左分区最后一个元素(最大)及在右分区的位置
- 找出右分区第一个元素(最小)及在左分区的位置
- 仅对这两个位置之间的元素进行合并，之外的元素本身就是有序的
线性排序
桶排序/Bucket sort
桶排序对要排序数据的要求：
首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。
在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。
桶排序比较适用于外部排序。 外部排序是指数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
例：有 10GB 的订单数据，需要按订单金额（假设金额都是正整数）进行排序，但是内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。
先扫描一遍文件，看订单金额所处的数据范围。假设范围为 1~10 万元。将所有订单根据金额划分到 100 个桶里，第一个桶存储 1~1000 元的订单，第二桶存储 1001~2000 元的订单，以此类推。 每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02…99）。
理想的情况下，如果订单金额在 1~10 万之间均匀分布，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的订单数据，即可将这 100 个小文件依次放到内存中，用快排来排序。 所有文件排好序后，按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。
但是，订单金额在 1~10 万元之间并不一定是均匀分布的，所以 10GB 订单数据是无法均匀划分到 100 个文件中的。可能某个金额区间的数据特别多，划分后对应的文件就会很大，没法一次性读入内存。 此时可以继续划分。比如，订单金额在 1~1000 元之间的比较多，则继续划分为 10 个小区间，1~100 元，101~200 元，201~300 元…901~1000 元。 若划分之后，101~200 元之间的订单还是太多，无法一次性读入内存，那就再继续划分，直到所有的文件都能读入内存为止。
计数排序/Counting sort
计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
高考查分数系统,查分数时，系统会显示成绩以及所在省的排名。如果你所在的省有 50 万考生，如何通过成绩快速排序得出名次呢？
假设满分是 900 分，最小是 0 分，这个数据的范围很小，可分成 901 个桶，对应分数从 0 分到 900 分。根据成绩，将这 50 万考生划分到这 901 个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 50 万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是 O(n)。
基数排序/Radix sort
假设我们有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序
手机号码有 11 位，范围太大，不适合用桶排序、计数排序。用快排时间复杂度可以做到 O(nlogn)
这个问题，可用基数排序，时间复杂度为 O(n)。
假设要比较两个手机号码 a，b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大了，那后面的几位就不用看了。
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了