| 算法名称 | 最差时间分析 | 平均时间复杂度 | 稳定度 | 空间复杂度 |
|---|---|---|---|---|
| 选择排序 | O(n2) | O(n2) | 不稳定 | O(1) |
| 插入排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 归并排序 | O(n2) | O(n*log2n) | 不一定 | O(n) |
| 快速排序 | O(n2) | O(n*log2n) | 不稳定 | O(log2n)~O(n) |
| 二叉树排序 | O(n2) | O(n*log2n) | 不一定 | O(n) |
| 堆排序 | O(n*log2n) | O(n*log2n) | 不稳定 | O(1) |
| 希尔排序 | O | O | 不稳定 | O(1) |
goos: darwin
goarch: amd64
pkg: github.com/gohp/goutils/sort
BenchmarkBubbleSort-8 26037326 44.3 ns/op
BenchmarkSelectSort-8 19312984 60.1 ns/op
BenchmarkInsertSort-8 39722790 28.2 ns/op
BenchmarkQuickSort-8 705214 1585 ns/op
BenchmarkMergingSort-8 1473480 814 ns/op
BenchmarkHeapSort-8 15629527 76.1 ns/op
PASS
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
- 从未排序序列中，找到关键字最小的元素
- 如果最小元素不是未排序序列的第一个元素，将其和未排序序列第一个元素互换
- 重复1、2步，直到排序结束。
通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中，为了要给插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：
- 从数列中挑出一个元素，称为"基准"（pivot）。
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
归并排序是建立在归并操作上的一种有效的排序算法，1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
归并排序可通过两种方式实现:
- 自上而下的递归:
- 自下而上的迭代
递归法（假设序列共有n个元素）：
- 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
- 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
- 重复步骤2，直到所有元素排序完毕。
Refer: