1. 堆排序
堆 是一种数据结构，它具有如下特征：
- 是一棵完全二叉树
- 父节点的值 > 子节点的值
1.1 完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是 完全二叉树。
完全二叉树有一个很重要的特点，它的元素可以全部放在一个数组中，这个数组中的元素排列非常紧密，不会出现零值的情况。比如下面这棵树，对应的数组为： [25, 14, 13, 4, 2, 10]。
如果我们从上到下、从左到右的顺序去遍历这棵树，会发现，元素顺序与数组中完全对应。于是会有下面的公式：
设数组中父节点的
index值为i，则左孩子的index值为2*i+1，右孩子的index值为2*i+2。这样数组和数的关系就对应上了。这是堆排序的基础。
1.2 heapify
我们称 将一棵树变成堆的过程 称为 heapify。具体来说是将 parent、left 和 right这三个结点，通过交换，使得 parent 为最大(left和right哪个大没关系)，因为数的定义是递归的，所以上面这个交换过程也是递归的。此时需要决定的是从下到上，还是从上到下。答案是如果是大根堆，从下到上进行 heapify 过程，因为从上到下的，处理完父节点，还不确定这个父节点是不是就是整个堆中的最大，而从下到上可以看成是一个不断往上 “喂” 最大值的过程。可以写出代码：
// heapify 从数组的第i个元素为父节点，使其符合大根堆的特性。前提，左右子树均已经是大根堆了
func heapify(arr []int, n int, i int) {
if i >= n {
return
}
// 第i个结点的左右孩子分别为
left := 2*i + 1
right := 2*i + 2
// 求得父节点、左孩子、右孩子之间的最大值
maxIndex := i
if left < n && arr[left] > arr[maxIndex] {
maxIndex = left
}
if right < n && arr[right] > arr[maxIndex] {
maxIndex = right
}
// 如果发生了交换，需要递归去处理对应的子树
if maxIndex != i {
// 交换 使得parent为最大的那个
arr[i], arr[maxIndex] = arr[maxIndex], arr[i]
//fmt.Println(arr[maxIndex], arr[left], arr[right])
// 此时，修改了原来的结构，为了保证交换后的子树也继续是大根堆，这里递归调用调整子树
heapify(arr, n, maxIndex)
}
}
1.3 build heap
当我们从下到上构建一个大根堆的时候，没必要从最后一个元素开始，需要从最后一个有孩子的父节点开始，所以第一步是先找到 最后一个有孩子的父节点。方法很简单，找到最后一个孩子，再根据他们之间的关系很容易就能求得其父节点的索引值。之后遍历所有的有孩子的节点，即剩下的 13 , 14, 25，这三个元素刚好按照数组索引的顺序递减，因此可以写出代码：
// buildHeap 从底向上构建大根堆
func buildHeap(arr []int) {
n := len(arr)
parent := (n - 1 - 1) / 2 // n-1为数组最后一个元素的index，其父节点为 ((n-1) - 1) / 2
for i := parent; i >= 0; i-- {
// 从这个父节点开始，一直到第一个元素，从下到上构建不断heapify
heapify(arr, n, i)
}
}
1.4 heap sort
构建出大根堆之后，堆顶(也就是数组index=0)的元素就是最大值。此时，我们将数组第一个元素和最后一个元素交换位置，之后缩小数组长度再次从头到尾进行 heapify ，之后再交换，最后的结果就是 数组从尾巴到头的元素一次递减。
func heapSort(arr []int) {
buildHeap(arr) // 构建大根堆
// 最后一个元素 与 第一个元素(最大)交换，之后再次heapify，再交换，结果就是从尾到头数值依次减小
for i := len(arr) - 1; i >= 0; i-- {
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
}
}
2. 插入排序
它的工作原理是构建有序序列，对于未排序的数据，在已经排好序的序列中从后向前扫描，放入合适的位置。
优点是：对近乎有序的一组数排序，其时间复杂度可以接近线性。 这个特性非常重要！谨记！！
步骤：
- 第一步，将第一个元素看成有序序列，第二个元素到最后一个元素看成未排序的序列；
- 从头到尾扫描未排序的序列，将这个元素插入到前面的有序序列的合适位置。为了 稳定性 的目的，如果某个元素和有序序列中的某个元素相同，应该将这个元素放在有序序列元素的后面。
// insertionSort 插入排序
func insertionSort(arr []int) {
sortedIndex := 0 // 有序序列的最后一个元素
// 遍历所有的未排序元素
for i := sortedIndex + 1; i < len(arr); i++ {
// 从当前元素开始向前遍历有序序列
for j := i; j > 0; j-- {
// 当前值大于等于前面的，终止循环
if arr[j-1] <= arr[j] {
break
}
// 如果当前值比前一个小，交换，之后循环再不断交换
arr[j-1], arr[j] = arr[j], arr[j-1]
}
}
}
3. 希尔排序
是插入排序的改进版本，更高效一些，但是它是不稳定的。具体步骤如下：
- 以 gap 为间隔分组
- 分好的组内内部排好序
- 降低 gap，重复上述步骤，直到 gap 变成 1，此时变成对整个数组进行排序
有一个问题，组内排序，采用什么方法？答案是 插入排序法，原因就是，在 gap 不断减小的过程中，数组主键接近有序，此时借助插入排序的优点：对近乎有序的一组数排序，其时间复杂度可以接近线性。是一个不错的选择。
func shellSort(arr []int) {
gap := 1 // 计算gap，简单点，可以让gap变成数组长度的一半
for gap < len(arr)/3 {
gap = gap*3 + 1
}
for gap > 0 {
for i := gap; i < len(arr); i++ {
tmp := arr[i]
j := i - gap
// 每次之和当前组内前面的元素比较交换
for j >= 0 && arr[j] > tmp {
arr[j+gap] = arr[j]
j -= gap
}
arr[j+gap] = tmp
}
gap /= 3 // 更新gap
}
}
4. 快速排序
采用的是“分而治之”的思想。步骤如下：
- 第一步，挑出基准元素(一般取第一个元素)
- 对数组进行排序，使得所有小于基准的排在前面，大于基准的排在基准后面。最后返回分区的位置。这个操作我们称之为
partition。 - 递归地 把小于基准值元素的子数列和大于基准值元素的子数列排序
func quickSort(arr []int) []int {
return _QuickSort(arr, 0, len(arr)-1)
}
func _QuickSort(arr []int, left, right int) []int {
if left < right {
partitionIndex := partition(arr, left, right)
_QuickSort(arr, left, partitionIndex-1)
_QuickSort(arr, partitionIndex+1, right)
}
return arr
}
func partition(arr []int, startIndex, endIndex int) int {
var (
pivot = arr[startIndex] // 基准
left = startIndex
right = endIndex
)
for left != right {
// right指向倒数第一个小于基准的数
for left < right && pivot < arr[right] {
right--
}
// left指向顺数第一个大于基准的
for left < right && pivot >= arr[left] {
left++
}
// 交换left和right处的值
if left < right {
arr[left], arr[right] = arr[right], arr[left]
}
}
// 此时left=right，将left与pivot处的值交换即可
arr[startIndex], arr[left] = arr[left], arr[startIndex]
return left
}