7种经典排序算法总结和实现

基于比较的7种排序算法

冒泡排序BubbleSort

介绍

冒泡排序的原理比较简单,主要是两两比较,每次把比较大的数据放在后面,这样一次下来,最大的数就放在数组最后了。然后依次类推。

主要特性如下:

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定

步骤

  • 从索引为0的位置开始,往后依次两两比较,把大的数放在后面,小的数放在前面,这样一次下来最大的数就在数组末尾了(n);
  • 最后一个数完成排序,退出排序工作,也就是令n–;
  • 重复第一步,直到n=0;

源码

1
2
3
4
5
6
7
8
9
10
11
12
public static void bubbleSort(int[] a){
int temp = 0;
for(int i = 0; i < a.length - 1; i++){// 遍历第i次,每一次排好后面的1个
for(int j = 0; j < a.length - i - 1; j++){// 从a[0]开始,依次去后面尚未排序的元素两两比较,大的置后
if(a[j] > a[j + 1]){
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}

优化方案

  • 每次排序,如果没有发生任何一次交换位置,说明已经是有序的了。因此可以用一个标识位记录是否交换了位置,如果没有则直接结束排序工作。

选择排序SelectionSort

介绍

选择排序每次用一个记录最小值的下标,然后把下标和前面未排序的序列中的第一个数据交换位置。依次类推。

主要特性如下:

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
选择排序 O(n^2) O(n^2) O(n^2) O(1) 稳定

步骤

  • 在未排序序列中找到最小元素,存放到排序序列的起始位置。
  • 再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾
  • 重复上面2个步骤,直到所有元素均排序完毕。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void selectionSort(int[] a){
int temp = 0;
int min = 0;
for(int i = 0; i < a.length - 1; i++){// 最后2个一比较就出结果了,所以最后一个不用比较了。i个元素排好序。
min = i;
for(int j = i + 1; j < a.length; j++){// 需要和全部未排序序列比较
if(a[min] > a[j]){
min = j;
}
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}

插入排序InsertionSort

介绍

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
—摘自维基百科

主要特性如下:

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
插入排序 O(n^2) O(n) O(n^2) O(1) 稳定

步骤

  • 从第一个元素开始,认为是有序的;
  • 取出下一个元素继续,往前面比较,如果遇到比新元素小的,则把该元素往后移动一位;
  • 重复步骤2,直到找到已排序中小于或等于新元素的位置;
  • 把新元素插入到该位置中;
  • 重复步骤2-5;

源码

1
2
3
4
5
6
7
8
9
10
11
public static void insertionSort(int[] a){
for(int i = 1; i < a.length; i++){ // 因为第一个元素可以认为是有序的,所有从索引为1开始
int key = a[i];
int j = i;
while(j > 0 && a[j - 1] > key){ // 如果前面元素大于新元素
a[j] = a[j - 1]; // 该大元素往后移动1位
j--;
}
a[j] = key; // 把新元素插入到找到的位置当中
}
}

希尔排序ShellSort

介绍

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

—摘自维基百科

主要特性如下:

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
希尔排序 O(nlogn)~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定

步骤

  • 假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:
    13 14 94 33 82
    25 59 94 65 23
    45 27 73 25 39
    10
  • 然后我们对每列进行排序:
    10 14 73 25 23
    13 27 94 33 39
    25 59 94 65 82
    45
  • 将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:
    10 14 73
    25 23 13
    27 94 33
    39 25 59
    94 65 82
    45
  • 排序之后变为:
    10 14 13
    25 23 33
    27 25 59
    39 65 73
    45 94 82
    94
  • 最后以1步长进行排序(此时就是简单的插入排序了)。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void shellSort(int[] a) {
int size = a.length;
// 初始步长为数组长度1/2,每次减半
for(int gap = size / 2; gap > 0; gap /= 2) {
for (int i = 0; i < gap; i++) { // 分别处理每个步长分组
for (int j = i + gap; j < size; j += gap) { // 插入排序
if (a[j] < a[j - gap]) {
int temp = a[j];
int k = j - gap;
while (k >= 0 && a[k] > temp) {
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = temp;
}
}
}
}
}

归并排序MergeSort

介绍

归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(nlogn)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。
— 摘自维基百科

主要特性如下:

归并算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定

步骤

  • 先考虑合并2个有序数组:基本思路是比较2个数组中最前面的数,谁小就取谁并填到合并数组中,取后其数组索引往后移动一位。然后再重新比较,直到其中的一个数组为空,最后把另一个数组的多出来的元素直接复制到合并数组中。
  • 再考虑递归分解:基本思路是把数组分解为左右2个数组,然后再对这2个数组递归分解,直到分解出来的数组只有1个元素,此时可认为这个数组是有序的,然后执行上面的合并步骤即可。

源码

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 int[] mergeSort(int[] a) {
if(a.length == 1) { // 先分解到最小数组,然后一层层合并
return a;
}
int half = a.length / 2;
int[] a1 = new int[half];
int[] a2 = new int[a.length - half];
System.arraycopy(a, 0, a1, 0, a1.length); // 新建左边数组
System.arraycopy(a, half, a2, 0, a2.length); // 新建右边数组
a1 = mergeSort(a1);
a2 = mergeSort(a2);
return mergeSortSub(a1, a2);
}
public static int[] mergeSortSub(int[] a1, int[] a2){
int[] result = new int[a1.length + a2.length];
int i = 0; // 记录左数组下标
int j = 0; // 记录右数组下标
int k = 0; // 记录合并数组下标
while(true) {
if(a1[i] < a2[j]) { // 左边数组元素小于右边,左边元素放到合并数组中
result[k] = a1[i];
i++;
if(i > a1.length - 1) { // 左数组已全部遍历
break;
}
}else { // 左边数组元素大于等于右边,右边元素放到合并数组中
result[k] = a2[j];
j++;
if(j > a2.length - 1) { // 右数组已全部遍历
break;
}
}
k++; // 移动合并数组下标
}
// 把左右数组中元素比较多的那个数组多余的元素填到合并数组中
for(; i < a1.length; i++) {
result[++k] = a1[i]; // 因为上面赋值完后没执行k++,所以k指向的是最后赋值的下标,所以这里需要先++k
}
for(; j < a2.length; j++) {
result[++k] = a2[j];
}
return result;
}

堆排序HeapSort

介绍

堆排序在top问题中使用比较频繁。堆排序是使用二叉树来实现的,不过实质上还是二维数组。二叉树是一个近似完全二叉树。

堆中二叉树特性(序号从0开始):

  • 父节点的键值总是>=(<=)任何一个子节点的键值;
  • 每个节点的左右子树都是一个二叉堆(都是最大堆或最小堆);
  • 树里面每个节点的子女和双亲节点都可以根据当前节点的序号求出:
    • parent(i) = (i-1)/2;
    • left(i) = 2*i + 1;
    • right = 2*i + 2;
  • 非叶子节点 = n / 2 -1;

堆排序主要特性如下:

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定

步骤

  • 构造最大堆:若数组长度为size,因为单个元素(也就是叶子节点)可以看成是最大堆,则从size/2开始的元素是最大堆。于是从size/2-1开始,向前依次构造最大堆,这样就能保证,构造到某一个点,它的左右子树都是最大堆。
  • 堆中排序:由于堆是用数组模拟的。得到一个大根堆后,数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点,并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换,再对heap[0…n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换,再对heap[0…n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间,故操作完后整个数组就是有序的了。
  • 最大堆调整(Max_Heapify):该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整,使得子节点永远小于父节点 。

源码

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
/*
* 堆排序(从小到大)
*
* 说明:2个for循环,第一个用于初始化最大堆,第二个用于交换root数据和调整堆;
*/
public static void heapSortAsc(int[] a) {
int tmp;
int arraySize = a.length;
// 初步全局调整:从第一个非叶子节点开始,调整size/2-1次,也就是对所有非叶子节点进行调整
for (int i = arraySize / 2 - 1; i >= 0; i--) {
maxHeapDown(a, i, arraySize - 1);
}
// 把a[0]依次与最后一个节点调换,然后调整最最大堆,然后需要调换的节点数量-1
for (int i = arraySize - 1; i >= 0; i--) {
// 交换a[0]和a[i]。交换后,a[i]是a[0...i]中最大的。
tmp = a[0];
a[0] = a[i];
a[i] = tmp;
// 局部调整:从root开始,只需要调整一次,调整的是尚未交换数据的节点
maxHeapDown(a, 0, i - 1);
}
}
/*
* (最大)堆的向下调整算法
*
* 注:数组实现的堆中,第n个节点的左孩子的索引值是(2n+1),右孩子的索引是(2n+2)。
* 其中,n为数组下标索引值。
*
* 参数说明:
* a -- 待排序的数组
* start -- 被下调节点的起始位置(一般为0,表示从第1个开始)
* end -- 截至范围(一般为数组中最后一个元素的索引)
*/
public static void maxHeapDown(int[] a, int start, int end) {
int current = start; // 当前(current)节点的位置
int left = 2 * current + 1; // 左(left)孩子的位置
int tmp = a[current]; // 当前(current)节点的大小
// 依次遍历其子树
for (; left <= end; current = left, left = 2 * left + 1) {
// "left"是左孩子,"left+1"是右孩子
if (left < end && a[left] < a[left + 1]) {
left++; // 左右两孩子中选择较大者
}
if (tmp >= a[left]) // 调整结束
break;
else { // 交换值
a[current] = a[left];
a[left] = tmp;
}
}
}

快速排序QuickSort

介绍

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n^2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
—摘自维基百科

快排通常明显比其他nlog(n)的算法更快,所以被广泛引用。在笔试的过程中更是可以说是必考。可见掌握快排的重要性。快排主要特性如下:

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn)~O(n) 不稳定

步骤

  • 选定基准数:从数组中选出一个元素作为基准数;
  • 分区过程:将比基准数大的放在右边,小于或等于基准数的放在左边;
  • 再对左右区间递归执行第二步,直至各个区间都只有一个元素;

源码(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
public static void quickSort(int[] a, int begin, int end){
if(begin < end){ // 如果区间不是只有一个元素,则继续分区
int i = begin;
int j = end;
int pivot = a[begin]; // 保存基准数,并在此处挖坑
while(i < j){
while(i < j && a[j] >= pivot){ // 在右边寻找比基准数小的元素
j--;
}
if(i < j){
a[i] = a[j]; // 找到一个比基准数小的元素,扔到左边,在j处挖坑
i++; // i开始移动
}
while(i < j && a[i] < pivot){ // 在左边寻找比基准数大的元素
i++;
}
if(i < j){
a[j] = a[i]; // 找到一个比基准数大的元素,扔到左边,在i处挖坑
j--;
}
}
a[i] = pivot;// 此时i == j,存在一个坑,把基准数填下
quickSort(a, begin, i - 1); // 对左区间递归
quickSort(a, i + 1, end); // 对右区间递归
}
}

总结

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 稳定
插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序 O(nlogn)~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn)~log(n) 不稳定

附录


参考文档