【数据结构与算法篇】手撕八大排序算法之交换排序

//冒泡排序
//时间复杂度：O(N^2)
void BubbleSort(int* a, int n)
{
  //控制冒泡排序的趟数
  for(int i = 0; i < n - 1; i++)
  {
    //假设数组有序
    int flag = 1;
    //控制每趟的过程
    for (int j = 0; j < n - 1 - i; j++)
    {
      if (a[j] > a[j + 1])
      {
         Swap(&a[j], &a[j + 1]);
         flag = 0;
      }
    }
    //说明没有发生交换，数组已经有序，跳出循环即可
    if (flag == 1) break;
  }
}

//快排(递归版本)
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end) return;
  int keyi = Partition(a, begin, end); 
  //前序遍历
  //递归基准值左边的区间
  QuickSort(a, begin, keyi - 1);
  //递归基准值右边的区间
  QuickSort(a, keyi + 1, end);
}

//hoare版本
int Partition1(int* a, int left, int right)
{
  int keyi = left;
  while (left < right)
  {
    //注意： 要加上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[left], &a[keyi]);
  return left;
}
//快排(递归版本)
void QuickSort(int* a, int begin, int end)
{
  //当区间不存在或者只剩一个元素，就回溯
  if (begin >= end) return;
  int keyi = Partition1(a, begin, end);
  //前序遍历
  //递归基准值左边的区间
  QuickSort(a, begin, keyi - 1);
  //递归基准值右边的区间
  QuickSort(a, keyi + 1, end);
}

//挖坑法
int Partition2(int* a, int left, int right)
{
  int key = a[left];
  //挖坑
  int hole = left;
  while (left < right)
  {
    //右边找小
    while (left < right && a[right] >= key)
    {
      right--;
    }
    a[hole] = a[right];
    hole = right;
    //左边找大
    while (left < right && a[left] <= key)
    {
      left++;
    }
    a[hole] = a[left];
    hole = left;
  }
  a[hole] = key;
  return hole;
}
//快排(递归版本)
void QuickSort(int* a, int begin, int end)
{
  //当区间不存在或者只剩一个元素，就回溯
  if (begin >= end) return;
  int keyi = Partition2(a, begin, end);
  //前序遍历
  //递归基准值左边的区间
  QuickSort(a, begin, keyi - 1);
  //递归基准值右边的区间
  QuickSort(a, keyi + 1, end);
}

//前后指针法
int Partition3(int* a, int left, int right)
{
  int prev = left;
  int cur = prev + 1;
  int keyi = left;
  //cur小于key，交换++prev与cur的位置
  //将大的位置翻滚时往后挪动，小的位置移动前面
  while (cur <= right)
  {
    if (a[cur] < a[keyi] && ++prev != cur)
    {
      Swap(&a[cur], &a[prev]);
    }
    cur++;
  }
  //将key与prev指向的元素交换。
  Swap(&a[prev], &a[keyi]);
  return prev;
}
//快排(递归版本)
void QuickSort(int* a, int begin, int end)
{
  //当区间不存在或者只剩一个元素，就回溯
  if (begin >= end) return;
  int keyi = Partition3(a, begin, end);
  //前序遍历
  //递归基准值左边的区间
  QuickSort(a, begin, keyi - 1);
  //递归基准值右边的区间
  QuickSort(a, keyi + 1, end);
}

//三数取中，返回下标
int GetMidIndex(int* a, int left, int right)
{
  int mid = (left + right) >> 1;
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right]) return mid;
    else if (a[left] > a[right]) return left;
    else return mid;
  }
  else //a[left] > a[mid]
  {
    if (a[mid] > a[right]) return mid;
    else if (a[right] > a[left]) return left;
    else return right;
  }
}
//hoare版本
int Partition1(int* a, int left, int right)
{
  //将中位数与数组的第一个元素(基准值)进行交换
  int midi = GetMidIndex(a, left, right);
  Swap(&a[left], &a[midi]);
  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[left], &a[keyi]);
  return left;
}