常见排序算法原理及实现——第一部分（冒泡排序、插入排序和选择排序）

引言

对于任何一个程序员来说，可能都不会陌生。你学的第一个算法，可能就是排序。排序算法有很多很多，我们只聊聊最常用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。我们分三次文章来学习。

一、如何分析一个排序算法

一般从以下几个方面衡量：

1.1 执行效率

• 最好、最坏、平均时间复杂度
  为什么要区分不同的时间复杂度呢？对于待排序的数据，有的接近有序，有的完全乱序，不同的数据源对排序算法的性能还是有影响的。
• 时间复杂度系数，常数、低阶
  时间复杂度描述的是排序算法耗时随着数据规模n增加而增加的趋势。但实际开发过程中，我们要排序的数据都在数百数千的量级，所以低阶及常数系数也是我们要考虑的点。
• 比较和移动的元素的次数
  基于比较的排序的排序算法，在执行过程中一般会经历两步，第一比较两个元素的大小；第二移动相应的元素。

1.2 内存消耗

简单理解就是排序需不需要再开辟新的空间，不需要开辟新空间就是原地排序，空间复杂度是O(1)，否则就是O(n)。

1.3 稳定性

稳定性指的是，如果待排序的数据中如果有相等的元素，在排序后相等元素的相对位置没有发生变化就是稳定的，否则就是不稳定的排序算法。举个例子：

待排序数据：5 2 8 3 5 4

排序后： 2 3 4 5 5 8

待排序数据中，下标为0 和 5的元素都是5，如果是稳定的排序算法，则在排序后，下标为0的那个5在下标为5的元素前面。

为什么要有稳定性呢？我们来看一个例子：假如现在需要对一个电商的“订单”进行排序，订单有两个属性，一个是下单时间，另一个是购买金额。假设现在需要按照金额从小到达进行排序，如果金额相同按照下单时间的早晚进行排序。怎么做呢？

这里就可以利用排序的稳定性，我们可以先按照下单时间的早晚进行排序，此时所有的订单就是按照下单时间早晚有序了，再按照下单金额进行排序，就可以得到结果了。这是因为排序的稳定性，排序后下单时间的早晚的相对顺序不会发生变化。

二、排序算法（冒泡、插入和选择排序）

2.1 冒泡排序

思路：每次只比较相邻的两个元素，如果不满足大小关系就交换他们的位置，每经过一次冒泡，一个元素就被放在了它应该在的位置。重复n次，直到所有的数据都有序。

我们用一个例子来看看，冒泡的过程: 4 5 6 3 2 1。

再看一个冒泡优化的例子：3 5 4 1 2 6

// 冒泡排序
void BubbleSort(vector<int>& nums)
{
    int size = nums.size();
    for (int i = 0; i < size; i++)
    {
      bool order = false;
        for (int j = 0; j < size-i-1; j++)
        {
            if (nums[j] > nums[j+1]){
              order = true;
                swap(nums[j], nums[j+1]);
            }
        }
    if (!order){ // 优化，如果在排序中途已经有序了就没必要再继续执行冒泡操作了
      break;
    }
    }
    cout << "Bubble Sort: " << endl;
    for (int i = 0; i < size; i++){
        cout << nums[i] << " " ;
    }
    cout << endl;
}

小结：

冒泡排序因为是相邻比较，不满足大小调减才会被交换位置，所以是稳定的；不需要开辟空间直接在原数组上操作，所以是原地排序。

最好时间复杂度是O(n)，最坏时间复杂度是O(n2)。

2.2 插入排序

我们先来看一个问题，在一个已经有序的数组中如何保证插入数据后，数组仍然有序。很简单，就是遍历数组找到适当的位置插入即可。

思路：插入排序将数组分为已经有序的部分和乱序的部分。初始有序部分只有第一个元素，然后从乱序部分取元素插入到有序部分的合适位置。

void InserSort(vector<int> &nums){
  int n = nums.size();
  for (int i = 1; i < n; i++)
  {
    int tmp = nums[i];
    for (int j = i-1; j >= 0; j--){
      if (nums[j] > tmp){
        nums[j+1] = nums[j];
      }
    }
    nums[j+1] = tmp;
  }
}

小结：

插入排序因为是遍历寻找合适位置，所以是稳定的；不需要开辟空间直接在原数组上操作，所以是原地排序。

在数据已经有序的情况下，从第二个元素开始，只需要比一次就能找到插入位置，需要执行n-1次，所以最好时间复杂度是O(n)；在数据倒序的情况下最坏时间复杂度是O(n2)。

2.3 选择排序

思路：在插入排序的基础上，每次从乱序部分中找出最小的元素位置的下标，插入到合适的位置。

void CSort::SelectSort(vector<int>& nums){
    int size = nums.size();
    int min = 0;
    for (int i = 0; i < size; i++)
    {
        min = i;
        for (int j = i+1; j < size; j++){
            if (nums[j] < nums[min]){
                min = j;
            }
        }
        if (min != i){
            swap(nums[min], nums[i]);
        }
    }
    cout << "Select Sort: " << endl;
    for (int i = 0; i < size; i++){
        cout << nums[i] << " " ;
    }
    cout << endl;
}

文章参考于<零声教育>的C/C++linux服务期高级架构