【算法】排序——选择排序和交换排序（快速排序）-阿里云开发者社区

【算法】排序——选择排序和交换排序（快速排序）

2023-11-23 56

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 上篇文章讲述了插入排序及插入排序的优化希尔排序，今天我们继续给大家带来排序中的选择排序和交换排序，选择排序包括直接选择排序、其中还包括堆排序，因为之前讲过堆排序，这篇文章就不多讲解，点击直达堆排序。交换排序包括冒泡排序、快速排序。让我们开始今天的选择排序之旅吧！！！

选择排序

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

直接选择排序

在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素

若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换

在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

实现代码

//交换函数
void swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
//直接选择排序
void SelectSort(int* a, int n)
{
  for (int i = 0; i < n; i++)
  {
    int mini = i;
    for (int j = i + 1; j < n; j++)
    {
      if (a[mini] > a[j])
      {
        mini = j;
      }
    }
    swap(&a[i], &a[mini]);
  }
}

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

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

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

4. 稳定性：不稳定

交换排序

基本思想：

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

交换排序的特点是：

将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

冒泡排序

实现代码

void BubbleSort(int* a, int n)
{
  for (int j = 0; j < n; j++)
  {
    for (int i = 0; i < n - 1-j; i++)
    {
      if (a[i + 1] < a[i])
      {
        Swap(&a[i + 1], &a[i]);
      }
    }
  }
}

如果我们给一个有序数组的话，冒泡排序还是会两两相比较，会很麻烦我们不妨给一个变量，如果发生交换的话就改变这个变量的值每一趟冒泡排序后我们判断这个值是否改变，如果没改变则这个数组是有序的。

冒泡排序优化

void BubbleSort(int* a, int n)
{
  for (int j = 0; j < n; j++)
  {
    int tmp = 1;
    for (int i = 0; i < n - 1-j; i++)
    {
      if (a[i + 1] < a[i])
      {
        Swap(&a[i + 1], &a[i]);
                tmp=0;
      }
    }
    if (tmp == 1)
    {
      return;
    }
  }
}

快速排序

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

这里我们能发现每一趟排序后的基准值都会被排序到正确的位置，因此我们以排好序的基准值为分界线，将数组分成左右两部分，左右两部分再根据排序的方法进行排序。每次排序都会产生一个排好序的基准值，每次都要根据这个基准值将数组分成两部分。因此我们考虑使用递归。

hoare法

实现代码

//hoare法
int PartSort1(int* a, int left, int right)
{
  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]);
  return left;
}
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  int keyi = PartSort1(a, begin, end);
  //[0 , keyi-1] keyi [keyi+1 , end]
  QuickSort(a, keyi + 1, end);
  QuickSort(a, begin, keyi - 1);
}

挖坑法

实现代码

//挖坑法
int PartSort2(int* a, int left, int right)
{
  int key = a[left];
  int keyi = left;
  while (left < right)
  {
    while (left < right && a[right] >= a[keyi])
    {
      right--;
    }
    a[keyi] = a[right];
    keyi = right;
    while (left < right && a[left] <= a[keyi])
    {
      left++;
    }
    a[keyi] = a[left];
    keyi = left;
  }
  a[keyi] = key;
  return keyi;
}
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  int keyi = PartSort2(a, begin, end);
  //[0 , keyi-1] keyi [keyi+1 , end]
  QuickSort(a, keyi + 1, end);
  QuickSort(a, begin, keyi - 1);
}

双指针法

实现代码

//双指针法
int PartSort3(int* a, int left, int right)
{
  int prev = left;
  int cur = left + 1;
  int keyi = left;
  while (cur <= right)
  {
    if (a[cur] < a[keyi])
    {
      Swap(&a[++prev], &a[cur]);
    }
    cur++;
  }
  Swap(&a[prev], &a[keyi]);
  return  prev;
}
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  int keyi = PartSort3(a, begin, end);
  //[0 , keyi-1] keyi [keyi+1 , end]
  QuickSort(a, keyi + 1, end);
  QuickSort(a, begin, keyi - 1);
}

上面的三中方法我们使用函数递归来完成的，如果给予一个很大的数组需要排序，递归的深度可能会很深，会导致栈溢出。

快速排序优化

我们能否发现快速排序的递归很像二叉树的遍历，但是还有一个问题我们每次选的基准值排好序后都不一定都处于数组中大致的中间位置，这是我们理想的情况，如果不理想呢，每次选好的基准值排好序后都位于开头，这样只能将一个数组元素分割出去，而不是将近分开一半一半。

最好情况：每次都将近分开一半。

时间复杂度：O(N*logN)

最坏的情况：每次都分开一小部分

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

优化一、三数取中

我们在传参数时会传数组的长度，我们不妨在在数组头，数组尾和数组中间这三个值之间挑出中间值放在数组的头部，作为基准值，在进行排序。

实现代码

int GetMidi(int* a, int left, int right)
{
  int mid= (left + right) / 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 //left>mid
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[left] < a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}

这样我们实现了三数取中，再将下面的代码放到三种方法排序之前就可以了

int mid = GetMidi(a, left, right);
  Swap(&a[left], &a[mid]);

这样我们初步的优化就完成了。

优化二、小区间优化

我们一上面的10个元素的数组为例，递归深度只有三四层没必要使用递归向下深入，继续浪费栈空间，我们不妨当数组元素大于等于10的时候递归，当数组元素小于10时使用插入排序。

实现代码

void QuickSort(int* a, int begin,int end)
{
  if (begin >= end)
    return;
  //小区间优化，小区间不在递归分割排序，减少递归次数
  if((end-begin+1)>10)
  { 
    int keyi = PartSort3(a, begin, end);
    //[begin,keyi-1] keyi [keyi+1 ,end]zd
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
  }
  else
  {
    InsertSort(a + begin, end - begin + 1);
  }
}

快速排序非递归

这里我们使用栈数据结构配合数组下标来完成非递归的实现。

实现代码

void QuickSortNonR(int* a, int left, int right)
{
  ST st;
  STInit(&st);
  STPush(&st, right);
  STPush(&st, left);
  while (!STEmpty(&st))
  {
    int begin = STTop(&st);
    STPop(&st);
    int end = STTop(&st);
    STPop(&st);
    int keyi = PartSort1(a, begin, end);
    if (keyi+1<end)
    {
      STPush(&st, right);
      STPush(&st, keyi + 1);
    }
    if (keyi - 1 > begin)
    {
      STPush(&st, keyi - 1);
      STPush(&st, left);
    }
  }
  STDer(&st);
}