三大基础排序算法——冒泡排序、选择排序、插入排序_三大基本排序

前言

在此之前，我们已经介绍了十大排序算法中的：归并排序、快速排序、堆排序（还不知道的小伙伴们可以参考我的 「数据结构与算法」 专栏），今天我们就来介绍三大基础的排序算法：冒泡排序，选择排序和插入排序。

一、排序简介

排序算法（Sorting Algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。

稳定性
排序算法的稳定性并不是指最坏时间复杂度和最好时间复杂度是否相等，而是指相等的元素在经过排序之后其相对位置是否发生改变。

下图展示了稳定排序和不稳定排序之间的区别：

按照是否稳定可对十大排序算法做出如下分类：

时间复杂度
排序算法的时间复杂度分为最好时间复杂度、平均时间复杂度和最坏时间复杂度。

基于比较的排序算法的时间复杂度下限是 $O(n\log n)$。

二、冒泡排序

冒泡排序多次遍历数组，它比较相邻的元素，将不合顺序的进行交换，每一轮遍历都将下一个最大值放到正确的位置上。本质上，每个元素通过「冒泡」找到自己所属的位置。

经过 $i$ 次遍历后，数组末尾的 $i$ 项必然是最大的那 $i$ 项，因此冒泡排序最多需要遍历 $n-1$ 遍数组就能完成排序。

动画演示：

冒泡排序实现：

// a是待排序数组，n是数组长度
void bubble_sort(int a[], int n) {
    for (int i = n - 1; i; i--)
        for (int j = 0; j < i; j++)
            if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}
1
2
3
4
5
6

可以看出，若两个元素相等，则它们之间不会发生交换，因此冒泡排序具有稳定性。

冒泡排序通常被认为是效率最低的排序算法，因为在确定最终的位置前必须交换元素。注意到如果在一轮遍历中没有发生元素交换，就说明数组已经有序，此时可以提前终止以避免后续的无用功。

改进后的冒泡排序如下（又称短冒泡）：

void bubble_sort(int a[], int n) {
    int round = n - 1;  // 因为冒泡排序至多n-1轮遍历就会结束
    bool flag = true;  // flag为false时代表一轮遍历中没有发生元素交换
    while (round && flag) {
        flag = false;
        for (int i = 0; i < round; i++)
            if (a[i] > a[i + 1]) {
                flag = true;
                swap(a[i], a[i + 1]);
            }
        round--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

分析时间复杂度。若数组已经是有序的，则冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 $O(n)$。显然冒泡排序的平均时间复杂度和最坏时间复杂度均为 $O(n^2)$，且在最坏情况下，冒泡排序需要执行 $n(n-1)/2$ 次交换操作。

三、选择排序

选择排序在冒泡排序的基础上进行了改进，每次遍历数组时只做一次交换。要实现这一点，选择排序在每次遍历时寻找最小值，并在遍历完后将它放到正确的位置上。第一次遍历后，最小的元素就位；第二次遍历后，第二小的元素就位，以此类推。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/668384