拒绝水文！八大排序（二）【适合初学者】冒泡排序和选择排序

大家好，我是纪宁。

这篇文章介绍八大排序中思路最简单，但效率也是最低的两种排序算法！

冒泡排序

冒泡排序，可以说是每个人在接触编程时最先学会的一种排序。

冒泡排序基本思想

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端，但是在广泛适用后，冒泡排序可以用来排任意顺序。

动态图解

冒泡排序示例

假设要将已知无需数列按从小到大排列，将第一个元素与后面的元素依次比较，如果必后面的元素小，就与后面某个元素交换位置，然后用这个元素再依次往后比较，遇到比这个元素小的就与这个元素交换，直到最后一个元素，就完成了一趟冒泡排序，则最后一个元素一定是这个序列里最大的一个元素；然后开始第二趟冒泡排序，继续从第一个元素开始往后一次比较，遇到较小的就交换位置，直到倒数第二个数，那么最后倒数第二个数就变成了第二大的数…依次排完序列中所有的数，那么这个数的顺序就会变成从小到大，下面我用图来演示 ：

一趟冒泡后，11就到了它该在的位置。

因为每次冒泡比较的次数都会递减，所以写代码的时候就要控制一下。

void BubbleSort(int* a, int n)//冒泡排序
{
  for (int i = 0; i < n; i++)
  {
    int flag = 0;//如果一趟后ret还等于0，说明数据已经有序
    for (int j = 0; j < n - i - 1; j++)
    {
      if (a[j] > a[j + 1])
      {
        Swap(&a[j], &a[j + 1]);
        flag = 1;
      }
    }
    if (flag == 0)
      break;
  }
}

因为冒泡排序在时间复杂度上确实不太占优，所以我们一般可以加一个 falg 用来判断即将进行调整的那部分序列是否已经有序，如果已有序，那就不用再进行‘冒泡’了，直接退出循环。

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：稳定

选择排序

选择排序基本思想

每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

动态图解

每次‘选择’一个较大或者较小的数，放在指定位置。

这个思路非常简单，那就直接上代码了。

void SelectSort(int* a, int n)
{
  for (int j = 0; j < n; j++)
  {
    int mini = j;
    int maxi= n - j-1;
    for (int i = j; i < n-j; i++)
    {
      if (a[i] < a[mini])
      {
        mini = i;
      }
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
    }
    Swap(&a[mini], &a[j]);
    if (maxi == j)
    {
      maxi = mini;//最大值如果在 j 这个位置的话，结果这个位置被换成了min 的值
    }
    Swap(&a[maxi], &a[n-1-j]);
  }
}

每次将最大值和最小值的下标找出来，与相应位置的数进行交换，但如果每次要直接找一个剩余序列的最大值和最小值的话，就需要判断最大值的下标对否恰好和最小值需要交换位置的下标重合，防止大的数据被‘调包’。