完整排序算法代码：https://github.com/huangliu0909/Sort-Algorithms
归并排序 Merge sort
分治法，每次将一个数组均分成两部分，对这两部分进行merge。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 public static void merge_sort(int[] array, int start, int end) {
if(start < end) {
int mid = (end + start)/2;
merge_sort(array, start, mid);
merge_sort(array, mid + 1, end);
merge(array, start, mid, end);
}
}
public static void merge(int[] array, int start, int mid, int end) {
int[] left = Arrays.copyOfRange(array, start, mid + 1);
int[] right = Arrays.copyOfRange(array, mid + 1, end + 1);
//Arrays.copyOfRange左闭右开
int i = 0, j = 0, count = start;
while(i != left.length && j != right.length) {
if(left[i] < right[j]) {
array[count] = left[i];
count ++;
i ++;
}
else {
array[count] = right[j];
count ++;
j ++;
}
}
//更新count和i或者j
while(i < left.length) {
array[count] = left[i];
i ++;
count ++;
}
while(j < right.length) {
array[count] = right[j];
j ++;
count ++;
}
}
```
# Timsort
**Used in Java’s Arrays.sort() as well as Python’s sorted() and sort().**
混合自归并排序和插入排序。当数组中元素个数超过64，插入排序效率较低。Timsort中已经排序好的子数组被称作run。规定一个minRun的大小，即：如果一个run大小小于minRun，将它的后一个元素插入到合适的位置形成minRun。对于每个排序好的minRun，进行merge sort，初始size = run，size+= 2* size。
```Java
public static void tim_sort(int[] array, int RUN)
{
for (int i = 0; i < array.length; i += RUN)
{
insertion_sort(array, i, Math.min((i + RUN), (array.length - 1)));
}
for (int size = RUN; size < array.length; size = 2 * size)
{
for (int left = 0; left < array.length; left += 2 * size)
{
int mid = left + size - 1;
int right = Math.min((left + 2 * size - 1), (array.length - 1));
merge(array, left, mid, right);
}
}
}
桶排序 Bucket sort
原理是将数组的元素分布(scatter)到多个桶中，然后每个桶被单独排序，最后收集(gather)桶中元素得到结果。
时间复杂度：最优：$\Omega (n+k)$，最坏：$O(n^2)$，平均：$\Theta(n+k)$
最坏空间复杂度：$O(n*k)$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 public static int[] heapsort(int[] array) {
int[] h = new int[0];
for(int i = 0; i < array.length; i ++) {
h = arrAppend(h, array[i]);
int k = i;
while(h[k] > h[(int) Math.floor(k/2)]) {
swap(h, k, (int) Math.floor(k/2));
k = (int) Math.floor(k/2);
}
}
swap(h, 0, h.length - 1);
return heapify(h, h.length - 2);
}
public static int[] heapify(int[] array, int i) {
if(0 < i) {
int k = 0;
while(k + 2 <= i) {
if(array[k + 1] < array[k + 2]) {
swap(array, k, k + 2);
k = k + 2;
}
else {
swap(array, k, k + 1);
k = k + 1;
}
}
swap(array, 0, i);
return heapify(array, i - 1);
}
else return array;
}
圈排序 Cycle sort
https://www.geeksforgeeks.org/cycle-sort/
https://www.raychase.net/1814
交换次数最少的排序，与计数排序类似，但圈排序只给那些需要计数的数字计数。
圈排序又叫循环排序，是不稳定的原地排序算法。选择排序本来已经让写元素的次数变得很少了，但是圈排序可以让它更少：试想一下这种情况，位置 1 的元素应该放当前位置 3 的元素，选择排序把当前位置 3 的元素和位置 1 的元素互换——那么原本位置 3 的元素，直接就到达了最后它应该在的位置；但是原本位置 1 的元素呢，却有可能会被再换位置，也就是说，选择排序依然可能存在着某元素被换了不止一次地方。圈排序真正使得任一元素要么不动，要动也最多动一次。圈排序最好和最坏的时间复杂度都是 O(n2)，但是因为最小的写入次数，对于在写入非常慢的介质中排序来说，会有它的价值（例如在某些 Flash 闪存中）。