摘自 数据结构与算法之美 | 极客时间

目录

1. 排序算法基础

1.1 常见排序算法的时间复杂度

排序算法有很多种,最常用的包括:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。按照时间复杂度可分为三类O(n^2)O(nlogn)O(n),如下图所示:

常见排序算法的时间复杂度
常见排序算法的时间复杂度

1.2 如何分析一个排序算法

  1. 最好情况、最坏情况、平均时间复杂度
  2. 时间复杂度的系数、常数、低阶
  3. 比较次数交换(或移动)次数

1.3 排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量。不过,针对排序算法的空间复杂度,我们还引入了一个新的概念,原地排序(Sorted in Place)。原地排序算法,就是特指空间复杂度是O(1)的算法

本文提到的冒泡、插入、选择排序,都是原地排序算法

1.4 排序算法的稳定性

仅仅用执行效率内存消耗来衡量排序算法的好坏是不够的。针对排序算法,还有一个重要的度量指标,稳定性。这个概念是说,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变,那么这个算法就是稳定的

1.5 有序度/逆序度

1. 有序度

有序度是数组中具有有序关系元素对的个数:

有序元素对:a[i] <= a[j], 如果 i < j

同理,对于一个倒序排列的数组,例如6, 5, 4, 3, 2, 1有序度是0;对于一个完全有序的数组,例如1, 2, 3, 4, 5, 6有序度是n*(n-1)/2,也就是15,又称满有序度

2. 逆序度

逆序度的定义正好跟有序度相反:

逆序元素对:a[i] > a[j], 如果 i < j

3. 有序度和逆序度之间的关系

关于有序度、逆序度、满有序度这三个概念,还可以得到一个计算公式

逆序度 = 满有序度 - 有序度

本质上,排序的过程就是一种增加有序度、减少逆序度、最后达到满有序度的过程。

2. 冒泡排序

2.1 基本思路

冒泡排序(Bubble Sort)只会比较相邻的两个元素,看是否满足大小关系要求,如果不满足就让他俩交换一次冒泡会让至少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序工作。

元素 6 冒泡到了数组末端
元素 6 冒泡到了数组末端

可以看到,经过一次冒泡操作之后,6这个元素已经存储在正确的位置上。要想完成所有数据的排序,只需要进行n次这样的冒泡操作就可以:

6 次冒泡后,所有数据排序完成
6 次冒泡后,所有数据排序完成

2.2 优化技巧

实际上,上述冒泡的过程还可以进行优化。当某次冒泡操作已经没有数据交换的时候,就说明已经达到了完全有序不用再继续执行后续的冒泡操作了。如下图的例子,6个元素只需要进行4次冒泡:

四次冒泡后达到完全有序
四次冒泡后达到完全有序

2.3 算法分析

  1. 冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度O(1),是一个原地排序算法
  2. 在冒泡排序中,只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,因此冒泡排序是稳定的排序算法
  3. 冒泡排序的最好情况是要排序的数据已经是有序的了,只需要进行一次冒泡操作,时间复杂度为O(n)。而最坏情况是要排序的数据刚好都是倒序的,需要进行n次冒泡操作,所以最坏情况时间复杂度为O(n^2)

再来分析一下平均情况:要排序的数组初始状态下的有序度3元素个数n=6。所以排序完成之后终态满有序度n*(n-1)/2=15

冒泡排序包含了两个操作原子比较交换每交换一次,有序度就加 1。所以不管算法怎么改进,交换次数总是确定的,即为逆序度。上图的例子中就是12,所以要进行 12 次交换操作。

  • 最坏情况下,初始状态的有序度为0,要进行n*(n-1)/2次交换
  • 最好情况下,初始状态的有序度为n*(n-1)/2不需要进行交换
  • 取两者中间值n*(n-1)/4,来表示初始有序度既不是很高也不是很低平均情况

所以平均情况下,需要n*(n-1)/4次交换操作。比较操作肯定要比交换操作多,而复杂度的上限O(n^2),所以经过不严格的推导可得出,冒泡排序平均情况下的时间复杂度O(n^2)

2.4 Java 实现

// 冒泡排序,a 表示数组,n 表示数组大小
public void bubbleSort(int[] a, int n) {
    if (n <= 1) return;

    for (int i = 0; i < n; ++i) {
        // 提前退出冒泡循环的标志位
        boolean flag = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (a[j] > a[j+1]) { // 交换
                int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                    flag = true;  // 表示有数据交换      
            }
        }
        if (!flag) break;  // 没有数据交换,提前退出
    }
}

2.5 Go 实现

注:Go 语言提供了交换操作语法糖a[j], a[j+1] = a[j+1], a[j]

// 冒泡排序,a 表示数组,n 表示数组大小
func BubbleSort(a []int, n int) {
    if n <= 1 {
        return
    }
    for i := 0; i < n; i++ {
        // 提前退出标志
        flag := false
        for j := 0; j < n-i-1; j++ {
            if a[j] > a[j+1] {
                a[j], a[j+1] = a[j+1], a[j]
                //此次冒泡有数据交换
                flag = true
            }
        }
            // 如果没有交换数据,提前退出
            if !flag {
                break
            }
    }
}

3. 插入排序

3.1 基本思路

对于一个有序的数组,为了继续保持数据有序,我们只需要遍历数组找到数据应该插入的位置将其插入即可:

插入排序(Insertion Sort)正是借助上面的思想来实现排序。首先,我们将数组中的数据分为两个区间:已排序区间未排序区间初始已排序区间只有数组的第一个元素。插入算法的核心思想就是取未排序区间中的元素,在已排序区间中找到合适的插入位置并将其插入,重复这个过程直到未排序区间中元素为空,算法结束:

左侧为已排序区间,右侧为未排序区间
左侧为已排序区间,右侧为未排序区间

插入排序也包含两种操作原子:元素的比较移动

  • 对于不同的查找插入点方法(从头到尾、从尾到头),元素的比较次数是有区别的
  • 对于一个给定的初始序列移动操作的次数总是固定的,就等于逆序度
插入排序中,数据移动的次数等于逆序度
插入排序中,数据移动的次数等于逆序度

3.2 算法分析

  1. 插入排序算法的运行并不需要额外的存储空间空间复杂度O(1),也是一个原地排序算法
  2. 对于值相同的元素,我们可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序也是稳定的排序算法
  3. 最好情况下,数据全部有序,只需要从尾到头遍历所有数据,时间复杂度为O(n)最坏情况下,数据全部逆序,时间复杂度为O(n^2)。总的来看,平均时间复杂度O(n^2)

3.3 Java 实现

// 插入排序,a 表示数组,n 表示数组大小
public void insertionSort(int[] a, int n) {
    if (n <= 1) return;

    for (int i = 1; i < n; ++i) {
        int value = a[i];
        int j = i - 1;
        // 查找插入的位置
        for (; j >= 0; --j) {
            if (a[j] > value) {
                a[j+1] = a[j];  // 数据移动
            } else {
                break;
            }
        }
        a[j+1] = value; // 插入数据
    }
}

3.4 Go 实现

// 插入排序,a 表示数组,n 表示数组大小
func InsertionSort(a []int, n int) {
    if n <= 1 {
        return
    }
    for i := 1; i < n; i++ {
        value := a[i]
        j := i - 1
        // 查找要插入的位置并移动数据
        for ; j >= 0; j-- {
            if a[j] > value {
                a[j+1] = a[j]
            } else {
                break
            }
        }
        a[j+1] = value
    }
}

4. 选择排序

4.1 基本思路

选择排序(Selection Sort)的实现思路类似于插入排序:也是分为已排序区间未排序区间,但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾

4.2 算法分析

  1. 选择排序空间复杂度O(1),也是一种原地排序算法
  2. 最好、最坏、平均时间复杂度都为O(n^2)
  3. 选择排序是一种不稳定的排序算法,原因在于每次都要找剩余未排序元素中的最小值,并和前面的元素交换位置,这样破坏了稳定性

例如5, 8, 5, 2, 9这组数据,如果使用选择排序算法来排序的话,第一次找到最小元素为2,与第一个5交换位置,导致第一个5和中间的5前后顺序发生改变,所以就不稳定

4.3 Java 实现

// 选择排序,a 表示数组,n 表示数组大小
public static void selectionSort(int[] a, int n) {
    if (n <= 1) return;

    for (int i = 0; i < n - 1; ++i) {
        // 查找最小值
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }
        // 交换
        if (minIndex != i) {
            int tmp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = tmp;
        }
    }
}

4.4 Go 实现

// 选择排序,a 表示数组,n 表示数组大小
func SelectionSort(a []int, n int) {
    if n <= 1 {
        return
    }
    for i := 0; i < n; i++ {
        // 查找最小值
        minIndex := i
        for j := i + 1; j < n; j++ {
            if a[j] < a[minIndex] {
                minIndex = j
            }
        }
        // 交换
        if minIndex != i {
            a[i], a[minIndex] = a[minIndex], a[i]
        }
    }
}

5. 为何插入比冒泡更受欢迎

  • 冒泡排序插入排序不管怎样优化,其元素交换次数是一个固定值,即原始数据的逆序度
  • 代码实现上来看,冒泡排序的数据交换比插入排序的数据移动要更复杂交换需要3个赋值操作,而移动只需要1
// 冒泡排序中数据的交换操作:
if (a[j] > a[j+1]) { // 交换
    int tmp = a[j];
    a[j] = a[j+1];
    a[j+1] = tmp;
    flag = true;
}

// 插入排序中数据的移动操作:
if (a[j] > value) {
    a[j+1] = a[j];  // 数据移动
} else {
    break;
}

因此,虽然冒泡排序插入排序时间复杂度都为O(n^2),但是如果我们希望把性能优化做到极致,就首选插入排序

插入排序的算法思路也有很大的优化空间,可以参考 希尔排序 | Wikipedia

6. 小结

参考文章

  1. 数据结构与算法之美 | 极客时间
  2. 十大经典排序算法动画与解析,看我就够了!(配代码完全版)| 五分钟学算法