排序算法(一): 初级比较排序

排序算法,作为算法中最基础的一部分。其中很多思想值得我们学习借鉴,故有必要了解、掌握一些常见常用的排序算法。排序算法根据是否使用比较元素的思想,可分为两大类:比较排序、非比较排序。本文,我们将对比较排序中的初级排序算法——Bubble Sort 冒泡排序、Selection Sort 选择排序、Insertion Sort 插入排序 一一进行介绍

abstract.png

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 趟排序过程后即排序完成

算法图解

BubbleSort.gif

特点

时间复杂度(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++) { // N-1趟冒泡
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;
}
}

测试结果:

BubbleSortResult.png

Selection Sort 选择排序

选择排序(Selection Sort),一种基于选择的排序算法。其每次在待排序元素中先选择最大(或最小)的元素,然后交换到开始(或最后)的合适的位置上完成排序,故此得名”选择排序”

算法流程

这里以对 N 个元素的数组 array 进行升序排列为例,讲解其算法流程:

  • 首先,找到数组中最小的元素;然后,将其与数组中的第一个元素交换位置
  • 其次,再在剩下待排序的元素中找到最小的元素。然后,将其与数组中的第二个元素交换位置
  • 选择排序的一轮”选择-交换”过程,可以完成对一个元素的排序,故对于N个元素排序而言,重复上述步骤,当其完成 N-1 趟排序过程后即排序完成

算法图解

SelectionSort.gif

特点

时间复杂度(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) );

// N-1 轮"选择-交换"过程
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;
}
}

测试结果:

SelectionSortResult.png

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)插入完毕,即排序完成

算法图解

InsertionSort.gif

特点

时间复杂度(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) );

// 从第2个元素开始插入,一直到插入最后一个元素
for(int i=1; i<size; i++) {
int temp = array[i]; // 欲插入元素
int j = i-1; // 索引i左边元素都是有序的
// 将 有序元素 中 大于欲插入元素temp 的元素均依次向后移动一位
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 = {7,3,8,1,4,9,2,5,6};
return caseArray;
}
}

测试结果:

InsertionSortResult.png

参考文献

  1. 算法(第4版) Robert Sedgewick、Kevin Wayne 著
0%