Content Table

常用排序

下面列举常用的排序算法的实现:

  • 冒泡排序
  • 插入排序
  • 选择排序
  • 快速排序
  • 归并排序
  • 堆排序

排序的时候, 需要大量的交换数组中的 2 个元素, 使用下面的函数 swap() 进行交换:

1
2
3
4
5
6
7
8
/**
* 交换数组中指定下标的 2 个元素的值
*/
public static void swap(int[] a, int indexA, int indexB) {
int temp = a[indexA];
a[indexA] = a[indexB];
a[indexB] = temp;
}

冒泡排序

原理:

  1. 比较相邻的元素,如果第一个比第二个大,就交换他们两个,把大的交换到后面。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
  5. 有 n 个元素的数组需要进行 n-1 轮
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 冒泡排序
*/
public static void bubbleSort(int[] a) {
for (int r = 1; r < a.length; ++r) { // r: round
for (int i = 0; i < a.length-r; ++i) {
// 如果 a[i] 大于 a[i+1], 则把大的交换到后面
if (a[i] > a[i+1]) {
swap(a, i, i+1);
}
}
}
}

插入排序

从整个待排序列中选出一个元素插入到已经有序的子序列中去,得到一个有序的、长度加一的子序列,直到整个序列的待插入元素为 0,则整个序列全部有序。

实现时选择数组的第一个元素作为有序序列 (因为一个元素肯定是有序的),然后逐渐将后面的元素插入到前面的有序序列中,直到整个序列有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 插入排序
*/
public static void insertSort(int[] a) {
for (int i = 1; i < a.length; ++i) {
int current = a[i];
int j = i;

while (j>0 && current<a[j-1]) {
a[j] = a[j-1];
j--;
}

a[j] = current;
}
}
1
2
3
4
5
6
7
8
// 使用冒泡的方式交换元素,简化代码,但是效率相对低一些
public static void insertSort(int[] a) {
for (int i = 1; i < a.length; ++i) {
for (int j = i; j>0 && a[j]<a[j-1]; --j) {
swap(a, j, j-1);
}
}
}

希尔排序 (Shell’s Sort) 是插入排序的一种又称缩小增量排序 (Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本,希尔排序是非稳定排序算法,该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是把元素按下标的一定增量分组 (可选 n/2),对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个数组恰被分成一组,算法便终止。

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 希尔排序
*/
public static void shellSort(int[] a) {
for (int gap = a.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < a.length; ++i) {
for (int j = i; j-gap>=0 && a[j]<a[j-gap]; j -= gap) {
swap(a, j, j-gap);
}
}
}
}

选择排序

选择排序 (Selection sort) 是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小 (或最大) 的一个元素,存放在序列的末尾,然后,再从剩余待排序元素中继续寻找最小 (大) 元素,然后放到此待排序序列的末尾。以此类推,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 选择排序
*/
public static void selectionSort(int[] a) {
for (int i = a.length - 1; i > 0; i--) {
int max = 0;
for (int j = 1; j <= i; j++) {
// 找到最大值的下表
if (a[j] > a[max]) {
max = j;
}
}

swap(a, max, i);
}
}

快速排序

快速排序的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

一趟快速排序的具体过程可描述为:从待排序列中任意选取一个元素 (通常选取第一个记录) 作为基准值,然后将记录中关键字比它小的记录都放置在它的位置之前,将记录中关键字比它大的记录都安置在它的位置之后。这样,以该基准值为分界线,将待排序列分成的两个子序列。

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
/**
* 使用快速排序对数组进行排序
*/
public static void quickSort(int[] a) {
quickSort(a, 0, a.length-1);
}

/**
* 使用快速排序对数组 a 中 low 到 high 之间的元素进行排序
*/
public static void quickSort(int[] a, int low, int high) {
if (low < high) {
int pivot = partition(a, low, high);

quickSort(a, low, pivot-1);
quickSort(a, pivot+1, high);
}
}

/**
* 分区: 把数组中小于 a[pivot] 的数放到 pivot 的左边, 大于 a[pivot] 的数放到 pivot 的右边
*
* @return 返回分区的下标 pivot
*/
public static int partition(int[] a, int low, int high) {
int pivotValue = a[low]; // pivotValue 作为参考值缓存起来,a[low] 空出来了

// 数组右边的数大于等于 pivotValue
// 数组左边的数小于等于 pivotValue
while (low < high) {
// 提示: low 和 high 的 ++ 与 -- 没有在赋值的时候进行, 而是在循环内执行,
// 避免 while 中 low == high 时外部进行 ++, --, 导致 low > high

// 从右向左找到第一个小于 pivotValue 的数,放到 a[low],此时则 a[high] 空出来
while (low < high && a[high]>=pivotValue) {
--high;
}
a[low] = a[high];

// 从左向右找到第一个大于 pivotValue 的数,放到 a[high],此时则 a[low] 空出来
while (low < high && a[low]<=pivotValue) {
++low;
}
a[high] = a[low];
}

// 循环结束时 low == high, pivot 的左边的数都小于 pivotValue, pivot 右边的数都大于 pivotValue
int pivot = low;
a[pivot] = pivotValue;

return pivot;
}

还有一种常见的做法是一趟中找到适合的 2 个数后一次性交换的逻辑

  • 数组右边的数大于 pivotValue
  • 数组左边的数小于等于 pivotValue (因为左边第一个数作为 pivotValue,需要跳过它进行比较)

测试数据: 5, 2, 6, 7, 5, 4, 8, 5

上面的方法是双边循环法进行分区,下面使用单边循环法进行分区:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 单边循环法分区
*
* @return 返回分区的下标 pivot
*/
public static int partition(int[] a, int low, int high) {
int pivot = a[low];
int mark = low; // mark 以及它前面的数据小于等于 pivot

for (int i = mark+1; i <= high; ++i) {
if (a[i] <= pivot) {
swap(a, ++mark, i); // 找到合适的数 a[i],区域 mark 扩大 1 个范围,然后交换 a[i] 和 a[mark]
}
}

swap(a, low, mark); // 把 pivot 放到中间

return mark;
}

归并排序

原理:

  1. 将待排序的数列分成若干个长度为 1 的子数列,然后将这些数列两两合并
  2. 得到若干个长度为 2 的有序数列,再将这些数列两两合并
  3. 得到若干个长度为 4 的有序数列,再将它们两两合并
  4. 直接合并成一个数列为止

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
/**
* 归并排序
*/
public static void mergeSort(int[] a) {
int[] o = a;
int[] t = new int[a.length];

for (int chunk = 1; chunk < a.length; chunk *= 2) {
for (int l = 0; l < a.length; l += 2*chunk) {
// 前 chunk 个元素和后续 chunk 个元素作为一组进行归并 (有序数组合并): [l,m) ~ [m,h)
int m = Math.min(l+chunk, a.length);
int h = Math.min(m+chunk, a.length);
merge(a, l, m, h, t);
}

// 一轮归并结束后, t 是此轮归并后的数组, 新一轮归并需要在前一轮归并的基础上进行
// 交互 a 和 t, 使得 a 是归并后的数组
int[] x = a;
a = t;
t = x;
}

// 归并结束时, a 的数据是有序的, 但是此时 a 不一定指向传入进来的数组, 也就是说 a 不一定等于 o,
// 需要复制数组 a 到原来的数组 o 中,这样函数外访问传入的数组才是排序后的有序数组 (引用使用传值传递)
System.arraycopy(a, 0, o, 0, a.length);
}

/**
* 有序数组合并
* 把数组 a 中的 [l, m) 到 [m, h) 部分合并为有序数列到 t 的 [l, h) 中
*/
public static void merge(int[] a, int l, int m, int h, int[] t) {
int i = l;
int j = m;
int k = l;

while (i < m && j < h) {
if (a[i] < a[j]) {
t[k++] = a[i++];
} else {
t[k++] = a[j++];
}
}

while (i < m) {
t[k++] = a[i++];
}

while (j < h) {
t[k++] = a[j++];
}
}

堆排序

堆排序 (Heap Sort) 是利用堆进行排序的方法,其基本思想为:将待排序列构造成一个大顶堆 (或小顶堆),整个序列的最大值 (或最小值) 就是堆顶的根结点,将根节点的值和堆数组的末尾元素交换,此时末尾元素就是最大值 (或最小值),然后将剩余的 n-1 个序列重新构造成一个堆,这样就会得到 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
/**
* 使用堆排序对数组进行排序
*/
public static void heapSort(int[] a) {
// 把整个数组调整为大顶堆
for (int parent = a.length/2-1; parent>=0; --parent) {
adjustHeap(a, parent, a.length);
}

// a[0] 为最大的数,和最后一个交换,再把数组调整为大顶堆
for (int end = a.length-1; end > 0; --end) {
swap(a, 0, end);
adjustHeap(a, 0, end);
}
}

/**
* 调整 a 为大顶堆, parent 的左右子树已经是大顶堆
*/
public static void adjustHeap(int[] a, int parent, final int end) {
int temp = a[parent];

for (int left = parent*2+1; left < end; left = parent*2+1) {
// max 存储左右节点中最大数的下标
// left 存储左子节点的下标
// right 存储右子节点的下标
int max = left;
int right = left + 1;

if (right<end && a[left]<a[right]) max = right; // 左右子节点中最大的数
if (temp >= a[max]) break; // parent 已经是最大值, 说明已经是大顶堆, 不需要再进行调整了

// a[parent] 存储左右子节点中的最大值, 并把 parent 指向此节点
a[parent] = a[max];
parent = max;
}

a[parent] = temp;
}