排序的概念
排序分为内部排序和外部排序，内部排序中，排序用的数据都在主存内，外部排序则可能存在在磁盘或者远端，访问数据需要进行I/O。
排序的稳定性是指数组中存在相同值得元素，在完成排序后，其前后相对位置不会发生变化。
| 稳定的排序算法 | 不稳定的排序算法 |
|---|---|
| 插入排序 | 选择排序 |
| 冒泡排序 | 快速排序 |
| 归并排序 | 堆排序 |
下面用Golang分别演示排序算法，为了简化讨论，本文中排序的目标都是升序。
比较排序
假设N是参与排序的元素个数，在内部排序中，存在几种直观的比较排序算法，插入排序、选择排序和冒泡排序，它们的时间复杂度为O(N^2)。
插入排序
插入排序是最直观的排序算法之一，它由N-1趟排序过程完成，从第p=1到N-1趟，插入排序保证从位置0到p的元素处于已排序状态。因此，插入排序利用了这样一个事实：在第p趟排序前，位置0到p-1的元素已经处于排序状态，第p趟需要在0到p的元素中选择一个合适的位置，放置元素p。随着排序的推进，已排序区的范围扩大，最终整个数组完成排序。
插入合适位置的策略是，在第p趟，将所有大于第p+1个元素的元素向左移动。
1
2
3
4
5
6
7
8
9
10
11
12
//go insert sort
func InsertSort(nums []int) {
var j int
for p := 1; p < len(nums); p++ {
tmp := nums[p]
// mind the j scope
for j = p; j > 0 && tmp < nums[j-1]; j-- {
nums[j] = nums[j-1]
}
nums[j] = tmp
}
}
当输入数组是反序时，插入排序的时间复杂度达到最高O(N^2)，当输入数组几乎被排序时，插入排序可以很快完成，到达O(N)。
冒泡排序
冒泡排序的思路是通过N-1趟遍历，每次比较两个元素，每趟将最小的一个元素传递到最前，形成一个顺序区，最终所有元素都与其邻居保持顺序，完成排序。
稍作优化的是，若在一轮遍历中，没有发现需要冒泡的逆序对，整个数组就认定为完成排序了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//bubble sort
func BubbleSort(nums []int) {
for i := 0; i < len(nums)-1; i++ {
var doSwap bool //if no swap done in this loop, the whole array must be in-order
for j := len(nums) - 1; j > 0; j-- {
if nums[j-1] > nums[j] {
doSwap = true
nums[j], nums[j-1] = nums[j-1], nums[j] //bubble up
}
}
if !doSwap {
break
}
}
}
冒泡排序和插入排序一样，在处理反序数组时需要O(N^2)的时间复杂度，而几乎排序好的数组只需要O(N)。
选择排序
选择排序和插入排序的思想基本相同，都是维护一个“顺序区”，不同的是，插入排序通过调整“顺序区”来维护，选择排序则通过选择一个“非顺序区”中最大的元素来维护新“顺序区”。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//selection sort
func SelectionSort(nums []int) {
for i := 0; i < len(nums); i++ {
var minIdx int
minKey := math.MaxInt32
//select the min element in 'unorder' region
for j := i; j < len(nums); j++ {
if nums[j] < minKey {
minIdx = j
minKey = nums[j]
}
}
//put min element in the back of 'ordered region'
nums[i], nums[minIdx] = nums[minIdx], nums[i]
}
}
选择排序的时间复杂度平均为O(N^2)。实际上，任何通过交换相邻元素进行排序的算法平均都需要O(N^2)的时间。因此，如果算法要在这个时间以下运行，必须执行一些比较，交换相距较远的元素，使得每次交换删除的逆序对不止一个。
希尔排序
希尔排序是第一批突破O(N^2)的排序算法。它的特点是允许位置相距很远的元素进行交换，每趟比较所用的距离逐渐减小，从而减少元素位置移动的次数。希尔排序也被成为缩减增量排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//shell sort
func ShellSort(nums []int) {
//compare ans swap element with distance gap
for gap := len(nums) / 2; gap > 0; gap /= 2 {
//offset i on current gap
for i := gap; i < len(nums); i++ {
var j int
tmp := nums[i] //to put nums[i] at its right place
//insert sort, move all nums[j] at gap 'gap' that is greater
// than tmp
for j = i; j >= gap && nums[j] < nums[j-gap]; j -= gap {
nums[j] = nums[j-gap]
}
nums[j] = tmp //found the right place for tmp
}
}
}
希尔排序使用了h1,h2,…hk序列作为增量序列，在使用增量hk完成排序后，对于任意i，有a[i]<=a[i+hk]成立，也就是说所有相隔hk的元素都被排好序。
快速排序
快速排序的平均时间为O(NlogN)，它使用了分而治之的思路，对于数据集合的每个区间，取出一个划分位(parition)，移动集合元素，使得划分位前的元素小于划分位，之后的元素大于划分位。同时推广这种方法于划分位前后子区间。
快速排序的直观实现为，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//quick sort
func QuickSort(nums []int) {
if len(nums) > 1 {
var smaller, equal, larger []int
pivot := nums[len(nums)/2]
//split input into three disjoint subset
for _, n := range nums {
if n < pivot {
smaller = append(smaller, n)
} else if n > pivot {
larger = append(larger, n)
} else {
equal = append(equal, n)
}
}
//sort the two subset
QuickSort(smaller)
QuickSort(larger)
//combine the subset
copy(nums[:], smaller)
copy(nums[len(smaller):], equal)
copy(nums[len(smaller)+len(equal):], larger)
}
}
这种实现虽然容易理解，但是需要付出大量的额外内存，考虑一种in-place的快速排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//in-place quick sort
func partition(nums []int, low, high int) int {
pivot := nums[high] //select the last element as pivot
i := low //set 'smaller' boundary at low
//traversal over all elements
for j := low; j < high; j++ {
if pivot > nums[j] {
//if element is smaller than pivot, put it
// at low boundary and adjust boundary
nums[i], nums[j] = nums[j], nums[i]
i++
}
}
//put pivot element at the low boundary
nums[i], nums[high] = nums[high], nums[i]
return i
}
func quickSortHelper(nums []int, low, high int) {
if low < high {
pi := partition(nums, low, high)
quickSortHelper(nums, low, pi-1)
quickSortHelper(nums, pi+1, high)
}
}
func QuickSort2(nums []int) {
quickSortHelper(nums, 0, len(nums)-1)
}
对于枢纽元pivot的处理，关键在于枢纽元要将元素平均地划分到前后两个集合。几种方案是，
- 选择第一个或者最后一个元素作为pivot
当输入数组正好是正序或者反序时，这种划分会非常糟糕
- 随机选取一个元素作为pivot
这种策略虽然安全，但是产生随机数发生器的开销可能非常大，有时根本无法减少算法的平均运行时间
- N数中值划分法，选择第N/2大的元素
通常这是一种太理想的方法，计算中位数的开销大
- 三数中值划分法，选左右中三个元素取中位数
这是一种可行的方法，它消除了最糟糕的情形
堆排序
堆排序利用了优先队列，实现O(NlogN)时间的排序。堆排序中，首先利用N个元素建立二叉堆(需要O(N)的时间)，优先队列的根节点总是存放着最小(大)的元素，取根节点值进行删除，直到二叉堆为空，得到的根节点序列即为排序好的数组。
算法的一个主要问题是需要额外的数组来存放结果，但是利用二叉堆每删除一次元素少一个的性质，可以用二叉堆的末尾位置存放结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//heap sort
func leftChild(i int) int {
return 2*i + 1
}
func precDown(heap []int, i, hsize int) {
var child int
var tmp int
for tmp = heap[i]; leftChild(i) < hsize; i = child {
child = leftChild(i)
if child < hsize-1 && heap[child] < heap[child+1] {
child++
}
//exchange left child
if tmp < heap[child] {
heap[i] = heap[child]
} else {
break
}
}
heap[i] = tmp
}
func HeapSort(nums []int) {
for i := len(nums)/2 - 1; i >= 0; i-- {
precDown(nums, i, len(nums))
}
for i := len(nums) - 1; i > 0; i-- {
nums[i], nums[0] = nums[0], nums[i]
precDown(nums, 0, i)
}
}
归并排序
归并排序的最坏情形时间复杂度也是O(NlogN)。算法的基本操作是合并两个已经排好序的数组，使用了“分而治之”的思路，将数据集合划分直到子集合只有一个元素，然后在归并子集合的过程中完成排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//merge sort
func merge(nums []int, low, mid, high int) {
var L, R []int
//left must include mid, since low could be equal with mid when
// high - low < 2, otherwise L would be empty and sort would fail
L = append(L, nums[low:mid+1]...)
R = append(R, nums[mid+1:high+1]...)
var left, right, idx int
llen, rlen := len(L), len(R) //mid-low+1, high-mid
idx = low
for left < llen && right < rlen {
if L[left] < R[right] {
nums[idx] = L[left]
left++
} else {
nums[idx] = R[right]
right++
}
idx++
}
if left < llen {
copy(nums[idx:], L[left:])
} else if right < rlen {
copy(nums[idx:], R[right:])
}
}
func mergeSortHelper(nums []int, low, high int) {
if low < high {
mid := low + (high-low)/2 //[0, 0, 1], low = mid
mergeSortHelper(nums, low, mid)
mergeSortHelper(nums, mid+1, high)
merge(nums, low, mid, high)
}
}
func MergeSort(nums []int) {
mergeSortHelper(nums, 0, len(nums)-1)
}
归并排序在合并两个已经排好序的数组时用到了线性的附加数组，需要对元素进行拷贝，在任意时刻，可能有logN个临时数组在活动。
归并排序和快速排序的对比
归并排序和快速排序常常被标准库层面选择实现排序。归并排序需要复制和比较元素，而快速排序可以不需要复制元素。
不同的对象在进行复制和比较时的开销是不同的，例如，在Java中，进行元素比较可能是昂贵的(可能涉及泛型和动态调度)，而由于对象是引用方式传递的，复制的代价是较小的。而在C++中，比较由内嵌的操作符实现，代价小，但是元素是通过传值的方式传递的，复制代价高昂。
因此，不同的语言会进行权衡，C++库常用快速排序实现，而Java较多使用归并排序。
桶排序–线性时间排序
桶排序和基数排序
桶排序在满足一些附加条件的情形下，可以达到O(N)的最坏时间复杂度。假设输入数据A1,…AN仅由小于M的正整数组成，使用一个大小为M的count数组，初始化为0，读入输入数据，记录count[Ai]的值，最后打印输出排序好的数组。桶排序对于输入只是一些小整数的情形十分有用。
基数排序是桶排序的一个应用，假设有0~99999的数字需要排序，我们显然不能用99999个桶来进行排序。但我们可以用几趟桶排序，首先用个位排序，然后是十位，最后是最高位，每一趟排序都是稳定的，即后序的桶排序会保留前面趟的顺序。
基数排序可以用于字符串排序，对于相同长为L的字符串，可以实现O(NL)时间内的基数排序。假设字符串的字符都是ASCII码，即Unicode的前256位。每一趟把一个元素放入合适的桶中，全部字符串放好后，再将桶中的字符串倒回数组中，依次推进，遍历L位字符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//radix sort
func RadixSort(strs []string) {
if len(strs) < 2 {
return
}
const BUCKET = 256
strLen := len(strs[0])
buckets := make([][]string, BUCKET) //create buckets
//from less significant byte to significant byte, each loop of
// bucket is therefore stable
for i := strLen - 1; i >= 0; i-- {
//put strings into buckets
for _, s := range strs {
buckets[s[i]] = append(buckets[s[i]], s)
}
var idx int
for _, b := range buckets {
//build string array with buckets
for _, s := range b {
strs[idx] = s
idx++
}
buckets = make([][]string, BUCKET) //reset buckets
}
}
}
上面一种算法在每趟桶排序中都需要将元素复制到桶中，再复制回数组中，考虑一种复制次数更少的基数排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
func CountingRadixSort(strs []string) {
if len(strs) < 2 {
return
}
const BUCKET = 256
strLen := len(strs[0])
arrLen := len(strs)
in := strs //reference to input array
out := make([]string, len(strs))
//bucket sort on the i-th char of all strings
for pos := strLen - 1; pos >= 0; pos-- {
count := make([]int, BUCKET+1)
//iterate over all strings
for j := 0; j < arrLen; j++ {
count[in[j][pos]+1]++ //the i-th char of the j-th string
}
//accumlate counting of buckets
for b := 1; b <= BUCKET; b++ {
count[b] += count[b-1]
}
//put back string at the right place
for j := 0; j < arrLen; j++ {
out[count[in[j][pos]]] = in[j]
count[in[j][pos]]++
}
//exchange bucket
in, out = out, in
}
//if odd num of passes, in is buffer while out is arr, copy buffer
// to arr
if strLen%2 == 1 {
copy(out[:], in[:])
}
//copy to origin array
copy(strs[:], out[:])
}
上面两种算法都要求数组中的字符串长度都相等，考虑字符串长度不相等的情形。