这篇文章再来看看几种在实践当中更加常用, 也更加复杂一点的排序算法, 分别是希尔排序, 堆排序, 快速排序, 归并排序.
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
来源: http://developer.51cto.com/art/202108/676343.htm