前言

交换类排序两个常见的排序算法【冒泡排序】、【快速排序】

交换排序基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。

交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

1.冒泡排序

1.1冒泡排序动图

冒泡排序动图

1.2冒泡排序源代码

void BubbleSort(int* a, int n)
{
  assert(a);
 
  for (int j = 0; j < n - 1; ++j)
  {
    int exchange = 0;//这里的exchange的值作为是否交换的标志
    for (int i = 1; i < n - j; ++i)
    {
      if (a[i - 1] > a[i])
      {
        Swap(&a[i - 1], &a[i]);
        exchange = 1;
      }
    }
 
    if (exchange == 0)//一趟下来exchange的值还为0，证明就没有发生交换，也就是已经有序
    {
      break;
    }
  }
}

1.3冒泡排序的特性总结

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度： O(N^2)   最坏O(N^) 、最好O(N)

3. 空间复杂度： O(1)

4. 稳定性：稳定

2.快速排序👑

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。

其基本思想为： 任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。

2.1hoare版本实现思想

排序前

排序中

①先选出一个基准值key（一般是最左边或者最右边)

②然后右边【L】先走找比key小的值，找到了就停下，然后再左边找比key大的值，找到了也停下

③然后交换这两个数

经过上面三步，就动图就变成了下面的样子

🥇

🥈

排序后

由于是一个一个先走一个后走，肯定会出现相遇的时候，相遇就停下来。相遇后将相遇坐标的值和基准值key交换，这时就完成了单趟的hoare排序

【这时的key其实就是在正确的位置上了】

相遇时如下图

🥉

2.2hoare版本快排源代码

void QuickSort(int* a, int begin, int end)
{
  // 区间不存在，或者只有一个值则不需要在处理
  if (begin >= end)
  {
    return;
  }
 
  int left = begin, right = end;
  int keyi = left;
  while (left < right)
  {
    // 右边先走，找小
    while (left < right && a[right] >= a[keyi])
    {
      --right;
    }
 
    // 左边再走，找大
    while (left < right && a[left] <= a[keyi])
    {
      ++left;
    }
 
    Swap(&a[left], &a[right]);
  }
 
  Swap(&a[keyi], &a[left]);
  keyi = left;
 
  // [begin, keyi-1] keyi [keyi+1, end]
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi+1, end);
}

2.3分析先走

为什么左边做key，右边先走。

右边做key，左边先走。

这样就可以保证相遇位置的值小余或者等于key

我这边拿左边做key，右边先走的情况来讲解。

情况1🥇

这个情况比较好理解，就是上面最后相遇位置的值，也就是3，比6要小

情况2🥈

这个情况如下图所示

这边也可以去画一下左边做key，左边先走的情况，会发现相遇位置的值不能保证比key要小