排序——交换排序-阿里云开发者社区

交换排序

基本思想

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

冒泡排序

冒泡排序是我们最早接触的算法了，对于冒泡排序我们应该是最熟悉的了

代码实现

void BubbleSort(int* a, int n)
{
  for (int i = 0; i < n; i++)
  {
    int flag = 0;
    for (int j = 0; j < n - 1 - i; j++)
    {
      if (a[j] > a[j + 1])
      {
        Swap(&a[j], &a[j + 1]);
        flag = 1;
      }
    }
    if (flag == 0)
    {
      break;
    }
  }
}
void TestBubbleSort()
{
  int a[] = { 105,5,8,2,50,7,-1,100,66 };
  int n = sizeof(a) / sizeof(a[0]);
  BubbleSort(a, n);
  Print(a, n);
}
int main()
{
  TestBubbleSort();
}

快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

简单来说，就是左边比基准值小，右边比基准值大（基准值我们一般选取最左边的值、中间的值、最右边的值，或者随机值）选取最左边的值的话，让右边先走，选取最右边的值的话，让左边先走

很明显，我们可以利用递归来实现快排。快速排序这部分我们会说的比较多。

hoare版本

下面，进行代码实现：

//单趟排序
int PartSort(int* a, int left, int right)
{
  int keyi = left;
  while (left < right)
  {
    //R找小(记得给等于号，不然会造成死循环)
    while (left<right && a[right] >= a[keyi])
    {
      --right;
    }
    //L找大
    if (left<right && a[left] <= a[keyi])
    {
      ++left;
    }
    if(left<right)
       Swap(&a[left], &a[right]);
  }
  int meeti = left;
  Swap(&a[left], &a[keyi]);
  return meeti;
}
void QuickSort(int* a, int begin,int end)
{
  int keyi = PartSort(a, begin, end);
  if (begin >= end)
    return;
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi + 1, end);
}
void TestQuickSort()
{
  int a[] = { 105,5,8,2,50,7,-1,100,66 };
  int n = sizeof(a) / sizeof(a[0]);
  QuickSort(a, 0,n-1);
  Print(a, n);
}
int main()
{
  TestQuickSort();
}

但是，对于hoare版本，我们还可以对其进行优化：

在比较理想的情况下，我们选择key单趟排完基本都是在中间，这样子才是二分logN O(N*logN)

如果在有序/接近有序的情况下，那么key每次单趟排完的效果是比较差的O（N^2）,所以下面进入快排的另一个主题，优化问题👇

快速排序优化

优化选key问题：

随机选一个数作为key(太随意了)
针对有序，选正中间值做key(具有针对性)
三数取中（第一个中间位置最后一个选出中间值），三数取中法选key（具有普遍性）

2.递归到小的子区间时，可以考虑使用插入排序

下面，我们用代码来实现三数取中的算法：

//三数取中
int GetMidIndex(int* a, int left, int right)
{
  int mid = left + (right - left) / 2;
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  else
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[right] > a[left])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}

下面，我们就可以优化我们的快排代码了：

//三数取中
int GetMidIndex(int* a, int left, int right)
{
  int mid = left + (right - left) / 2;
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  else
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[right] > a[left])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}
//单趟排序
int PartSort(int* a, int left, int right)
{
    //三数取中
  int mid = GetMidIndex(a, left, right);
  Swap(&a[left], &a[mid]);
  int keyi = left;
  while (left < right)
  {
    //R找小(记得给等于号，不然会造成死循环)
    while (left < right && a[right] >= a[keyi])
    {
      --right;
    }
    //L找大
    if (left < right && a[left] <= a[keyi])
    {
      ++left;
    }
    if (left < right)
      Swap(&a[left], &a[right]);
  }
  int meeti = left;
  Swap(&a[left], &a[keyi]);
  return meeti;
}
void QuickSort(int* a, int begin, int end)
{
  int keyi = PartSort(a, begin, end);
  if (begin >= end)
    return;
  //小区间优化
  if (end - begin <= 8)
  {
    InsertSort(a+begin,end-begin+1);
  }
  else
  {
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
  }
}

挖坑法
简单来说，就是对单趟排序进行改造，三数取中后我们还是以左边作为key,然后把左边作为坑，然后右边找小，在把找到的值放在坑位上去，在把坑位置为右边找到的位置。再从左边找大，把找到的值放在坑位上，在更新一下坑位。重复以上过程。整体思路与hoare方法类似。

int PartSort2(int* a, int left, int right)
{
  int mid = GetMidIndex(a, left, right);
  Swap(&a[left], &a[mid]);
  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)
{
  int keyi = PartSort2(a, begin, end);
  if (begin >= end)
    return;
  //小区间优化
  if (end - begin <= 8)
  {
    InsertSort(a+begin,end-begin+1);
  }
  else
  {
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
  }
}

前后指针版本

下面，我们以动图的形式演示前后指针版本的过程：

代码实现：

//前后指针法
int PartSort3(int* a, int left, int right)
{
  int mid = GetMidIndex(a, left, right);
  Swap(&a[left], &a[mid]);
  int keyi = left;
  int prev = left;
  int cur = left + 1;
  while (cur<=right)
  {
    if (a[cur] < a[keyi]&&++prev!=cur)
    {
      Swap(&a[cur], &a[prev]);
    }
    ++cur;
  }
  Swap(&a[keyi], &a[prev]);
  return prev;
}
void QuickSort(int* a, int begin, int end)
{
  int keyi = PartSort3(a, begin, end);
  if (begin >= end)
    return;
  //小区间优化
  if (end - begin <= 8)
  {
    InsertSort(a+begin,end-begin+1);
  }
  else
  {
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
  }
}

至此，我们对于快排基本了解完了，这里还有另一点：那就是快速排序的非递归实现：

快速排序非递归

我们需要借助一个栈，对于栈，C语言我们肯定要自己去实现，栈的实现可参考我之前写过的博客，这里就直接来用了：

int PartSort3(int* a, int left, int right)
{
  int mid = GetMidIndex(a, left, right);
  Swap(&a[left], &a[mid]);
  int keyi = left;
  int prev = left;
  int cur = left + 1;
  while (cur<=right)
  {
    if (a[cur] < a[keyi]&&++prev!=cur)
    {
      Swap(&a[cur], &a[prev]);
    }
    ++cur;
  }
  Swap(&a[keyi], &a[prev]);
  return prev;
}
void QuickSortNonR(int* a, int begin, int end)
{
  ST st;
  StackInit(&st);
  StackPush(&st, begin);
  StackPush(&st, end);
  while (!StackEmpty(&st))
  {
    int right = StackTop(&st);
    StackPop(&st);
    int left = StackTop(&st);
    StackPop(&st);
    if (left >= right)
    {
      continue;
    }
    int keyi = PartSort3(a, left, right);
    //[left,keyi-1] keyi  [keyi+1,right]
    //先入右边
    StackPush(&st, keyi+1);
    StackPush(&st, right);
    //后入左边
    StackPush(&st, left);
    StackPush(&st, keyi-1);
  }
  StackDestory(&st);
}

至此，我们终于把快速排序的大部分内容说完了。

快速排序的特性总结：

快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)

空间复杂度：O(logN)
稳定性：不稳定

排序——交换排序