关于这篇笔记
最近做了几道比较难的leetCode题，其中一道题使用了基数排序（LeetCode-164题，另一种思路有桶排序的思想）， 突然发现自己好多东西都忘记了，或者说其实从来就没有真正的学会。所以这里决定重新回到算法导论的前面再看一看排序算法。
这篇笔记中包含算法冒泡排序、插入排序、希尔排序、归并排序、堆排序、快速排序、计数排序、基数排序、桶排序。
代码:github
代码的实现中均没有考虑负数，只考虑了非负数。
参考资料：
冒泡排序
冒泡排序是一种最为简单的排序算法，它的想法就是“比较所有相邻的数的大小，将小的放前面，大的放后面，重复这个过程”。
在算法执行过程中，可以看成，第一轮把最小的元素放到第一个位置，第二轮把第二小的元素放到第二个位置…重复N次。
在实现的时候每次可以检查是否发生交换，如何没有发生交换，就可以提前停止算法。
时间复杂度：$O(n^2)$
空间复杂度：原址（也就是$O(1)$）
是否稳定：是
是否能处理负数：是
代码：
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
public class BubbleSort {
public void sort(int[] nums, int begin, int end) {
if ( nums == null ) {
return;
}
if ( nums.length < 2 || begin >= (end - 1)) {
return;
}
begin = begin < 0 ? 0 : begin;
end = end > nums.length ? nums.length : end;
boolean change;
for ( int i = begin; i < end; i++ ) {
change = false;
for ( int j = end - 1; j > i; j-- ) {
if ( nums[j] < nums[j-1] ) {
int tmp = nums[j-1];
nums[j-1] = nums[j];
nums[j] = tmp;
change = true;
}
}
if ( !change ) {
break;
}
}
}
}
1 | public class BubbleSort { |
插入排序
插入排序也是一种基本的排序算法，它就类似于抓牌的过程，“当抓到一张新牌时，我们会把牌按大小顺序插入到它应该在的位置上”。
在感觉上插入排序和冒泡排序有一些类似，它们的复杂度也是一样，但是实际上插入排序要比冒泡排序快一点。
时间复杂度：$O(n^2)$
空间复杂度：原址
是否稳定：是
是否能处理负数：是
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class InsertionSort{
public void sort(int[] nums, int begin, int end) {
if ( nums == null ) {
return;
}
if ( nums.length < 2 || begin >= (end - 1)) {
return;
}
begin = begin < 0 ? 0 : begin;
end = end > nums.length ? nums.length : end;
for ( int i = begin + 1; i < end; i++ ) {
int key = nums[i];
int j = i - 1
for (; j >= begin && A[j] > key; j-- ) {
nums[j+1] = nums[j];
}
nums[j+1] = key;
}
}
}
1 | public class InsertionSort{ |
希尔排序
希尔排序英文为Shell Sort，这里的‘Shell’实际上是一个人名。
希尔排序是对插入排序的一种改进，它的改进想法来自于“序列越基本有序，则插入排序效率越高”：
设想序列的最后一个数是最小的数，那么当对它进行插入时，将需要从最后的位置，一个一个向前挪到第一个， 所以这种情况如果越少发生，那么插入排序的效率也就越高。
这里“序列的基本有序”定义就是所有的数当前位置离排序后的位置越近，就越有序。也就是大的数就在序列的后面，小的数就在序列的前面。
有了上面的观察，那么就要想办法先将序列变得“有序”，然后再进行插入排序。
具体流程可以参考算法导论———ShellSort希尔排序，比较直观。
代码中gap选择A102549， 至于gap，可以参考wikiGap_sequences
时间复杂度：小于$O(n^{\frac{4}{3}})$
空间复杂度：原址
是否稳定：否
是否能处理负数：是
代码：
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
public class ShellSort {
public void sort(int[] nums, int begin, int end) {
if ( nums == null ) {
return;
}
if ( nums.length < 2 || begin >= (end - 1)) {
return;
}
begin = begin < 0 ? 0 : begin;
end = end > nums.length ? nums.length : end;
int[] gaps = {1, 4, 10, 23, 57, 132, 301, 701, 1750};
int idx = gaps.length - 1;
while ( idx >= 0 ) {
int start = gaps[idx] + begin;
for ( int i = start; i < end; i++ ) {
for ( int j = i; j >= start; j -= gaps[idx] ) {
int front = j - gaps[idx];
if ( nums[j] >= nums[front] ) {
break;
}
int tmp = nums[j];
nums[j] = nums[front];
nums[front] = tmp;
}
}
idx--;
}
}
}
1 | public class ShellSort { |
归并排序
归并是一种递归排序的方式，它每一次递归将数据均分成左右两个部分，然后两个部分分别排序，这里分别排序也就是再次调用归并排序来进行。
当递归到元素只剩下一个的时候，那么它当然是有序的，于是就开始返回，从下往上进行合并。
两个已经排好序的序列合并很简单，新建一个数组，长度等于两个序列的总长， 对比两个序列的第一个元素，每次选最小的那一个放到新数组里就行了。
对于复杂度为$O(n^2)$的算法，相当于序列的每一个元素都要和序列的其它所有元素比一遍，也就是每个元素要比n-1次，一共n个元素，
所以复杂度就为$O(n^2)$。
对于归并排序来说，它每次进行二分，所以总的深度就为$log_2(n)$，在向上合并的过程中，比较一次就可以放下一个元素，
所以每一层最多需要比较n次，所以算法的复杂度就降到了$nlog(n)$。
时间复杂度：$nlog(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
35
36
public class MergeSort {
public void sort(int[] nums, int begin, int end) {
if ( nums == null ) {
return;
}
if ( nums.length < 2 || begin >= (end - 1)) {
return;
}
begin = begin < 0 ? 0 : begin;
end = end > nums.length ? nums.length : end;
mergeSort(nums, begin, end);
}
private void mergeSort(int[] nums, int begin, int end) {
if ( begin >= (end - 1) ) {
return;
}
int mid = (end + begin) / 2;
mergeSort(nums, begin, mid);
mergeSort(nums, mid, end);
int[] a = new int[mid-begin], b = new int[end-mid];
System.arraycopy(nums, begin, a, 0, a.length);
System.arraycopy(nums, mid, b, 0, b.length);
int idx1 = 0, idx2 = 0;
for ( int i = begin; i < end; i++ ) {
if ( idx1 >= a.length ) {
nums[i] = b[idx2++];
} else if ( idx2 >= b.length || a[idx1] <= b[idx2] ) {
nums[i] = a[idx1++];
} else {
nums[i] = b[idx2++];
}
}
}
}
1 | public class MergeSort { |
堆排序
堆排序则是利用了最大堆的性质，建立一个最大堆所需的时间复杂度为$nlog(n)$，将最大堆的最大元素取出， 填上另一个数，再维护最大堆的性质，将这个数下沉到它应该的位置，复杂度为$log(n)$。
所以每次将最大堆的最大元素与堆尾（数组实现最大堆）的元素进行交换，堆大小减一，维护最大堆性质，反复即可。
时间复杂度：$nlog(n)$
空间复杂度：原址
是否稳定：否
是否能处理负数：是
代码，实现中为了简化数组实现最大堆的过程，额外申请了空间保证从数组索引0开始：
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class HeapSort {
public void sort(int[] nums, int begin, int end) {
if ( nums == null ) {
return;
}
if ( nums.length < 2 || begin >= (end - 1)) {
return;
}
begin = begin < 0 ? 0 : begin;
end = end > nums.length ? nums.length : end;
int[] array = new int[end-begin];
System.arraycopy(nums, begin, array, 0, array.length);
heapSort(array);
System.arraycopy(array, 0, nums, begin, array.length);
}
private void heapSort(int[] nums) {
buildMaxHeap(nums);
for ( int i = nums.length-1; i > 0; i-- ) {
int tmp = nums[0];
nums[0] = nums[i];
nums[i] = tmp;
maxHeapify(nums, i, 0);
}
}
private void buildMaxHeap(int[] heap) {
for ( int i = heap.length / 2 - 1; i >= 0; i-- ) {
maxHeapify(heap, heap.length, i);
}
}
private void maxHeapify(int[] heap, int len, int i) {
int l = left(i), r = right(i);
int largest = i;
if ( l < len && heap[l] > heap[largest] ) {
largest = l;
}
if ( r < len && heap[r] > heap[largest] ) {
largest = r;
}
if ( largest != i ) {
int tmp = heap[i];
heap[i] = heap[largest];
heap[largest] = tmp;
maxHeapify(heap, len, largest);
}
}
private int parent(int i) {
return (i + 1) / 2 - 1;
}
private int left(int i) {
return (i + 1) * 2 - 1;
}
private int right(int i) {
return (i + 1) * 2;
}
}
1 | public class HeapSort { |
快速排序
快速排序是程序员最常使用的排序算法了，它每次选择一个主元，将比主元小的元素放到左边，大的放到右边， 在左右划分中重复这个过程，直到划分中只剩下一个元素，也就完成了排序，它通常也是递归实现。
快速排序的最坏复杂度为$O(n^2)$，也就是每次都倒霉的选择了最大或者最小的那个元素，使得左右的划分十分的“不均匀”， 但是在期望情况下，它的复杂度为$nlog(n)$。具体的证明有一些繁琐，需要参考算法导论。
随机化版本：如果每次主元的选择都是固定位置的，那么很容易就能造出一个使复杂度变成$O(n^2)$的序列， 这一点可能会被不怀好意的人给利用，所以通常主元的选择会引入随机化，快速排序的复杂度能不被输入序列给影响。
时间复杂度：$nlog(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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class QuickSort {
private Random rand = new Random();
public void sort(int[] nums, int begin, int end) {
if ( nums == null ) {
return;
}
if ( nums.length < 2 || begin >= (end - 1)) {
return;
}
begin = begin < 0 ? 0 : begin;
end = end > nums.length ? nums.length : end;
quickSort(nums, begin, end-1);
}
private void quickSort(int[] nums, int p, int q) {
if ( p >= q ) {
return;
}
int m = partition(nums, p, q);
if ( m == -1 ) {
return;
}
quickSort(nums, p, m - 1);
quickSort(nums, m+1, q);
}
private int partition(int[] nums, int p, int q) {
randomExchange(nums, p, q);
int axle = nums[q];
int j = p - 1;
int equals_count = 1;
for (int i = p; i < q; i++) {
if (nums[i] < axle) {
j++;
int tmp = nums[j];
nums[j] = nums[i];
nums[i] = tmp;
} else if ( nums[i] == axle ) {
j++;
int tmp = nums[j];
nums[j] = nums[i];
nums[i] = tmp;
equals_count++;
}
}
if ( equals_count == nums.length ) { // 防止所有元素都相等时还进行递归
return -1;
}
j++;
int tmp = nums[j];
nums[j] = nums[q];
nums[q] = tmp;
return j;
}
private void randomExchange(int[] nums, int p, int q) {
int exchange = rand.nextInt(q-p+1) + p;
int tmp = nums[exchange];
nums[exchange] = nums[q];
nums[q] = tmp;
}
}
1 | public class QuickSort { |
计数排序
假设输入的数都是非负数，它们都小于某一个数N，那么我们就可以额外申请一个长度为N的数组对输入序列进行统计，
这个数组中第i个位置就表示序列中大小为i的数的个数。于是我们就可以使用这个计数的信息，
将输入序列中数放到它应该在的位置上。
计数排序有一个很大的假设，就是需要提前知道数的范围，在数的范围已知并且范围不大的时候，计数排序的时间效率为$O(n)$。 但是通常情况下这两个假设都难以满足，所以计数排序用得很少。
时间复杂度：$O(n)$
空间复杂度：$O(n) + O(N)$
是否稳定：是
是否能处理负数：否
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class CountingSort {
public void sort(int[] nums, int k) {
if (nums == null || nums.length < 2 ) {
return;
}
int[] count = new int[k];
for ( int i = 0; i < nums.length; i++ ) {
count[nums[i]]++;
}
for ( int j = 1; j < k; j++ ) {
count[j] += count[j-1];
}
int[] copy = new int[nums.length];
System.arraycopy(nums, 0, copy, 0, copy.length);
for ( int i = copy.length-1; i >= 0; i-- ) {
nums[--count[copy[i]]] = copy[i];
}
}
}
1 | public class CountingSort { |
基数排序
基数排序的基础是计数排序，由于输入是一堆十进制数，那么它的每一位就是一个十进制数，也就是范围在0~9，
所以就可能按照计数排序的思想，对输入序列的某一位数进行排序。神奇的是，这样从个位往高位排一遍，
序列就完成了排序。
基数排序同样也只能处理非负数，但是它的复杂度只为$O(n)$，虽然其中的隐藏因子有一点大，当序列很长时， 基数排序会有很大的优势。
时间复杂度：$O(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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class RadixSort {
public void sort(int[] nums, int begin, int end) {
if ( nums == null ) {
return;
}
if ( nums.length < 2 || begin >= (end - 1)) {
return;
}
begin = begin < 0 ? 0 : begin;
end = end > nums.length ? nums.length : end;
radixSort(nums, begin, end);
}
private void radixSort(int[] nums, int begin, int end) {
int max = -1;
for ( int i = begin; i < end; i++ ) {
if ( nums[i] > max ) {
max = nums[i];
}
}
int max_exp = 1;
while ( (max / max_exp) >= 10 ) {
max_exp *= 10;
}
int[] count = new int[10];
int[] a = new int[end-begin], b = new int[a.length], radixs = new int[a.length], exchange;
System.arraycopy(nums, begin, a, 0, a.length);
int exp = 1;
while ( exp <= max_exp ) {
Arrays.fill(count,0);
for ( int i = 0; i < a.length; i++) {
radixs[i] = (a[i] / exp) % 10;
count[radixs[i]]++;
}
for ( int i = 1; i < 10; i++ ) {
count[i] += count[i-1];
}
for ( int i = a.length-1; i >= 0; i-- ) {
b[--count[radixs[i]]] = a[i];
}
exchange = b;
b = a;
a = exchange;
exp *= 10;
}
System.arraycopy(a, 0, nums, begin, a.length);
}
}
1 | public class RadixSort { |
桶排序
假设输入数据的范围是N，桶排序将N划分为m个范围，也就是m个桶，将输入序列的数一个一个丢到桶里， 然后进行桶内排序，再把所有的数据串起来，就完成了排序。
桶排序需要知道输入数据的范围，另外一个十分重要的假设是输入序列均匀分布，这样才能保证每个桶里面的元素不会太多。
个人认为计数排序就是一个特殊的桶排序，也就是桶的大小为1的时候的桶排序。
桶排序中的每一个桶其实是一个链表，它的空间消耗应该是上面所有算法中最多的。
时间复杂度：$O(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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class BucketSort {
private class Bucket {
int num = -1;
Bucket front, next;
}
public void sort(int[] nums, int bound) {
if (nums == null || nums.length < 2 ) {
return;
}
int bucket_num = Math.min(nums.length, bound);
Bucket[] buckets = new Bucket[bucket_num];
for ( int i = 0; i < bucket_num; i++ ) {
buckets[i] = new Bucket();
}
for ( int num : nums ) {
insertHelper(buckets[(num*bucket_num) / bound], num);
}
int idx = 0;
for ( Bucket bucket : buckets ) {
while ( bucket.next != null ) {
bucket = bucket.next;
nums[idx++] = bucket.num;
}
}
}
private void insertHelper(Bucket bucket, int num) {
Bucket in = new Bucket();
in.num = num;
while ( bucket.next != null && bucket.next.num < num ) {
bucket = bucket.next;
}
if ( bucket.next == null ) {
bucket.next = in;
in.front = bucket;
} else {
in.next = bucket.next;
in.front = bucket;
bucket.next.front = in;
bucket.next = in;
}
}
}
1 | public class BucketSort { |
代码时间效率对比
其中基于比较的排序算法：冒泡排序、插入排序、希尔排序、归并排序、堆排序、快速排序。
其它排序算法：计数排序、基数排序、桶排序。
由算法导论可知，基于比较的排序算法的最坏时间复杂度一定是$nlog(n)$，而另外三个算法则没有这个限制，它们的复杂度都在$O(n)$。
时间程序效率对比，可能会受到个人代码编写的影响带来一些偏差，但是大概没有问题：
其中T表示序列个数，N表示序列的最大长度（在N一下进行随机），K表示取值上界（下界默认为大于等于0）。
| 算法\取值 | T=100000, N=20, K=100 | T=100000, N=50, K=100 | T=100000, N=50, K=200000 | T=100000, N=100, K=200000 | T=10000, N=1000, K=200000 | T=1000, N=20000, K=20000 | T=5000, N=10000, K=200000 |
|---|---|---|---|---|---|---|---|
| 冒泡排序 | 26ms | 128ms | 133ms | 457ms | 2590ms | 119063ms | 138309ms |
| 插入排序 | 22ms | 51ms | 48ms | 124ms | 801ms | 29212ms | 38779ms |
| 希尔排序 | 22ms | 69ms | 67ms | 134ms | 239ms | 709ms | 1694ms |
| 归并排序 | 64ms | 167ms | 161ms | 305ms | 375ms | 892ms | 2180ms |
| 堆排序 | 25ms | 90ms | 84ms | 155ms | 242ms | 666ms | 1605ms |
| 快速排序 | 38ms | 93ms | 87ms | 145ms | 193ms | 519ms | 1201ms |
| 计数排序 | 32ms | 30ms | 10828ms | 10633ms | 1301ms | 79ms | 760ms |
| 基数排序 | 35ms | 46ms | 99ms | 172ms | 146ms | 237ms | 689ms |
| 桶排序 | 44ms | 68ms | 66ms | 129ms | 125ms | 280ms | 688ms |
值得关注的点：
- 计数排序再取值范围与序列长度差距不大的情况下速度爆炸快。
- 基数排序平均来看是最快的，当然不能有非负数。
- 快速排序的稳定性是最好的。
- 插入排序在序列较短的情况下效率非常高。
快速排序作为最火的排序算法不是没有道理的，它有几点优势：速度快且稳定，$O(1)$的额外空间，能够处理负数。
特殊情况下，计数排序会十分有用。