Go 语言算法之美—进阶排序

本文转载自微信公众号「roseduan写字的算法地方」，作者roseduan。进阶转载本文请联系roseduan写字的排序地方公众号。

这篇文章再来看看几种在实践当中更加常用、算法也更加复杂一点的进阶排序算法，分别是排序希尔排序、堆排序、算法快速排序、进阶归并排序。排序

1、算法希尔排序

希尔排序其实是进阶对插入排序的一种优化，回想一下，排序插入排序的算法流程是：将数据分为了已排序区间和未排序区间，依次遍历未排序区间的进阶值，将其插入到已排序区间合适的排序位置。

插入排序的一个最大的缺点是：每次只能移动一位，这样在一些极端的情况下会非常低效;例如数据 2 3 5 7 9 0，如果将 0 移动至元素头部，需要遍历整个数组。

希尔排序的服务器托管优化点就在于此，它的核心思想是将数据中的元素分为了多个组，每一组分别进行插入排序。

举一个简单的例子：有数据 35 33 42 10 14 19 27 44，首先将数据以其长度的 1/2 (也就是 4)为步长，分为了四个组，分别是 { 35,14}、{ 33,19}、{ 42,27}、{ 10,44}。

然后对每一组分别进行插入排序，排序后的结果如下：

然后步长缩小一半，变为 2 ，将数组分为了两个组，分别是 { 14,27,35,42}、{ 19,10,33,44}：

然后再分别对这两个组进行插入排序，结果就是 14 10 27 19 35 33 42 44。

最后，步长再缩小一半，变为 1，将数组分为了一个组(其实就是数组本身)，并再进行插入排序，亿华云计算这样希尔排序的流程便完成了。

可以看到，希尔排序将数组分为了多个组，其实是为了尽可能的将数据变得局部有序，代码如下：

func ShellSort(data []int) {     length := len(data)    step := length / 2    for step >= 1 {        for i := 0; i < length-step; i++ {           j, k := i+step, data[i+step]          for ; j > step-1 && data[j-step] > k; j -= step {              data[j] = data[j-step]          }          data[j] = k       }       step /= 2    } } 

希尔排序实际应用并不是很多，它的相关复杂度如下：

    Time Complexity   Best O(nlog n) Worst O(n2) Average O(nlog n) Space Complexity O(1) Stability no

2、堆排序

要理解堆排序，必须得先明白什么是二叉堆。二叉堆(以下简称堆)是一种很优雅的数据结构，它是一种特殊的二叉树，满足二叉树的两个特性便可以叫做堆：

是一个完全二叉树 堆中任意一个节点的值都必须大于等于(或者小于等于)其子树中的所有节点值

对于节点大于等于子树中节点值的堆，叫做大顶堆，反之则叫做小顶堆，以下是两个堆的例子：

从定义和上图中可以看到，堆的一个特点是香港云服务器，堆顶元素就是堆中最大(或最小)的元素。

堆其实可以使用数组来存储，堆顶元素就是数组的第一个元素，并且对于任意下标为 i 的节点，其左子节点是 2 * i + 1，右子节点是 2 * i + 2，有了这个对应关系，堆在数组中的存储就是这样的：

理解了什么是堆之后，接下来进入正题，看看如何基于堆实现排序。堆排序的步骤一般有两个，分别是构造堆和排序，下面依次介绍。

构造堆

构造堆指的是将无序的数组构造成堆(这里使用大顶堆进行讲解)，使其符合堆的特征，举一个例子，对于一个完全无序的数组，其原始状态和存储结构如下图：

要使其变成大顶堆，我们可以这样做：从第一个非叶子节点开始，依次将其和子节点的值进行比较，如果小于子节点的值，交换节点顺序，然后再依次比较下去，直到叶子节点。

这样就能够始终满足堆的特性，任意节点的值总是大于其子树中所有节点的值。

排序

堆构建完成之后就是排序了，前面提到了堆有一个很重要的特性，那就是堆顶元素就是最大的元素，我们遍历数组的长度，每次都取堆顶的元素(下标为 0 的元素)，将其和数组最后的元素交换位置，然后重新将剩下的数据组织成堆，继续取堆顶的最大元素，以此类推。

将两个步骤结合起来，就是堆排序的完整实现了，代码如下：

// 堆排序 func HeapSort(data []int) {     // 构建堆    length := len(data)    for i := (length - 2) / 2; i >= 0; i-- {        heapify(data, length, i)    }    // 排序    for length > 0 {        length--       data[length], data[0] = data[0], data[length]       heapify(data, length, 0)    } } func heapify(data []int, size, i int) {     for {        max := i       if 2*i+1 < size && data[2*i+1] > data[max] {           max = 2*i + 1       }       if 2*i+2 < size && data[2*i+2] > data[max] {           max = 2*i + 2       }       if i == max {           break       }       data[i], data[max] = data[max], data[i]       i = max    } } 

相关复杂度如下： 

Time Complexity   Best O(nlog n) Worst O(nlog n) Average O(nlog n) Space Complexity O(1) Stability No

归并排序

归并排序基于分治思想。

分治，顾名思义就是分而治之，它是一种解决问题的思路，将原始问题分解为多个相同或相似的子问题，然后将子问题解决，并将子问题的求得的解进行合并，这样原问题就能够得到解决了。

分治思想是很多复杂算法的基础，例如归并排序、快速排序、二分查找等等。

言归正传，再来看归并排序，它的概念理解起来非常简单，如果我们要对一组数据进行排序，我们可以将这个数组分为两个子数组，子数组再进行分组，这样子数组排序之后，将结果合并起来，就能够得到原始数据排序的结果。

下面这张图展示了将一个问题分解为多个子问题的过程：

子问题得到解决之后，需要将结果合并，合并的过程如下图：

代码实现如下：

//归并排序 func MergeSort(data []int) {     mergeSortHelper(data, 0, len(data)-1) } func mergeSortHelper(data []int, lo, hi int) {     if lo < hi {        mid := lo + (hi-lo)/2       mergeSortHelper(data, lo, mid)       mergeSortHelper(data, mid+1, hi)       merge(data, lo, mid, hi)    } } func merge(data []int, lo, mid, hi int) {     temp := make([]int, hi-lo+1)    i, j, k := lo, mid+1, 0    for i <= mid && j <= hi {        if data[i] < data[j] {           temp[k] = data[i]          i++       } else {           temp[k] = data[j]          j++       }       k++    }    copy(temp[k:], data[i:mid+1])    copy(temp[k:], data[j:hi+1])    copy(data[lo:hi+1], temp[:]) } 

相关复杂度如下：

Time Complexity   Best O(n*log n) Worst O(n*log n) Average O(n*log n) Space Complexity O(n) Stability Yes

3、快速排序

快速排序通常叫做“快排”，它应该是应用最广泛的一个排序算法了，很多编程语言内置的排序方法，都或多或少使用到了快速排序，因为快速排序的时间复杂度可以达到 O(nlogn)，并且是原地排序，前面介绍的几种排序算法都无法将这两个优点结合起来。

快排和归并排序类似，都采用了分治思想，但是它的解决思路却和归并排序不太一样。

如果要排序一个数组，我们可以从数组中选择一个数据，做为分区点(pivot)，然后将小于分区点的放到分区点的左侧，大于分区点的放到其右侧，然后对于分区点左右两边的数据，继续采用这种分区的方式，直到数组完全有序。

概念读起来可能有点抽象，这里我画了一张图来帮助你理解整个排序的过程：

上图展示了第一次分区的过程，假设要排序的数组的下标是 p ~ r，我们取数组的最后一个元素 5 做为分区点，然后比 5 小的数字 0 3 1 2 移动到 5 的左边，比 5 大的数字 9 6 8 7 移动到 5 的右边。

然后以数字 5 为分界点，其左边的数字(下标为 p ~ q - 1)，以及右边的数字(下标为 q + 1 ~ r)，分别再进行同样的分区操作，一直分下去，直到数组完全有序，如下图：

下面的动图展示了快速排序的完整过程(注意动图中是选择第一个元素做为分区点的)：

如果使用一个简单的公式来表示快速排序，可以写成这样：

int q = partition(data, p, r); quick_sort(data, p, r) = quick_sort(data, p, q - 1) + quick_sort(data, q + 1, r); 

这里有一个 partition 分区函数，它的作用是选择一个分区点，并且将小于分区点的数据放到其左边，大于分区点的放到其右边，然后返回分区点的下标。

其实这个 partition 分区函数是快速排序实现的关键，那究竟怎么实现这个函数呢?很容易想到的一种方式是：直接遍历一次原数组，依次取出小于和大于分区点的数据，将其各自存放到一个临时数组中，然后再依次拷贝回原数组中，过程如下图：

这样做虽然简单，但是存在一个缺陷，那就是每次分区都会使用额外的存储空间，这会导致快速排序的空间复杂度为 O(n)，那么就不是原地排序了。

所以快速排序使用了另一种方式来实现分区，并且没有借助额外的存储空间，它是怎么实现的呢?我还是画了一张图来帮助你理解：

声明了两个指针 i 和 j，从数组的最开始处向后移动，这里的移动规则有两个：

一是如果 j 所在元素大于分区点，那么 j 向后移动一位，i 不变; 二是如果 j 所在元素小于分区点，那么交换 i 和 j 所在元素，然后 i 和 将 j 同时向后移动一位。

终止的条件是 j 移动至数组末尾，然后交换分区点和 i 所在的元素，i 就是分区点的下标。

理解了这个过程之后，再来看快速排序的代码实现，就会非常的简单了，下面是一个示例：

func QuickSort(data []int) {    quickSortHelper(data, 0, len(data)-1) } func quickSortHelper(data []int, lo, hi int) {    if lo < hi {      mid := partition(data, lo, hi)     quickSortHelper(data, lo, mid-1)     quickSortHelper(data, mid+1, hi)   } } func partition(data []int, lo, hi int) int {    pivot, i, j := data[hi], lo, lo   for j < hi {      if data[j] < pivot {        data[j], data[i] = data[i], data[j]       i++     }     j++   }   data[i], data[hi] = data[hi], data[i]   return i } 

快速排序相关复杂度如下：

Time Complexity   Best O(n*log n) Worst O(n2) Average O(n*log n) Space Complexity O(log n) Stability No

文中的全部代码可在我的 Github 上查看：https://github.com/roseduan/Go-Algorithm

很赞哦!（7955）