手撕排序算法3：优化版冒泡排序和快速排序的三种方法（包括三数取中，小区间优化,递归版本）（上）

void BubbleSort(int* a, int n)
{
  int i = 0;
  for (i = 0; i < n - 1; i++)//一共冒泡n-1趟(i控制趟数)
  {
    int flag = 1;//假设有序
    int j = 0;
    for (j = 0; j < n - 1 - i; j++)//(j控制每一趟比较的次数)
      //第一趟比较n-1次,第二趟比较n-2次(因为第二趟就不需要比较最后一个数字了,因为最后一个数字已经是最大的了)....,归纳为n-1-i次
    {
      if (a[j] > a[j + 1])
      {
        Swap(&a[j], &a[j + 1]);
        flag = 0;//发生交换,改为无序
      }
    }
    if (flag == 1)//有序,所以无需再进行排序,直接break
    {
      break;
    }
  }
}

void QuickSort(int* a, int n)
{
  int begin = 0;
  int end = n - 1;
  int pivot = begin;
  int key = a[begin];
  while (begin < end)
  {
    //左边有坑,右边找小,放到左边
    while (a[end] >= key && begin < end)
    {
      end--;
    }
    if (begin < end)
    {
      //小的放到左边的坑里,自己形成了新的坑位
      a[pivot] = a[end];
      pivot = end;
    }
    //右边有坑,左边找小,放到右边
    while (a[begin] <= key && begin < end)
    {
      begin++;
    }
    if (begin < end)
    {
      //大的放到右边的坑里,自己形成了新的坑位
      a[pivot] = a[begin];
      pivot = begin;
    }
  }
  pivot = begin;
  a[pivot] = key;
}

void QuickSort(int* a, int left,int right)//这里为了进行函数递归,把形参改为左右"指针",方便进行递归
{
  if (left >= right)//当区间长度小于等于1时,无需进行排序了,如果不加这一条,函数将进入死递归
  {
    return;
  }
  int begin = left;
  int end = right;
  int pivot = begin;
  int key = a[begin];
  while (begin < end)
  {
    //左边有坑,右边找小,放到左边
    while (a[end] >= key && begin < end)
    {
      end--;
    }
    if (begin < end)
    {
      //小的放到左边的坑里,自己形成了新的坑位
      a[pivot] = a[end];
      pivot = end;
    }
    //右边有坑,左边找小,放到右边
    while (a[begin] <= key && begin < end)
    {
      begin++;
    }
    if (begin < end)
    {
      //大的放到右边的坑里,自己形成了新的坑位
      a[pivot] = a[begin];
      pivot = begin;
    }
  }
  pivot = begin;
  a[pivot] = key;
  //这里我们将[left,right]这个区间分为这么三个部分
  //[left,pivot-1]  pivot [pivot+1,right]
  QuickSort(a, left, pivot - 1);
  QuickSort(a, pivot + 1, right);
  //快排的递归思想就像是二叉树的深度优先遍历.
  //根 左区间 右区间 根 左区间 右区间 根 左区间 右区间 根 左区间 右区间 .........,
  //单个区间就像是叶子节点
}