手撕排序算法3:优化版冒泡排序和快速排序的三种方法(包括三数取中,小区间优化,递归版本)(下)

简介: 手撕排序算法3:优化版冒泡排序和快速排序的三种方法(包括三数取中,小区间优化,递归版本)(下)

4.快排的改进(三数取中版本和小区间优化)

1.快排的时间复杂度

> 理想状态下
> 假设我们所取的key每一次都能将它所在区间二分,也就构成了一颗完全二叉树
> 这时一共有N个结点,一共有大概log(2)(N)层
> (假设为满二叉树,但其实完全二叉树在节点个数多的情况下那几个空缺的结点可以忽略不计)
> 也就是说理想状态下我们要进行log(2)N次单趟排序,而每一次单趟排序的时间复杂度都是O(N)
> 所以时间复杂度为O(N*log(2)N)

我们呢来测一下性能

// 测试排序的性能对比
void TestOP()
{
  srand(time(0));
  const int N = 100000;
  int* a1 = (int*)malloc(sizeof(int) * N);
  int* a2 = (int*)malloc(sizeof(int) * N);
  int* a3 = (int*)malloc(sizeof(int) * N);
  int* a4 = (int*)malloc(sizeof(int) * N);
  int* a5 = (int*)malloc(sizeof(int) * N);
  int* a6 = (int*)malloc(sizeof(int) * N);
  for (int i = 0; i < N; ++i)
  {
    a1[i] = rand();
    a2[i] = a1[i];
    a3[i] = a1[i];
    a4[i] = a1[i];
    a5[i] = a1[i];
    a6[i] = a1[i];
  }
  int begin1 = clock();//clock()获取到系统运行到这里的毫秒数
  InsertSort(a1, N);
  int end1 = clock();
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
  int begin3 = clock();
  SelectSort(a3, N);
  int end3 = clock();
  int begin4 = clock();
  HeapSort(a4, N);
  int end4 = clock();
  int begin5 = clock();
  QuickSort(a5, 0, N - 1);
  int end5 = clock();
  int begin6 = clock();
  MergeSort(a6, N);
  int end6 = clock();
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  printf("SelectSort:%d\n", end3 - begin3);
  printf("HeapSort:%d\n", end4 - begin4);
  printf("QuickSort:%d\n", end5 - begin5);
  printf("MergeSort:%d\n", end6 - begin6);
  free(a1);
  free(a2);
  free(a3);
  free(a4);
  free(a5);
  free(a6);
}

我们可以看到快排排序100000个随机数仅仅用了6ms,已经很快了,我们还可以看出插入排序就是比直接选择排序要强

但是,上面的是理想状态下的时间复杂度

那么不理想的情况呢?

快排什么情况下最坏呢?最坏的时候的时间复杂度是多少呢?

注意:不只是逆序的情况下最坏

而是有序的情况下最坏:

因为这时

每一趟排序只能排一个数

这就意味着快排的执行情况是这样的

(N+(N-1)+(N-2)+(N-3)+…+1)*N -> O(N^2)

所以快排有致命的缺陷

下面我们来测试一下快排排序有序数组的情况

// 测试排序的性能对比
void TestOP()
{
  srand(time(0));
  const int N = 100000;
  int* a1 = (int*)malloc(sizeof(int) * N);
  int* a2 = (int*)malloc(sizeof(int) * N);
  int* a3 = (int*)malloc(sizeof(int) * N);
  int* a4 = (int*)malloc(sizeof(int) * N);
  int* a5 = (int*)malloc(sizeof(int) * N);
  int* a6 = (int*)malloc(sizeof(int) * N);
  for (int i = 0; i < N; ++i)
  {
    a1[i] = rand();
    a2[i] = a1[i];
    a3[i] = a1[i];
    a4[i] = a1[i];
    a5[i] = a1[i];
    a6[i] = a1[i];
  }
  int begin1 = clock();//clock()获取到系统运行到这里的毫秒数
  InsertSort(a1, N);
  int end1 = clock();
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
  int begin3 = clock();
  SelectSort(a3, N);
  int end3 = clock();
  int begin4 = clock();
  HeapSort(a4, N);
  int end4 = clock();
  int begin5 = clock();
  QuickSort(a4, 0, N - 1);//将a5改为a4即可,因为a5是无序数组,a4已经被排好序了,是有序数组
  int end5 = clock();
  int begin6 = clock();
  MergeSort(a6, N);
  int end6 = clock();
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  printf("SelectSort:%d\n", end3 - begin3);
  printf("HeapSort:%d\n", end4 - begin4);
  printf("QuickSort:%d\n", end5 - begin5);
  printf("MergeSort:%d\n", end6 - begin6);
  free(a1);
  free(a2);
  free(a3);
  free(a4);
  free(a5);
  free(a6);
}

我们可以看出快排这时候花了2563ms,比起堆排序和希尔排序来说太慢了

但是有人想到了一种优化的方法,这个方法极大地挽救了快排,让快排即使在有序的情况下也并不比无序的情况差多少

这个方法叫做:三数取中法

下面我们来介绍这个方法

2.三数取中方法

三数取中指的是:

从第一个数,最后一个数,中间那个数这三个数里面找出值为中间的那个数,让那个数去做key

可以有效避免有序状态下快排的致命缺陷,也可以避免无序状态下因为取key的随机性所导致的不可控的时间效率问题.

上代码,先让大家看一下

//三数取中:
int GetMidIndex(int* a, int left, int right)
{
  //下面两行的意思一样
  //int mid = (left + right) / 2;
  int mid = (left + right) >> 1;
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])//mid是最大的,那么left和right中更大的那个就是中间值
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  else//a[left] >= a[mid]
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[left] < a[right])//mid是最小的,那么left和right中更小的那个就是中间值
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}
void QuickSort(int* a, int left, int right)
{
  if (left >= right)
  {
    return;
  }
  int index = GetMidIndex(a, left, right);
  Swap(&a[left], &a[index]);//为了保证下面的代码不会发生改变,所以交换了a[index]和a[left]这两个数,
  int begin = left;
  int end = right;
  int pivot = begin;
  int key = a[begin];
  while (begin < end)
  {
    while (end > begin && a[end] >= key)
    {
      --end;
    }
    a[pivot] = a[end];
    pivot = end;
    while (begin < end && a[begin] <= key)
    {
      ++begin;
    }
    a[pivot] = a[begin];
    pivot = begin;
  }
  pivot = begin;
  a[pivot] = key;
  QuickSort(a, left, pivot - 1);
  QuickSort(a, pivot + 1, right);
}

然后,我们现在已经完成了三数取中的优化,接下来我们让我们测一下优化后的快排对于有序数组的效率.

在这里我们可以看出三数取中优化后的快排从2600多ms降为了1ms,可见三数取中拯救了快排

但是快排虽好,它也是使用递归来进行操作的,既然是递归,就免不了会有开辟函数栈帧的消耗,也有可能会出现栈溢出的情况,所以有人发明了小区间优化的方法,也有人发明了快排的非递归版本.

下面我们来剖析一下小区间优化

3.小区间优化版本

每调用一次函数,就会调用两次函数:左区间和右区间,所以函数调用次数是呈等比数列的形式增长的,所以说当基数越大(即调用层数越深时)时,函数调用的增长量越大,也就是说整个函数递归调用的次数很大一部分取决于最后几次调用

例如:最后一次调用就会使总的递归调用层数翻倍

所以有人就想能不能想个办法把最后几次的递归调用给消除掉呢?

于是就发明了小区间优化

小区间优化的整体思想:

下面上代码:

void QuickSort(int* a, int left, int right)
{
  if (left >= right)
  {
    return;
  }
  int index = GetMidIndex(a, left, right);
  Swap(&a[left], &a[index]);//为了保证下面的代码不会发生改变,所以交换了a[index]和a[left]这两个数,
  int begin = left;
  int end = right;
  int pivot = begin;
  int key = a[begin];
  while (begin < end)
  {
    while (end > begin && a[end] >= key)
    {
      --end;
    }
    a[pivot] = a[end];
    pivot = end;
    while (begin < end && a[begin] <= key)
    {
      ++begin;
    }
    a[pivot] = a[begin];
    pivot = begin;
  }
  pivot = begin;
  a[pivot] = key;
  //[left,pivot-1]  pivot  [pivot+1,right]
  if(pivot-1-left>10)
  {
    QuickSort(a, left, pivot - 1);
  }
  else
  {
  //对于闭区间[a,b]而言,这个区间内的元素个数为b-a+1,即右下标-左下标+1
    InsertSort(a+left,pivot-1-left+1);//pivot-1-left-left+1 就是待排序数组的长度
    //a+left:就是待排序数组的起始下标
  }
    if(right-(pivot+1)>10)
  {
    QuickSort(a, pivot + 1, right);
}
  }
  else
  {
    InsertSort(a+pivot+1,right-(pivot+1)+1);
  }
}
1.其实小区间优化的效果并不明显,差不多100w次调用能减少10几ms的时间
2.C++的官方库里这个小区间也没有给很高,建议给10就行
因为小区间优化的目的
就是消除掉函数调用最后几层时所递归调用的巨大的次数
给个10,大概小区间优化的目的就完成了.
3.这里为什么要用插入排序呢?
因为我们只需要排序10个数字,所以直接用直接插入排序即可,
再去用快排会形成巨多栈帧不值得,用堆和希尔去做这么小的数据量的排序也很大材小用
因为上面的三个排序都是数据量越多相比于直接插入排序而言越有优势,而现在数据量很小,优势显不出来
而且本来进行了很多次快速排序的单趟排序后这个小区间内的数据有很多都已经是部分或整体有序的了
而直接插入排序对部分有序或整体有序的数组的排序有奇效(甚至时间复杂度有可能能达到O(N)),所以我们用直接插入排序即可

5.左右指针法

1.算法剖析

下面给大家介绍一下左右指针法,即挖坑法的一种变形

就是实现单趟排序的另一种方法

注意:

这两种方法得到的序列并不一定相同

下面给大家画个图

2.代码实现

void PartSort(int* a, int left, int right)
{
  int index = GetMidIndex(a, left, right);
  Swap(&a[left], &a[index]);
  int begin = left;
  int end = right;
  int keyi = begin;
  while (begin < end)
  {
    while (a[end] >= a[keyi] && begin < end)//  begin < end:
    //防止有序且没有三数取中的优化的情况下出现数组越界访问的情况
    //不加=的话可能会死循环
    //死循环:例如
      // 5    .......... 5  
      // begin          end
      //因为a[begin]==a[end]  都等于5
      //所以如果没有加=的话begin和end就不会动了,也就是会导致死循环
      //挖坑法也是
    {
      end--;
    }
    while(a[begin] <= a[keyi] && begin < end)
    {
      begin++;
    }
    //注意:在这里我们必须先从右边开始找小,再从左边开始找大
    //因为我们这个方法是挖坑法的一种变形,
    //而初始状态我们选定最左边的元素为key值,即为"坑位",所以根据左边有坑,右边找小的口诀,
    //我们要从右侧开始找起
    Swap(&a[begin], &a[end]);
  }
  Swap(&a[begin], &a[keyi]);
}

6.前后指针法

1.算法剖析

下面给大家介绍一下前后指针法,即挖坑法的一种变形

就是实现单趟排序的另一种方法

下面大家看一下这张图片

2.代码实现

下面我们来实现一下这个代码

void PartSort3(int* a, int left, int right)
{
  int keyi = left;
  int prev = left;
  int cur = left + 1;
  while (cur <= right)
  {
    if (a[cur] < a[keyi])
    {
      ++prev;
      Swap(&a[prev], &a[cur]);
    }
  //这是优化版本,使得当两数相同时无需进行交换,即防止自己和自己交换
  //  if (a[cur] < a[keyi] && ++prev!=cur)
  //  {
  //    Swap(&a[prev], &a[cur]);
  //  }
    ++cur;
  }
  Swap(&a[prev], &a[keyi]);
}

以上就是快速排序和冒泡排序的讲解,

希望能对大家有所帮助

关于快速排序的非递归版本我后续会给大家去单独写一篇博客去讲解

相关文章
|
2天前
|
算法
基于大爆炸优化算法的PID控制器参数寻优matlab仿真
本研究基于大爆炸优化算法对PID控制器参数进行寻优,并通过Matlab仿真对比优化前后PID控制效果。使用MATLAB2022a实现核心程序,展示了算法迭代过程及最优PID参数的求解。大爆炸优化算法通过模拟宇宙大爆炸和大收缩过程,在搜索空间中迭代寻找全局最优解,特别适用于PID参数优化,提升控制系统性能。
|
9天前
|
存储 关系型数据库 分布式数据库
PolarDB的PolarStore存储引擎以其高效的索引结构、优化的数据压缩算法、出色的事务处理能力著称
PolarDB的PolarStore存储引擎以其高效的索引结构、优化的数据压缩算法、出色的事务处理能力著称。本文深入解析PolarStore的内部机制及优化策略,包括合理调整索引、优化数据分布、控制事务规模等,旨在最大化其性能优势,提升数据存储与访问效率。
21 5
|
23天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
21天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
38 2
|
24天前
|
人工智能 算法 大数据
Linux内核中的调度算法演变:从O(1)到CFS的优化之旅###
本文深入探讨了Linux操作系统内核中进程调度算法的发展历程,聚焦于O(1)调度器向完全公平调度器(CFS)的转变。不同于传统摘要对研究背景、方法、结果和结论的概述,本文创新性地采用“技术演进时间线”的形式,简明扼要地勾勒出这一转变背后的关键技术里程碑,旨在为读者提供一个清晰的历史脉络,引领其深入了解Linux调度机制的革新之路。 ###
|
2月前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。
|
1月前
|
存储 缓存 算法
优化轮询算法以提高资源分配的效率
【10月更文挑战第13天】通过以上这些优化措施,可以在一定程度上提高轮询算法的资源分配效率,使其更好地适应不同的应用场景和需求。但需要注意的是,优化策略的选择和实施需要根据具体情况进行详细的分析和评估,以确保优化效果的最大化。
|
2月前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
|
14天前
|
算法 数据安全/隐私保护 索引
OFDM系统PAPR算法的MATLAB仿真,对比SLM,PTS以及CAF,对比不同傅里叶变换长度
本项目展示了在MATLAB 2022a环境下,通过选择映射(SLM)与相位截断星座图(PTS)技术有效降低OFDM系统中PAPR的算法实现。包括无水印的算法运行效果预览、核心程序及详尽的中文注释,附带操作步骤视频,适合研究与教学使用。