基础排序算法
排序算法：让数据有序
排序算法中蕴含着重要的算法设计思想
选择排序法
思路：先把最小的拿出来，剩下的再把最小的拿出来，剩下的再把最小的拿出来…每次选择还没处理（排序）的元素里最小的元素
过程：
目前有一组元素：6 4 2 3 1 5
开辟一个新的空间进行操作
- 拿出最小的元素1，放入新的空间内，剩余元素6 4 2 3 5
- 剩余的元素拿出最小的元素2，放入新的空间内1的后面，剩余元素6 4 3 5
- 剩余的元素拿出最小的元素3，放入新的空间内2的后面，剩余元素6 4 5
- 剩余的元素拿出最小的元素4，放入新的空间内3的后面，剩余元素6 5
- 剩余的元素拿出最小的元素5，放入新的空间内4的后面，剩余元素6
- 剩下一个元素，拿出放入新的空间内5的后面，则新数组为：1 2 3 4 5 6
这样的排序过程占用了额外的空间
思考：可否进行原地（原空间）排序完成？
- arr[i…n)未排序
- arr[0…i)已排序 – 循环不变量
- arr[i…n)中的最小值要放到arr[i]的位置
已排好序的部分是最终排序的结果
开辟新空间的选择排序法
1
2
3
4
5
6
7
8
9
10
11
12
| public static <E extends Comparable<E>> void sortSpace(E[] arr) {
E[] newArr = (E[]) new Object[arr.length];
for (E value : arr) {
for (int j = 1; j < arr.length; j++) {
if (arr[j].compareTo(value) < 0) {
newArr[j] = arr[j];
}
}
}
}
|
原地排序的选择排序法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static <E extends Comparable<E>> void sort(E[] arr) {
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i; j < arr.length; j++) {
if (arr[j].compareTo(arr[minIndex]) < 0) {
minIndex = j;
}
}
SortingHelper.swap(arr, i, minIndex);
}
}
|
选择排序法的复杂度分析
通过测试来验证复杂度及排序的性能
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static void main(String[] args) {
int n1 = 1000;
int n2 = 10000;
int n3 = 100000;
Integer[] arr1 = ArrayGenerator.generateRandomArray(n1, n1);
Integer[] arr2 = ArrayGenerator.generateRandomArray(n2, n2);
Integer[] arr3 = ArrayGenerator.generateRandomArray(n3, n3);
SortingHelper.sortTest("SelectionSort", arr1);
SortingHelper.sortTest("SelectionSort", arr2);
SortingHelper.sortTest("SelectionSort", arr3);
}
|
上面的代码，根据数组长度分别测试一千、一万、十万，生成的随机数组进行排序，我们看下执行结果
随着数组的长度增长，时间也是线性直线增加。
插入排序法
思路：每次处理一个元素，把这个元素插入到前面已经排好序的数组中
过程：
- arr[0, 1)已经排好序
- arr[i…n)未排序
- 把arr[i]放到合适的位置
- 第一个元素(元素1)，第二元素(元素2)与元素1比较，如果元素2比元素1小，则进行交换位置，否则不动，进行下一步
- 第三个元素(元素3)，元素3比元素2小，则交换位置，继续元素3比元素1小，则交换位置，否则不动，进行下一步
- 第四个元素(元素4)，元素4比元素3小，则交换位置，继续元素4比元素2小，则交换位置，下来元素4比元素1大，则不进行交换，元素4已找到对应位置…
- 第五个元素…依次类推…
已排好序的部分是目前已经遍历的元素，还有未遍历的元素，不是最终结果
插入排序算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static <E extends Comparable<E>> void sort(E[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = i; j - 1 >= 0; j--) {
if (arr[j].compareTo(arr[j - 1]) < 0) {
SortingHelper.swap(arr, j, j - 1);
} else {
break;
}
}
}
}
|
将if语句中的条件合并到for循环中的条件中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public static <E extends Comparable<E>> void sortMerge(E[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = i; j - 1 >= 0 && arr[j].compareTo(arr[j - 1]) < 0; j--) {
SortingHelper.swap(arr, j, j - 1);
}
}
}
|
插入排序算法优化
注意：上述的步骤都是每次交换是三次操作，是否可优化呢？
- 暂存需要比较的元素，该元素比较前一个元素，如果前一个元素比该元素大，则将前一个元素赋值给该元素的位置
- 根据上一步，继续该方式，将大的值赋值给后一位元素（则是后移一位）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static <E extends Comparable<E>> void sortPlus(E[] arr) {
for (int i = 0; i < arr.length; i++) {
E t = arr[i];
int j;
for (j = i; j - 1 >= 0 && t.compareTo(arr[j - 1]) < 0; j--) {
arr[j] = arr[j - 1];
}
arr[j] = t;
}
}
|
插入排序复杂度分析及两种方式性能的对比
时间复杂度：O(n^2)
依旧是根据数组长度分别测试一千、一万、十万，生成的随机数组进行排序，我们看下测试代码及执行结果
1
2
3
4
5
6
7
8
9
| public static void main(String[] args) {
int[] dataSize = {1000, 10000, 100000};
for (int n : dataSize) {
Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
Integer[] arr2 = Arrays.copyOf(arr, arr.length);
SortingHelper.sortTest("InsertionSort", arr);
SortingHelper.sortTest("InsertionSortPlus", arr2);
}
}
|
插入排序法的重要特性
- 对于有序数组，插入排序的复杂度是O(n)的
- 对于无序数组，插入排序的复杂度依然是O(n^2)的
- 对比，不论是有序还是无序数组，选择排序的复杂度永远是O(n^2)的
换个角度实现插入排序法
基本逻辑是：从后向前扫描，对于每一个arr[i]，寻找arr[i…n)区间中需要插入的位置。
在具体找这个位置的时候，我们依然是暂存arr[i]到t这个变量，之后，只要t比当前的arr[j+1]还要大，说明t应该插入的位置还靠后，我们只需要让arr[j+1]平行移动到arr[j]的位置，然后j++，继续看下一个j。
1
2
3
4
5
6
7
8
9
10
11
| public static <E extends Comparable<E>> void sort2(E[] arr) {
for (int i = arr.length - 1; i >= 0; i--) {
E t = arr[i];
int j;
for (j = i; j + 1 < arr.length && arr[j].compareTo(arr[j + 1]) > 0; j--) {
arr[j] = arr[j + 1];
}
arr[j] = t;
}
}
|
Comparable接口
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
| package demo.helper.model;
public class Student implements Comparable<Student> {
private final String name;
private final int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public boolean equals(Object student) {
if (this == student) {
return true;
}
if (student == null) {
return false;
}
if (this.getClass() != student.getClass()) {
return false;
}
Student another = (Student) student;
return this.name.equals(another.name);
}
@Override
public int compareTo(Student another) {
return this.score - another.score;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", score=" + score +
'}';
}
}
|
