【探索排序算法的魅力:优化、性能与实用技巧】(中)

简介: 【探索排序算法的魅力:优化、性能与实用技巧】

【探索排序算法的魅力:优化、性能与实用技巧】(上):https://developer.aliyun.com/article/1425253


2.3 交换排序


2.3.1基本思想


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


2.3.2冒泡排序


冒泡排序是数据两两比较,将小的交换到前面,每趟排序将最大的排序到最后面,假设有n个数据,只用进行n-1趟排序,同时我们还要注意每趟排序的比较次数是不同的,第一轮,所有数据都要排序,就是n-1轮比较,第二轮比较的时候,最大的数据已经到了正确的位置,所以第二轮就只有n-2个数据比较。


void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
//冒泡排序
void BubbleSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)//比较的趟数
  {
    for (int j = 0; j < n - i - 1; j++)
    {
      if (a[j] > a[j + 1])
      {
        Swap(&a[j], &a[j + 1]);
      }
    }
  }
}


上面的代码就是我们的冒泡排序,但是如果经过第一轮交换后,数据就已经有序了,但是我们的程序还在上面一轮一轮比较,这样效率较低,我们可以设置一个标志,如果经过一轮排序没有数据交换,那就说明数据已经有序了。

void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
//冒泡排序
void BubbleSort(int* a, int n)
{
  for (int i = 0; i < n - 1 ; i++)//比较的趟数
  {
    int flag = 1;//默认数据有序
    for (int j = 0; j < n - i - 1; j++)
    {
      if (a[j] > a[j + 1])
      {
        Swap(&a[j], &a[j + 1]);
        flag = 0;//数据无序
      }
    }
    if (flag == 1)
      break;
  }
}


冒泡排序的特性总结:


  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:稳定


2.3.2快速排序


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

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
  //= 代表只剩下一个值
    if (left >= right)
    return;
  // 按照基准值对array数组的 [left, right)区间中的元素进行划分
  int div = PartSort(array, left, right);
  // 划分成功后以div为边界形成了左右两部分 [left, div-1) 和 [div+1, right)
  // 递归排[left, div-1)
  QuickSort(array, left, div-1);
  // 递归排[div+1, right)
  QuickSort(array, div + 1, right);
}


上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

单趟排序

//1. hoare版本
int PartSort(int* a, int left, int right)
{
  int key = a[left];
  while (left < right)
  {
    //右边找小
    while (a[right] > key)
    {
      right--;
    }
    //左边找大
    while (a[left] < key)
    {
      left++;
    }
    Swap(&a[left], &a[right]);
  }
  //key和相遇位置交换
  Swap(&key, &a[left]);
  return left;
}


我们看看上面的代码有问题没?我们来看看下面的图。


很明显,根据我们上面的代码,当key和a[left]、a[right]相等的时候,程序是不是就卡死啦。所以我们需要修改上面的循环条件key和a[left]、a[right]相等的时候,left和right的值都要改变。

//1. hoare版本
int PartSort(int* a, int left, int right)
{
  int key = a[left];
  while (left < right)
  {
    //右边找小
    while (a[right] >= key)
    {
      right--;
    }
    //左边找大
    while (a[left] <= key)
    {
      left++;
    }
    Swap(&a[left], &a[right]);
  }
  //key和相遇位置交换
  Swap(&key, &a[left]);
  return left;
}


我们再看看上面的代码还有问题没?我们来看看下面的图。



如果a[right]的值都大于key,那么right会一直减,最后就会越界的问题;同样a[left]的值都大于key,那么left会一直加,最后就会越界的问题。

//1. hoare版本
int PartSort(int* a, int left, int right)
{
  int key = a[left];
  while (left < right)
  {
    //右边找小
    while (left < right && a[right] >= key)
    {
      right--;
    }
    //左边找大
    while (left < right && a[left] <= key)
    {
      left++;
    }
    Swap(&a[left], &a[right]);
  }
  //key和相遇位置交换
  Swap(&key, &a[left]);
  return left;
}


我们再看看上面的代码还有问题没?我们来看看下面的图。


当最后right和left相遇的时候,此时执行Swap(&key, &a[left]),但是只是和key这个局部变量交换,并不是和数组里面的内容交换,数组里面的那个key值元素没有变化,我们可以通过下标去实现数组内容的交换。

//1. hoare版本
int PartSort(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]);
  }
  //key和相遇位置交换
  Swap(&a[keyi], &a[left]);
  return left;
}


这里有一个疑问?为什么相遇的地方的值比key值一定小呢?怎么做到的呢???右边先走才能做到相遇的地方的值比key值一定小。


相遇情况:

  1. 如果左边先走,相遇位置是R的位置,L和R在上一轮交换过,交换后R的位置一定比key大,此时和key交换没有意义。
  2. 如果R先走找到比key小的值停下来了,然后L再走,找比key大的值,没有找到和R相遇了,相遇位置比key小,交换之后满足左边值比key小,右边比key大。



上面的hoare版本有很多的坑,下面我们来换一种写法:挖坑法


//挖坑法
int PartSort1(int* a,int left,int right)
{
  int key = a[left];//保存key值,形成第一个坑位
  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;
  }
  //相遇的位置放key
  a[hole] = key;
  return hole;
}


除了上面的这种写法,我们还有一张前后指针法。cur找小,找到之后让prev加加,再交换cur和prev处的值,prev在这里有两种情况,在cur还没遇到比key大的值得时候,此时prev紧跟cur,在cur遇到比key大的值的时候,prev在比key大的一组值得前面。本质是:把一段大于key的区间往右推,同时把小的甩到左边。

//前后指针版本     
int PartSort(int* a,int left,int right)
{
  int cur = left + 1;
  int prev = left;
  int keyi = left;
  while(cur < right + 1)
  {
    if(a[cur] < a[keyi] && cur != prev)
    {
      Swap(&a[cur],&a[++prev]);
    }
    cur++;
  } 
  Swap(&a[keyi],&a[prev]);
  return prev;
}


其实我们上面的三种快速排序遇到有一种情况就会对时间的消耗巨大,在利扣上运行就会出现超出时间限制的错误,什么情况呢?如果我们要排序的数是一组数据量极大的重复数字,此时的三数取中就没有任何意义,且上面三个版本的写法都不能处理这个问题,拿上面的hoare版本来说,如果是一组重复数据,hoare每次都是从右边先开始以此往左边找比keyi小的值,但是此时数组中的值都是一样的,找不到比keyi小的值,只能keyi就只能和right交换,我们想想,如果是一组数据重复极大的值,每次都要这样,消耗的时间是非常巨大的。因此这里可以使用第四种写法,三路划分:把小于key往左推,等于key换到中间,大于key的往右推。


三路划分:


  • 1.cur小于key时,交换cur和left位置的值,然后再++cur,++left。
  • 2.cur等于key时,直接++cur。
  • 3.cur大于key时,交换cur和right位置的值,这里不能直接++cur,因为交换cur和right位置的值之后,此时不清楚cur位置与key位置值得大小关系,需要先--right,然后再比较cur位置与key位置值得大小关系。


结束条件:cur > right


【探索排序算法的魅力:优化、性能与实用技巧】(下):https://developer.aliyun.com/article/1425264

相关文章
|
12天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
12天前
|
机器学习/深度学习 算法 5G
基于MIMO系统的SDR-AltMin混合预编码算法matlab性能仿真
基于MIMO系统的SDR-AltMin混合预编码算法通过结合半定松弛和交替最小化技术,优化大规模MIMO系统的预编码矩阵,提高信号质量。Matlab 2022a仿真结果显示,该算法能有效提升系统性能并降低计算复杂度。核心程序包括预编码和接收矩阵的设计,以及不同信噪比下的性能评估。
31 3
|
12天前
|
人工智能 算法 大数据
Linux内核中的调度算法演变:从O(1)到CFS的优化之旅###
本文深入探讨了Linux操作系统内核中进程调度算法的发展历程,聚焦于O(1)调度器向完全公平调度器(CFS)的转变。不同于传统摘要对研究背景、方法、结果和结论的概述,本文创新性地采用“技术演进时间线”的形式,简明扼要地勾勒出这一转变背后的关键技术里程碑,旨在为读者提供一个清晰的历史脉络,引领其深入了解Linux调度机制的革新之路。 ###
|
15天前
|
机器学习/深度学习 算法 数据挖掘
提高时钟置换算法的性能
【10月更文挑战第25天】通过上述一种或多种方法的综合应用,可以在不同程度上提高时钟置换算法的性能,使其更好地适应各种复杂的系统环境和应用场景,提高虚拟内存管理的效率和系统的整体性能。
35 5
|
23天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。
|
22天前
|
存储 缓存 算法
优化轮询算法以提高资源分配的效率
【10月更文挑战第13天】通过以上这些优化措施,可以在一定程度上提高轮询算法的资源分配效率,使其更好地适应不同的应用场景和需求。但需要注意的是,优化策略的选择和实施需要根据具体情况进行详细的分析和评估,以确保优化效果的最大化。
|
23天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
23天前
|
存储 缓存 算法
前端算法:优化与实战技巧的深度探索
【10月更文挑战第21天】前端算法:优化与实战技巧的深度探索
20 1
|
26天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
11天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。