一、如何选择合适的排序算法？

排序算法一览表

时间复杂度 是稳定排序？ 是原地排序？
冒泡排序 O(n^2) 是 是
插入排序 O(n^2) 是 是
选择排序 O(n^2) 否 是
快速排序 O(nlogn) 否 是
归并排序 O(nlogn) 是 否
桶排序 O(n) 是 否
计数排序 O(n+k)，k是数据范围 是 否
基数排序 O(dn)，d是纬度 是 否

为什选择快速排序？

1. 线性排序时间复杂度很低但使用场景特殊，如果要写一个通用排序函数，不能选择线性排序。
2. 为了兼顾任意规模数据的排序，一般会首选时间复杂度为O(nlogn)的排序算法来实现排序函数。
3. 同为O(nlogn)的快排和归并排序相比，归并排序不是原地排序算法，所以最优的选择是快排。

二、如何优化快速排序？

导致快排时间复杂度降为O(n)的原因是分区点选择不合理，最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。如何优化分区点的选择？有2种常用方法，如下：

• 三数取中法
  • 从区间的首、中、尾分别取一个数，然后比较大小，取中间值作为分区点。
  • 如果要排序的数组比较大，那“三数取中”可能就不够用了，可能要“5数取中”或者“10数取中”。
• 随机法：每次从要排序的区间中，随机选择一个元素作为分区点。
• 警惕快排的递归发生堆栈溢出，有2中解决方法，如下：
  • 限制递归深度，一旦递归超过了设置的阈值就停止递归。
  • 在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈过程，这样就没有系统栈大小的限制。

三、通用排序函数实现技巧

1. 数据量不大时，可以采取用时间换空间的思路
2. 数据量大时，优化快排分区点的选择
3. 防止堆栈溢出，可以选择在堆上手动模拟调用栈解决
4. 在排序区间中，当元素个数小于某个常数是，可以考虑使用O(n^2)级别的插入排序
5. 用哨兵简化代码，每次排序都减少一次判断，尽可能把性能优化到极致

四、Go语言排序函数的实现

golang标准库中的Sort用的是快排+希尔排序+插排，数据量大于12时用快排，小于等于12时用6作为gap做一次希尔排序，然后走一遍普通的插排（插排对有序度高的序列效率高）。其中快排pivot的选择做了很多工作，是基于首中尾中值的很复杂的变种

func quickSort(data Interface, a, b, maxDepth int) {
	for b-a > 12 { // Use ShellSort for slices <= 12 elements
		if maxDepth == 0 {
			heapSort(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := doPivot(data, a, b)
		// Avoiding recursion on the larger subproblem guarantees
		// a stack depth of at most lg(b-a).
		if mlo-a < b-mhi {
			quickSort(data, a, mlo, maxDepth)
			a = mhi // i.e., quickSort(data, mhi, b)
		} else {
			quickSort(data, mhi, b, maxDepth)
			b = mlo // i.e., quickSort(data, a, mlo)
			}
		}
		if b-a > 1 {
			// Do ShellSort pass with gap 6
			// It could be written in this simplified form cause b-a <= 12
			for i := a + 6; i < b; i++ {
				if data.Less(i, i-6) {
				data.Swap(i, i-6)
			}
		}
		insertionSort(data, a, b)
	}
}