选择、冒泡与插入排序

发表于 | 更新于 | 分类于 ，

我们首先来讲一下基于比较的排序中最简单的几个。选择排序、冒泡排序和插入排序是排序算法中 \(O(n^2)\) 梯队的典型代表，放在一块来讲。

1. 选择排序

1.1 思路

从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作了。

1
2
3
4
for i = 1:n
    for j = i:n
        遍历并找到最小的元素 v
    将 v 放到位置 i 处
选择排序
选择排序

1.2 算法分析

  • 空间复杂度: \(O(1)\)
  • 时间复杂度：\(O(n^{2})\)

1.3 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void SelectionSort(int arr[], int len)
{
    for (int i = 0; i < len; ++i)
    {
        int minVal = arr[i], minLoc = i;
        for (int j = i + 1; j < len; ++j)
        {
            if (minVal > arr[j])
            {
                minVal = arr[j];
                minLoc = j;
            }
        }
        if (i != minLoc)
            Swap(arr[i], arr[minLoc]);
    }
}

2. 冒泡排序

2.1 原始算法

思路

反复遍历数组，每次都在当前指针的地方进行比较，如果前一个元素大于后一个元素，就将两个交换。就好像一块重重的石头不断往下沉一样。
每遍历一次，当前最大的元素都会沉到末尾。

1
2
3
4
for i = 1:n
    for j = 1:n-i
        if arr[j] > arr[j+1]
            Swap(arr[j], arr[j+1])

实现

1
2
3
4
5
6
7
8
9
10
11
void BubbleSort(int arr[], int len)
{
    for (int i = 0; i < len; ++i)
    {
        for (int j = 0; j < len - i - 1; ++j)
        {
            if (arr[j] > arr[j + 1])
                Swap(arr[j], arr[j + 1]);
        }
    }
}

2.2 改进版本1

思路

反观原始算法，存在一个缺陷(虽然实际上到处都是缺陷)。比如这样:

\[ 1: (1, 5, 2, 3, 4)\\ 2: (1, 2, 3, 4, 5)\\ 3: (1, 2, 3, 4, 5)\\ \vdots \]

如果早早地已经排好序了，冒泡法依旧会傻乎乎地走完全部过程。

我们可以在这个地方做一些修改：如果某一趟下来没有发生交换操作，说明已经排好序了，完全可以提前退出

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void ImprovedBubbleSort1(int arr[], int len)
{
    bool didSwap = true;
    for (int i = 0; i < len && didSwap; ++i)
    {
        didSwap = false;
        for (int j = 0; j < len - i - 1; ++j)
        {
            if (arr[j] > arr[j + 1])
            {
                Swap(arr[j], arr[j + 1]);
                didSwap = true;
            }
        }
    }
}

2.3 改进版本2

思路

考虑这种情况:假设某序列的一个较小区间前缀是无序的，而此后的区间都是有序的。

实例
实例

这个数列的特点是前半部分 (3，4，2，1) 无序，后半部分 (5，6，7，8) 升序，并且后半部分的元素已经是数列最大值。

在算法运行时真正作比较的只有一小段，而大部分未作比较。这是因为冒泡排序的运行过程中，有序区间会按照从末尾向前端不断扩张，因此任意时刻无序区间中最大的元素经过一次循环后必然会移到无序区间的末尾，成为有序区间的前缀，因此，在这种情况下继续对有序区间进行比较就是毫无意义的操作了。

不妨在每次循环记录最后一次发生交换的元素的位置，这说明这之后的元素已经有序，下一次循环不用比较这些元素。

可以看出，改进版本 1 是这个改进版本 2 的一种特殊情况 —— 当有序区间的前缀变为第一个元素时，就回退到了改进版本 1 的情况了。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void ImprovedBubbleSort2(int arr[], int len)
{
    //初始情况我们认为只有最后一个元素是有序的
    int orderedBeg = len - 1;
    for (int i = 0; i < len; ++i)
    {
        //记录在哪些地方发生了比较
        int cmpAt = 0;
        //从orderedBeg开始的元素都是有序的，无需比较
        for (int j = 0; j < orderedBeg; ++j)
        {
            if (arr[j] > arr[j + 1])
            {
                Swap(arr[j], arr[j + 1]);
                cmpAt = j;
            }
        }
        //最后一次比较的位置之后所有的元素都是有序的
        orderedBeg = cmpAt;
    }
}

3. 插入排序

思路

假设在插入第i个元素时， 前面的i-1个元素已经排好了序。这是用 v[i] 的排序码与 v[i-1],v[i-2]... 进行比较，找到了插入位置即将 v[i] 插入，原来位置上的元素向后移。

算法评估

  • 空间复杂度：\(O(1)\)
  • 时间复杂度：
    • 平均：\(\Theta(n^{2})\)
    • 最好(已排好序)：\(O(n)\)
    • 最坏(逆序)：\(O(n^{2})\)
  • 稳定性：稳定
  • 输入敏感性：高敏感
    插入排序的性能受输入序列中逆序对数量的影响很大。事实上，插入排序的实际运行时间正比于序列中的逆序数。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void InsertionSort(int arr[], int len)
{
    for (int i = 1; i < len; ++i)
    {
        int tailVal = arr[i];
        int j;
        //找到合适的位置
        for(j = i; j >= 1 && arr[j - 1] > tailVal; --j)
            //数组后移
            arr[j] =  arr[j - 1];
        //插入
        arr[j] = tailVal;
    }
}