显示目录

常用排序

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

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

排序的时候, 需要大量的交换数组中的 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. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 冒泡排序
*/
public static void bubbleSort(int[] a) {
for (int i = 1; i < a.length; ++i) {
for (int j = 0; j < a.length-i; ++j) {
// 如果 a[j] 大于 a[j+1], 则把大的交换到后面
if (a[j] > a[j+1]) {
swap(a, j, j+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-1; 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 - gap; j>=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 = 0; i < a.length-1; i++) {
int minIndex = i;

for (int j = i+1; j < a.length; ++j) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}

swap(a, i, minIndex);
}
}

快速排序

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

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

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]; // 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, low 右边的数都大于 pivotValue
int pivot = low;
a[pivot] = pivotValue;

return pivot;
}

一趟中找到大于和小于的数后一次性交换的逻辑:

归并排序

原理:

  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
53
54
55
56
57
/**
* 归并排序
*/
public static void mergeSort(int[] a) {
int[] original = a;
int[] c = new int[a.length];

for (int n = 1; n < a.length; n += n) {
for (int i = 0; i < a.length; i += n*2) {
// 前 n 个元素和后 n 个元素作为一组进行归并 (有序数组合并)
int aFirst = i;
int aLast = aFirst + n - 1;
int bFirst = aLast + 1;
int bLast = bFirst + n - 1;
int cFirst = aFirst;

mergeSortedArray(a, aFirst, aLast, a, bFirst, bLast, c, cFirst);
}

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

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

/**
* 有序数组合并
*/
public static void mergeSortedArray(int[] a, int aFirst, int aLast,
int[] b, int bFirst, int bLast,
int[] c, int cFirst) {
int i = aFirst;
int j = bFirst;
int k = cFirst;

while (i<= aLast && j<= bLast && i<c.length && j<c.length) {
if (a[i] < b[j]) {
c[k++] = a[i++];
} else {
c[k++] = b[j++];
}
}

while (i<= aLast && i<c.length) {
c[k++] = a[i++];
}

while (j<= bLast && j<c.length) {
c[k++] = b[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;
}