排序算法上——冒泡排序、插入排序和选择排序

1. 排序算法？

排序算法应该算是我们最熟悉的算法了，我们学的第一个算法，可能就是排序算法，而在实际应用中，排序算法也经常会被用到，其重要作用不言而喻。

经典的排序算法有：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。按照时间复杂度，可以分为以下三类。

2. 如何分析一个排序算法？

2.1. 排序算法的执行效率

• 最好情况、最坏情况、平均情况时间复杂度。我们不仅要知道一个排序算法的最好情况、最坏情况、平均情况时间复杂度，还要知道它们分别对应的原始数据是什么样的。有序度不同的数据，对于排序算法的执行时间肯定是有影响的。
• 时间复杂度的系数、常量、低阶。时间复杂度反映的是数据规模非常大时的一个增长趋势，但实际中，我们面临的数据可能是 10 个、100 个、 1000 个这样的小数据，因此之前我们忽略的系数、常量、低阶也要考虑进来。
• 比较次数和交换（或移动）次数。基于比较的排序算法涉及到两个主要操作，一个是元素比较大小，另一个是元素交换或移动。

2.2. 排序算法的内存消耗

• 算法的内存消耗可以用空间复杂度来衡量，针对排序算法的空间复杂度，我们引入了一个新的概念，原地排序(Sorted in place)，特指空间复杂度为 $O(1)$ 的排序算法，即指直接在原有数据结构上进行排序，无需额外的内存消耗。

2.3. 排序算法的稳定性

• 排序算法的稳定性指的是，如果待排序的序列中存在值相等的数据，经过排序之后，相等元素之间原有的先后循序不变。
• 比如一组数据 2， 9， 3， 4， 8， 3，按照大小排序之后就是 2， 3， 3， 4， 8， 9，如果排序后两个 3 的顺序没有发生改变，我们就把这种算法叫作稳定的排序算法，反之就叫作不稳定的排序算法。
• 我们学习排序的时候一般都是用整数来举例，但在真正的软件开发中，待排序的数据往往不是单纯的整数，而是一组对象，我们需要按照对象的某一个键值对数据进行排序。
• 假设我们有 10 万条订单数据，要求金额从小到大排序，并且金额相同的订单按照下单时间从早到晚排序。这时候，稳定排序就发挥了其作用，我们可以先按照下单时间对数据进行排序，然后再用稳定排序算法按照订单金额重新排序。

3. 冒泡排序（Bubble Sort）？

3.1. 冒泡排序算法实现

• 冒泡排序只会操作相邻的两个数据，将其调整到正确的顺序。一次冒泡会让至少一个数据移动到它应该在的位置，冒泡 n 次，就完成了 n 个数据的排序工作。

• 若某一次冒泡没有数据移动，则说明数据已经完全达到有序，不用再继续执行后续的冒泡操作，针对此我们可以再对刚才的算法进行优化。

• 代码实现

// O(n^2)
void Bubble_Sort(float data[], int n)
{
    int i = 0, j = 0;
    int temp = 0;
    int flag = 0;
    for(i = n-1; i > 0; i--)
    {
        flag = 0;
        for(j = 0; j < i; j++)
        {
            if(data[j+1] < data[j])
            {
                temp = data[j];
                data[j] = data[j+1];
                data[j+1] = temp;
                flag = 1;
            }
        }

        if(!flag)//If no data needs to be exchanged, the sort finishes.
        {
            break;
        }
    }
}

3.2. 冒泡排序算法分析

• 冒泡排序是一个原地排序算法，只需要常量级的临时空间。
• 冒泡排序是一个稳定的排序算法，当元素大小相等时，我们没有进行交换。
• 最好情况下，数据已经是有序的，我们只需要进行一次冒泡即可，时间复杂度为 $O(n)$。最坏情况下，数据刚好是倒序的，我们需要进行 n 次冒泡，时间复杂度为 $O(n^2)$。

3.3. 有序度和逆序度

• 有序度是数组中具有有序关系的元素对的个数。有序元素对定义：a[i] <= a[j], 如果 i < j。

• 完全倒序排列的数组，其有序度为 0；完全有序的数组，其有序度为 $C_n^2 = \frac{n*(n-1)}{2}$，我们把这种完全有序的数组叫作满有序度。
• 逆序度和有序度正好相反，逆序元素对定义：a[i] > a[j], 如果 i < j。
• 逆序度 = 满有序度 - 有序度。排序的过程就是一个增加有序度减少逆序度的过程，最后达到满有序度，排序就完成了。
• 在冒泡排序中，每进行一次交换，有序度就加 1。不管算法怎么改进，交换次数总是确定的，即为逆序度。
• 最好情况下，需要的交换次数为 0；最坏情况下，需要的交换次数为 $\frac{n * (n-1)}{2}$。平均情况下，需要的交换次数为 $\frac{n * (n-1)}{4}$，而比较次数肯定要比交换次数多，而复杂度的上限是 $O(n^2)$，所以，平均时间复杂度也就是 $O(n^2)$。

4. 插入排序（Insertion Sort）

4.1. 插入排序算法实现

• 往一个有序的数组插入一个新的元素时，我们只需要找到新元素正确的位置，就可以保证插入后的数组依然是有序的。

• 插入排序就是从第一个元素开始，把当前数据的左侧看作是有序的，然后将当前元素插入到正确的位置，依次往后进行，直到最后一个元素。
• 对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的，但移动次数是确定的就等于逆序度。
• 代码实现

// O(n^2)
void Insertion_Sort(float data[], int n)
{
    int i = 0, j = 0;
    int temp = 0;
    for(i = 1; i < n; i++)
    {
        temp = data[i];
        for(j = i; j > 0; j--)
        {
            if(temp < data[j-1])
            {
                data[j] = data[j-1];
            }
            else// The data ahead has been sorted correctly.
            {
                break;
            }
        }
        data[j] = temp; // insert the data
    }
}

4.2. 插入排序算法分析

• 插入排序是一个原地排序算法，只需要常量级的临时空间。
• 插入排序是一个稳定的排序算法，当元素大小相等时，我们不进行插入。
• 最好情况下，数据已经是有序的，从尾到头进行比较的话，每次我们只需要进行一次比较即可，时间复杂度为 $O(n)$。最坏情况下，数据刚好是倒序的，我们每次都要在数组的第一个位置插入新数据，有大量的移动操作，时间复杂度为 $O(n^2)$。
• 在数组中插入一个元素的平均时间复杂度为$O(n)$，这里，我们需要循环执行 n 次插入操作，所以平均时间复杂度为 $O(n^2)$。

5. 选择排序（Selection Sort）

5.1. 选择排序算法实现

• 选择排序就是从第一个元素开始，从当前数据的右侧未排序区间中选取一个最小的元素，然后放到左侧已排序区间末尾，依次往后进行，直到最后一个元素。

• 代码实现

// O(n^2)
void Selection_Sort(float data[], int n)
{
    int i = 0, j = 0, k = 0;
    int temp = 0;
    for(i = 0; i < n-1; i++)
    {
        k = i;
        for(j = i+1; j < n; j++)
        {
            if(data[j] < data[k])
            {
                k = j;
            }
        }
        if(k != i)
        {
            temp = data[i];
            data[i] = data[k];
            data[k] = temp;
        }
    }
}

5.2. 选择排序算法分析

• 选择排序是一个原地排序算法，只需要常量级的临时空间。
• 选择排序的最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度都为 $O(n^2)$，因为不管数据排列情况怎样，都要进行相同次数的比较。
• 选择排序是一个不稳定的排序算法，因为每次都要从右侧未排序区间选择一个最小值与前面元素交换，这种交换会打破相等元素的原始位置。

6. 为什么插入排序比冒泡排序更受欢迎？

交换排序和插入排序的时间复杂度都为 $O(n^2)$，也都是原地排序算法，为什么插入排序更受欢迎呢？

• 前面分析，插入排序的移动次数等于逆序度，冒泡排序的交换次数等于逆序度，但冒泡排序每次交换需要进行三次赋值操作，而插入排序每次移动只需要一次赋值操作，其相应的真实运行时间也会更短。

冒泡排序中数据的交换操作：
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;
}

7. 小结

• 冒泡排序和选择排序在实际中应用很少，仅仅停留在理论层次即可，选择排序算法还是挺有用的，而且其还有很大的优化空间，比如希尔排序。

参考资料-极客时间专栏《数据结构与算法之美》

获取更多精彩，请关注「seniusen」!