排序是基础的算法问题，常见的排序有插入排序、冒泡排序、快速排序等，它们分别有不同的计算复杂度。插入排序和冒泡排序的复杂度为O(n^2),而快速排序的复杂度为O(nlogn)。因此，快速排序是最常用的排序方法之一，因为它的复杂度更。然而，对简单的排序方法的理解，还是有必要的。
插入排序 (Insert Sort)
插入排序的原理是将乱序的数据依次插入有序的数组中，其中每个数据的插入，都需要遍历一次已排好序的数组，因此会用到两层循环嵌套，复杂度为O(n^2)
插入排序实现方法
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class InsertSort {
public static int[] isort(int[] num) {
for (int i = 1; i < num.length; i++) {
int tmp = num[i];
int j;
for (j = i - 1; j >= 0 && tmp < num[j]; j--) {
num[j+1] = num[j];
}
num[j+1] = tmp;
}
return num;
}
}
|
冒泡排序 (Bubble Sort)
冒泡排序的原理是把乱序数据的最大值（或最小值）依次排到数组边缘，其中每个最大值（或最小值）的排出，都要遍历一次未排好序的数组，因此也会用到两层循环嵌套，复杂度为O(n^2)
冒泡排序实现方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class BubbleSort {
public static ArrayList<Integer> bsort(ArrayList<Integer> num) {
for (int i = 0; i < num.size() - 1; i++) {
for (int j = num.size() - 1; j > i; j--) {
if (num.get(j) < num.get(j-1)) {
int tmp = num.get(j);
num.set(j, num.get(j-1));
num.set(j-1, tmp);
}
}
}
return num;
}
}
|
快速排序 (Quick Sort)
快速排序是目前最常用的排序方法之一，因其计算效率高，复杂度只有O(nlogn)。它采用了很多巧妙的方法，例如双指针、递归等，其原位排序的特性又极大节省了运算所需的内存空间
快速排序实现方法
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 class Sorter {
public static void qsort(Integer head, Integer tail, ArrayList<Integer> input) {
if (head >= tail || input.isEmpty() || input.size() <= 1) {
return;
}
int i = head;
int j = tail;
// 1.任意取一个数，这里取数组中位数下标的对应值
Integer pivot = input.get((i + j) / 2);
System.out.print("before qsort:");
for (int k = head; k <= tail; k++) {
System.out.print(input.get(k)+" ");
}
System.out.print("\n");
// 2.排序，将小于pivot的值放在左边，大于pivot的值放在右边
while (i <= j) {
while (input.get(i) < pivot) {
// 无需变换位置，光标移到后一个位置
i++;
}
while (input.get(j) > pivot) {
// 无需变换位置，光标移到前一个位置
j--;
}
if (i < j) {
// 数据交换，然后继续移动光标
Integer tmp = input.get(i);
input.set(i, input.get(j));
input.set(j, tmp);
i++;
j--;
}
// 必须用else if而不能用if，交换后重新进入循环，否则可能会出现剩下的值卡在中间无法排序的现象
else if (i == j) {
System.out.println("i == j");
i++; // 剩下一个恰好等于pivot的数
}
}
// 3.分块,继续排序
System.out.print("after qsort:");
for (int k = head; k <= tail; k++) {
System.out.print(input.get(k)+" ");
}
System.out.print("\n\n");
// 递归继续排序
qsort(head, j, input);
qsort(i, tail, input);
}
}
|
测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(9);
list.add(7);
list.add(8);
list.add(5);
list.add(7);
list.add(10);
list.add(2);
list.add(4);
list.add(3);
list.add(1);
Sorter.qsort(0, list.size()-1, list);
System.out.print(list);
}
}
|
结果
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
| before qsort:9 7 8 5 7 10 2 4 3 1
after qsort:1 3 4 5 2 10 7 8 7 9
before qsort:1 3 4 5 2
after qsort:1 3 2 5 4
before qsort:1 3 2
after qsort:1 2 3
before qsort:1 2
i == j
after qsort:1 2
before qsort:5 4
after qsort:4 5
before qsort:10 7 8 7 9
i == j
after qsort:7 7 8 10 9
before qsort:7 7 8
after qsort:7 7 8
before qsort:7 8
i == j
after qsort:7 8
before qsort:10 9
after qsort:9 10
[1, 2, 3, 4, 5, 7, 7, 8, 9, 10]
|
过程分析
主要体现的是分而治之的思想，用两个指针来记录位置，每一次迭代，都将数组分成两块，将小于等于所取值的数据放于左边，大于所取值的数据放于右边，以栈的形式记录当前状态，再次递归排序。
上例求解的具体先后顺序如图所示：
维基上对快速排序的过程也有详细的图示：
Gif中表达的就是快速排序法，它取数组最后一个数据作为比较值，然后再交换到中间，大体思路是相同的