完整排序算法代码：https://github.com/huangliu0909/Sort-Algorithms
快速排序 Quicksort
快速排序是一种分治算法，不断找到pivot元素，将比它小的放在它左边，比它大的放在右边。双指针从头、从末尾分别开始与pivot比较，如果满足则移动，如果不满足则交换。1
2
3
4
5
6
7
8
9
10
11
12
13 public static void Quicksort(int[] array, int start, int end) {
if(end > start) {
int pivot = array[end];
int i = start, j = end;
while(i < j) {
swap(array, i, j);
if(array[i] < pivot) i ++;
if(array[j] > pivot) j --;
}
Quicksort(array, start, i - 1); // Before pi
Quicksort(array, i + 1, end); // After pi
}
}
堆排序 Heapsort
根据输入数据构造一个最大堆（堆：有序二叉树）将root(index = 0)与数组的最后一个点交换(index = len - 1)，即将最大值放在了数组的最后，整理前len - 1个使之成为最大堆，对前len - 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
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;
}
平滑排序 Smoothsort
是堆排序的一个变种
内省排序 Introsort
procedure sort(A : array):
let maxdepth = ⌊log(length(A))⌋ × 2
introsort(A, maxdepth)
procedure introsort(A, maxdepth):
n ← length(A)
if n ≤ 1:
return // base case
else if maxdepth = 0:
heapsort(A)
else:
p ← partition(A)
// assume this function does pivot selection, p is the final position of the pivot
introsort(A[0:p-1], maxdepth - 1)
introsort(A[p+1:n], maxdepth - 1)
奇偶排序 Odd–even sort
通过比较数组中相邻的（奇-偶）位置数字对，如果该奇偶对是错误的顺序（第一个大于第二个），则交换。可以使用并行计算，每个处理器处理一个值