排序算法，作为算法中最基础的一部分。其中很多思想值得我们学习借鉴，故有必要了解、掌握一些常见常用的排序算法。排序算法根据是否使用比较元素的思想，可分为两大类：比较排序、非比较排序。本文，我们将对比较排序中的初级排序算法——Bubble Sort 冒泡排序、Selection Sort 选择排序、Insertion Sort 插入排序 一一进行介绍
Bubble Sort 冒泡排序
冒泡排序（Bubble Sort），一种基于交换的的排序算法。其每次比较相邻两个元素，如果反序则交换。在一趟排序过程中，将待排序元素中最大(或最小)的元素交换到最后的准确的位置上，如同水里的气泡慢慢浮出水面一样，故此得名”冒泡排序”
算法流程
这里以对 N 个元素的数组 array 进行升序排列为例，讲解其算法流程：
- 第一趟排序开始时，对所有元素(array[0]～array[N-1])从头到尾依次比较相邻2个元素，如果反序(array[i] > array[i+1])则交换。很显然，第一趟排序结束时，最后一个位置上的元素array[N-1]一定是N个元素中最大的元素，即，array[N-1]排序完成
- 开始下一趟排序，其对剩下尚未排序的元素(array[0]～array[N-2])，从头到尾依次比较相邻2个元素，如果反序则交换
- 冒泡排序中的一趟排序过程可以完成对一个元素的排序，故对于N个元素排序而言，重复上述步骤，当其完成 N-1 趟排序过程后即排序完成
算法图解
特点
| 时间复杂度(average) |
时间复杂度(worst) |
时间复杂度(best) |
空间复杂度 |
稳定性 |
| $O(n^2)$ |
$O(n^2)$ |
$O(n)$ |
$O(1)$ |
稳定 |
Java 代码示例
Java 代码示例如下：
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
|
public class BubbleSort {
public static void sort() {
int[] array = getTestCase();
int size = array.length;
System.out.println("before sort: " + Arrays.toString(array) );
for(int i=0; i<size-1; i++) {
for(int j=0; j<size-1-i; j++ ) {
if( array[j] > array[j+1] ) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
System.out.println("after sort: " + Arrays.toString(array) );
}
private static int[] getTestCase() {
int[] caseArray = {5, 4, 3, 2, 1};
return caseArray;
}
}
|
测试结果:
Selection Sort 选择排序
选择排序（Selection Sort），一种基于选择的排序算法。其每次在待排序元素中先选择最大(或最小)的元素，然后交换到开始(或最后)的合适的位置上完成排序，故此得名”选择排序”
算法流程
这里以对 N 个元素的数组 array 进行升序排列为例，讲解其算法流程：
- 首先，找到数组中最小的元素；然后，将其与数组中的第一个元素交换位置
- 其次，再在剩下待排序的元素中找到最小的元素。然后，将其与数组中的第二个元素交换位置
- 选择排序的一轮”选择-交换”过程，可以完成对一个元素的排序，故对于N个元素排序而言，重复上述步骤，当其完成 N-1 趟排序过程后即排序完成
算法图解
特点
| 时间复杂度(average) |
时间复杂度(worst) |
时间复杂度(best) |
空间复杂度 |
稳定性 |
| $O(n^2)$ |
$O(n^2)$ |
$O(n^2)$ |
$O(1)$ |
不稳定 |
Java 代码示例
Java 代码示例如下：
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 class SelectionSort {
public static void sort() {
int[] array = getTestCase();
int size = array.length;
System.out.println("before sort: " + Arrays.toString(array) );
for(int i=0; i<size-1; i++) {
int minIndex = i;
for(int j=i+1; j<size; j++) {
if( array[j] < array[minIndex] ) {
minIndex = j;
}
}
if( minIndex != i ) {
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
System.out.println("after sort: " + Arrays.toString(array) );
}
private static int[] getTestCase() {
int[] caseArray = {3,1,7,4,2,5,6};
return caseArray;
}
}
|
测试结果:
Insertion Sort 插入排序
插入排序（Insertion Sort），一种基于插入的排序算法。其不断地将一个待排序元素向一个有序元素中去插入，故此得名”插入排序”
算法流程
这里以对 N 个元素的数组 array 进行升序排列为例，讲解其算法流程：
- 在插入排序中，索引index左边(=index)的元素则是待插入排序的。故其首先从第二个元素开始插入，即 index=1
- 对于待插入元素array[index]而言，其在左边有序的元素中的位置indexInsert，是最后一个大于array[index]的元素array[indexInsert]
- 在插入元素array[index]时，建议先将 indexInsert及其之后的有序元素 均向后移动一位再插入；而不是两两交换，通过移动的方式将array[index]移动至欲插入位置。此举可以大大提高时间效率
- 重复上述插入过程，直到最后一个元素(index=N-1)插入完毕，即排序完成
算法图解
特点
| 时间复杂度(average) |
时间复杂度(worst) |
时间复杂度(best) |
空间复杂度 |
稳定性 |
| $O(n^2)$ |
$O(n^2)$ |
$O(n)$ |
$O(1)$ |
稳定 |
Java 代码示例
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
|
public class InsertionSort {
public static void sort() {
int[] array = getTestCase();
int size = array.length;
System.out.println("before sort: " + Arrays.toString(array) );
for(int i=1; i<size; i++) {
int temp = array[i];
int j = i-1;
for( ; j>=0 && array[j]>temp; j--){
array[j+1] = array[j];
}
array[j+1] = temp;
}
System.out.println("after sort: " + Arrays.toString(array) );
}
private static int[] getTestCase() {
int[] caseArray = {3,1,7,4,2,5,6};
return caseArray;
}
}
|
测试结果:
参考文献
- 算法(第4版) Robert Sedgewick、Kevin Wayne 著
