【数据结构】排序（插入、选择、交换、归并） -- 详解（下）-阿里云开发者社区

【数据结构】排序（插入、选择、交换、归并） -- 详解（上）https://developer.aliyun.com/article/1514538?spm=a2c6h.13148508.setting.25.4b904f0ejdbHoA

（4）快速排序优化 · 三数取中法

三数取中法依然无法完全解决针对某种特殊序列（比如元素全部相同）复杂度变为 O(n) 的情况。

三数取中法一般选取首、尾和正中三个数进行取中。

该方法的基本思想是从待排序数组中随机选择三个元素，并将它们按升序排列。然后，选择中间位置的元素作为 mid 。

这样处理的方式有几个优点，可以提高排序算法的效率：

减少最坏情况：选择中间位置的元素，可以避免最坏情况的发生。最坏情况是在每次划分过程中总是选择了最大或最小的元素，导致划分不平衡，使得排序算法的时间复杂度变为 O(n²) 。而三数取中法可以减少最坏情况的发生，提高划分的平衡性。

提高划分效率：选择适当的中间元素可以增加划分的平衡性，使得每次划分都能将数组分为近似相等大小的两个部分。这样，在后续的排序过程中，可以减少比较和交换的次数，提高排序算法的效率。

三数取中法可以有效地应对一些特殊情况，如数组已经有序或部分有序的情况。在这些情况下，选择中间位置的元素可以避免不必要的划分和比较操作。

总的来说，三数取中法通过选择合适的中间元素，可以减少最坏情况的发生，提高划分的平衡性和效率，从而提高排序算法的整体效率。

// 三数取中法
int GetMidIndex(int* a, int begin, int end)
{
  //int mid = (begin + end) / 2;
    int mid = left + (right - left) / 2; // 防止溢出版本
 
  if (a[begin] < a[mid])
  {
    if (a[mid] < a[end])
    {
      return mid;
    }
    else if (a[begin] < a[end])
    {
      return end;
    }
    else
    {
      return begin;
    }
  }
  else // (a[begin] >= a[mid])
  {
    if (a[mid] > a[end])
    {
      return mid;
    }
    else if (a[begin] < a[end])
    {
      return begin;
    }
    else
    {
      return end;
    }
  }
}

三数取中法选 key。

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

优化后的代码：

void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
 
// Hoare
int PartSort1(int* a, int begin, int end)
{
  int left = begin, right = end;
  int keyi = left;
 
    // 加入三数取中的优化
  int midi = GetMidIndex(a, begin, end);
  Swap(&a[keyi], &a[midi]);
 
  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;
 
  return keyi;
}

// 挖坑法
int PartSort2(int* a, int begin, int end)
{
  int key = a[begin];
  int piti = begin;
 
    // 加入三数取中的优化
  int midi = GetMidIndex(a, begin, end);
  Swap(&a[keyi], &a[midi]);
 
  while (begin < end)
  {
    // 右边找小，填到左边的坑里面去。这个位置形成新的坑
    while (begin < end && a[end] >= key)
    {
      --end;
    }
    a[piti] = a[end]; // 填坑
    piti = end; // 新坑
 
    // 左边找大，填到右边的坑里面去。这个位置形成新的坑
    while (begin < end && a[begin] <= key)
    {
      ++begin;
    }
    a[piti] = a[begin]; // 填坑
    piti = begin; // 新坑
  }
  a[piti] = key; // 将key填到最后一个坑里
  return piti;
}

void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
 
// 前后指针法
int PartSort3(int* a, int begin, int end)
{
  int prev = begin;
  int cur = begin + 1;
  int keyi = begin;
 
  // 加入三数取中的优化
  //int midi = GetMidIndex(a, begin, end);
  //Swap(&a[keyi], &a[midi]);
 
  while (cur <= end)
  {
    // cur位置的值小于keyi位置的值
    if (a[cur] < a[keyi] && ++prev != cur)
    {
      Swap(&a[prev], &a[cur]);
    }
    ++cur;
  }
  Swap(&a[prev], &a[keyi]);
  keyi = prev;
 
  return keyi;
}

快速排序是一种高效的排序算法，通常在处理大规模数据时表现良好。然而，当递归到较小区间时，快速排序可能会变得相对较慢。这是因为递归调用本身会带来一定的开销，而对于较小的区间，插入排序可能更加高效。

插入排序是一种简单但有效的排序算法，对于小规模的数据集表现出色。它的时间复杂度为O(n²)，但在实际应用中，由于具有低的常数因子和良好的局部性，插入排序通常会比其他 O(n²) 复杂度的排序算法更快。

因此，当快速排序递归到较小区间时，我们可以切换到插入排序。这样可以减少递归调用的次数，降低开销，并且利用插入排序的优势来提高整体性能。

void InsertSort(int* a, int n)
{
  for (int i = 0; i < n - 1; ++i)
  {
    // [0,end]有序，把end+1位置的值插入，保持有序
    int end = i;
    int tmp = a[end + 1];
    while (end >= 0)
    {
      if (tmp < a[end]) // 升序
      {
        a[end + 1] = a[end];
        --end;
      }
      else
      {
        break;
      }
    }
    a[end + 1] = tmp;
  }
}
 
// 快速排序（递归）
void QuickSort(int* a, int begin, int end)
{
 
  // 区间不存在，或者只有一个值则不需要再处理
  if (begin >= end)
  {
    return;
  }
 
  if (end - begin > 10)
  {
    int keyi = PartSort3(a, begin, end);
 
    // [begin, keyi-1] keyi [keyi+1, end]
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
  }
  else // 递归到小的子区间时，可以考虑使用插入排序
  {
    InsertSort(a + begin, end - begin + 1);
  }
}

（5）快速排序非递归

递归的大问题是在极端场景下，如果栈帧深度太深，栈空间不够用，会出现栈溢出。下面用非递归实现快速排序：

递归改成非递归一般有两种方法：

直接改循环（简单）；

借助数据结构栈模拟递归过程（复杂）。

快速排序的非递归遍历可以使用栈模拟二叉树的前序遍历的方式实现，也可以使用队列模拟二叉树的层序遍历的方式实现。

快排的非递归是在模拟递归的过程，所以时间复杂度并没有本质的变化，但是没有递归，可以减少栈空间的开销。

// 快速排序非递归（栈）
void QuickSortNonR(int* a, int begin, int end)
{
  ST st;
  StackInit(&st);
  StackPush(&st, end);
  StackPush(&st, begin);
 
  while (!StackEmpty(&st)) // 栈不为空
  {
        // 取栈顶left，并Pop
    int left = StackTop(&st);
    StackPop(&st);
 
        // 再取栈顶right，并Pop
    int right = StackTop(&st);
    StackPop(&st);
 
    int keyi = PartSort3(a, left, right); // 这里用前后指针单趟排
    // [left, keyi-1] keyi [keyi+1, right]
 
    if (keyi + 1 < right) // 至少还有一个以上的值
    {
      StackPush(&st, right);
      StackPush(&st, keyi + 1);
    }
 
    if (left < keyi - 1) // 至少还有一个以上的值
    {
      StackPush(&st, keyi - 1); // 先入右，再入左 -- 先出左，再出右
      StackPush(&st, left);
    }
  }
  StackDestroy(&st);
}

需要入栈的是数组的下标区间，且先入右再入左，因为栈是先进后出，条件是栈不为空。

依次把需要进行单趟排的区间入栈，依次取栈里的区间出来单趟排，再把需要处理的子区间入栈。

快速排序的特性总结：（ 前序遍历 ）（ 层序遍历 ）

快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序。

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

空间复杂度：O(logN)。

稳定性：不稳定。

4、归并排序

（1）基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用 分治法（Divide and Conquer）的一个非常典型的应用。分治，顾名思义，就是分而治之， 将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
分治思想跟我们前面讲的递归思想很像。是的，分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧 ，这两者并不冲突。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

（2）归并排序（MergeSort）

归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两

部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有

序了。

void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if (begin >= end)
  {
    return;
  }
 
  //int mid = (begin + end) / 2;
    int mid = begin + (end - begin) / 2; // 防止溢出版本
 
  // [begin, mid] [mid+1, end] 分治递归，让子区间有序
  _MergeSort(a, begin, mid, tmp);
  _MergeSort(a, mid + 1, end, tmp);
 
  // 归并[begin, mid] [mid+1, end]
  int begin1 = begin, end1 = mid;
  int begin2 = mid + 1, end2 = end;
  int i = begin1;
  while (begin1 <= end1 && begin2 <= end2) // 其中一个结束就结束
  {
    if (a[begin1] <= a[begin2]) // 等于可以保证稳定性
    {
      tmp[i++] = a[begin1++];
    }
    else
    {
      tmp[i++] = a[begin2++];
    }
  }
 
    // 将剩余的数字直接填入tmp数组里
  while (begin1 <= end1) // begin2结束了，拷贝剩下的begin1
  {
    tmp[i++] = a[begin1++];
  }
 
  while (begin2 <= end2) //begin1结束了，拷贝剩下的begin2
  {
    tmp[i++] = a[begin2++];
  }
 
    // 归并后的结果，拷贝到原数组
  memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
 
    //for(int i = begin; i <= end; ++i)
    //{
    //    a[i] = tmp[i];
    //}
}
 
// 归并排序
void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n); // 临时数组
  if (tmp == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  _MergeSort(a, 0, n - 1, tmp); // 子函数递归
 
  free(tmp);
}

a.归并排序是稳定的排序算法吗？

在合并的过程中，如果 a[p…q] 和 a[q+1…r] 之间有值相同的元素，先把 a[p…q] 中的元素放入 tmp 数组，这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。

b.归并排序的时间复杂度是多少？

归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(n*logn) 。

c.归并排序的空间复杂度是多少？

归并排序不是原地排序算法。这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。

如果我们继续按照分析递归时间复杂度的方法，通过递推公式来求解，那整个归并过程需要的空间复杂度就是 O(n*logn)。不过，类似分析时间复杂度那样来分析空间复杂度，这个思路并不对。实际上，递归代码的空间复杂度并不能像时间复杂度那样累加。刚刚我们忘记了最重要的一点，那就是，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻， CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n) 。

归并排序的特性总结：（ 后序遍历 ）

归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

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

空间复杂度：O(N)。

稳定性：稳定。

（3）归并排序非递归

非递归未必比递归简单，因为这里需要对边界进行精准控制。

// 归并排序（非递归）
void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
 
  int gap = 1;
  while (gap < n)
  {
    for (int i = 0; i < n; i += 2 * gap)
    {
      // [i, i+gap-1][i+gap, i+2*gap-1]
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + 2 * gap - 1;
 
      // end1越界或者begin2越界，则可以不归并
      if (end1 >= n || begin2 >= n)
      {
        break;
      }
      else if (end2 >= n) // 修正边界
      {
        end2 = n - 1;
      }
 
      int m = end2 - begin1 + 1; //实际归并的总体个数
      int j = begin1;
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
 
      while (begin1 <= end1) // begin2结束了，拷贝剩下的begin1
      {
        tmp[j++] = a[begin1++];
      }
 
      while (begin2 <= end2) // begin1结束了，拷贝剩下的begin2
      {
        tmp[j++] = a[begin2++];
      }
      memcpy(a + i, tmp + i, sizeof(int) * m); // 拷贝回原数组
    }
    gap *= 2; // 迭代
  }
  free(tmp);
}

⚪非比较排序

（1）思想

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

（2）计数排序（CountSort）

操作步骤：

统计相同元素出现次数。

根据统计的结果将序列回收到原来的序列中。

// 计数排序
void CountSort(int* a, int n)
{
  int min = a[0], max = a[0];
    // 找出最大最小值
  for (int i = 1; i < n; ++i)
  {
    if (a[i] < min)
    {
      min = a[i];
    }
    
    if (a[i] > max)
    {
      max = a[i];
    }
  }
 
  // 统计次数的数组
  int range = max - min + 1;
  int* count = (int*)malloc(sizeof(int) * range);
  if (count == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  memset(count, 0, sizeof(int) * range); // 初始化为0
 
  //统计次数
  for (int i = 0; i < n; ++i)
  {
    count[a[i] - min]++;
  }
 
  //回写-排序
  int j = 0;
  for (int i = 0; i < range; ++i)
  {
    // 出现几次就要回写几个i+min
    while (count[i]--)
    {
      a[j++] = i + min;
    }
  }
    free(count);
}

如果要开 0~5000 个数据的数组，但其实小于 1000 的数据一个都没有，空间浪费严重，这种方式叫作绝对映射。

针对此情况，如果我们只需要 0~4000 个数据的数组即可，放数据时是 a[i] - min，这种方式叫作相对映射。

注意：计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

计数排序的特性总结：

计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。

时间复杂度：O(MAX(N，range))。

空间复杂度：O(range)。

稳定性：稳定。

【数据结构】排序（插入、选择、交换、归并） -- 详解（下）

（4）快速排序优化 · 三数取中法

（5）快速排序非递归

4、归并排序

（1）基本思想

（2）归并排序（MergeSort）

a.归并排序是稳定的排序算法吗？

b.归并排序的时间复杂度是多少？

c.归并排序的空间复杂度是多少？

（3）归并排序非递归

⚪非比较排序

（1）思想

（2）计数排序（CountSort）

三、排序算法复杂度及稳定性分析

热门文章

最新文章

相关课程

相关电子书