交换排序详讲：冒泡排序+快速排序+快排优化+非递归实现（多方法+思路+图解+代码）

2023-11-21 09:52
文章标签 代码 实现 方法 优化 快速 排序 图解 交换 递归 冒泡排序 快排 思路 详讲

本文主要是介绍交换排序详讲：冒泡排序+快速排序+快排优化+非递归实现（多方法+思路+图解+代码），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 交换排序
      • 一.冒泡排序
      • 二.快速排序
          • 1.挖坑法
          • 2.Hoare法
          • 3.前后指针法
          • 4.快速排序的优化
            • 方法一：随机选取基准值
            • 方法二：三数取中法选基准值
            • 方法三：递归到最小区间时、用插入排序
          • 5.快速排序非递归实现

交换排序

  • 根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置
  • 将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

一.冒泡排序

在这里插入图片描述

    /*** 冒泡排序* 时间复杂度 n^2* 空间复杂度  1* @param array*/public static void bubbleSort(int[]array){for (int i = 0; i < array.length-1; i++) {//趟数boolean flg =false;for (int j = 0; j < array.length-1-i; j++) {if (array[j]>array[j+1]){swap(array,j,j+1);flg = true;}}if (flg == false){return;}}}

1.遍历 i 代表交换的趟数，遍历 j 进行两两交换

2.j < array.length-1-i 是对于趟数的优化，每走一趟，交换就少一次

3.boolean flg =false;当两两交换时，flg变为true

4.进一步优化：如果遍历完，没发生交换，flg还是false,直接返回，排序结束

  • 时间复杂度：O ( N2 )
  • 空间复杂度：O ( 1 )
  • 稳定性：稳定

二.快速排序

  • 二叉树结构的交换排序方法

  • 任取一个待排序元素作为基准值，把序列一分为二，左子序都比基准值小，右子序都比基准值大，左右两边再重复进行

在这里插入图片描述

  • 左边找比基准值大的，右边找比基准值小的
1.挖坑法

在这里插入图片描述

  • 基准值位置挖一个坑，后面找一个比基准值小的把坑埋上
  • 前面找一个比基准值大的，埋后面的坑
  • 当l==r时，把基准值填入剩下的坑中

在这里插入图片描述

  • 左右两边重复进行上述步骤，直到排完为止
  • 左右两边都以同样的方法进行划分，运用递归来实现
    /*** 快速排序 ---挖坑法** @param array*/public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int start, int end) {if (start >= end) {return;//结束条件// start == end，说明只剩一个了，是有序的，返回//start > end ,说明此时的基准值在开头或者末尾//在开头：start不变，end=pivot-1,start > end ，end=-1 没有左树//在结尾：end不变，start = pivot+1,start > end,超出索引，没有右树}//不断递归quickint pivot = partition(array, start, end);// 进行排序，划分找到pivot//然后递归划分法左边，递归划分的右边quick(array, start, pivot - 1);quick(array, pivot + 1, end);}//划分，返回基准值private static int partition(int[] array, int left, int right) {int tmp = array[left];//挖一个坑，取left位置为基准值while (left < right) {//在右边找一个比基准值小的把坑填上while (left < right && array[right] >= tmp) {//防止越界right--;}array[left] = array[right];//找到比tmp小的数，填坑,//在左边找一个比tmp大的值，填到右边的坑while (left < right && array[left] <= tmp) {//防止越界left++;}array[right] = array[left];}//如果相遇了，退出循环array[left] = tmp;//填坑return left;}

  • 先划分序列，递归左边，然后再递归右边

  • 递归结束条件：

    start == end时，说明只剩一个了，是有序的，返回
    start > end 时 ,说明此时的基准值在开头或者末尾

    如果基准值在开头：start不变，end=pivot-1,start > end ，end=-1 没有左树
    如果基准值在结尾：end不变，start = pivot+1,start > end,超出索引，没有右树

2.Hoare法

在这里插入图片描述

  • 不同的方法，找出基准值，排的序列是不一样的

在这里插入图片描述

  • i记录基准值一开始在left位置的下标
  • r找到比基准值小的停下来，l找到比基准值大的停下来，互相交换
  • l和r相遇的时候，把i 记录基准值的初始下标和相遇位置交换

以左边为基准，先找右边再找左边，相遇的位置就是以右边为基准的值，要比基准小，才能交换

    /*** Hoare法 划分排序找基准值* @param array* @param left* @param right* @return*/private static int partition2(int[] array, int left, int right) {int tmp = array[left];int i  = left;//记录基准值一开始在left位置的下标while (left < right) {while (left < right && array[right] >= tmp) {right--;}while (left < right && array[left] <= tmp) {left++;}swap(array,left,right);}swap(array,i,left);return left;}
3.前后指针法

在这里插入图片描述

在这里插入图片描述

  • prev记录了比key小的最后一个位置
  • cur去找比key值小的，找到后，放到prev的下一个位置
  • 最后找到基准值，并且基准值的左边都比它小，右边都比他大
    /*** 前后指针法，划分排序找基准值** @param array* @param left* @param right* @return*/private static int partition3(int[] array, int left, int right) {int prev = left; //prev从left位置开始，left为当前的基准值int cur = left + 1;//cur在prev的后一个while (cur <= right) {//遍历完当前数组段if (array[cur] < array[left] && array[++prev] != array[cur]) {//只要cur指向的值小于left位置的基准值//并且prev++后不等于cur的值swap(array, cur, prev);//将cur和prev位置的值交换//cur++;}//如果cur的值大于基准值,或者prev下一位的值等于cur,cur后移cur++;}//cur越界，循环结束，最后，交换基准值和prev位置的值//prev记录的就是比基准值小的最后一个数swap(array, prev, left);return prev;//prev为基准值}
4.快速排序的优化

  • 时间复杂度：

    最好情况：O (N*log2N) ：树的高度为log2N，每一层都是N

    最坏情况:O (N2)：有序、逆序的情况下,没有左树，只有右树，单分支树，树的高度是N,每一层都是N

  • 空间复杂的：

    最好情况：O (log2N)：满二叉树（均匀分割待排序的序列，效率最高）树高为 log2N

    最坏情况：O（N）:单分支树,树高为N

  • 稳定性：不稳定

  • 快速排序有可能发生栈溢出异常，需要进行优化

  • 所以要能均匀分割待排序的序列

递归的次数多了，会导致栈溢出，所以优化的方向就是减少递归的次数

在最坏情况下，比如顺序，基准值都取自左边，本身没有左树

方法一：随机选取基准值

看人品，有概率

方法二：三数取中法选基准值

三数：第一个数、中间的数、最后一个数 ，在这三个数中，选出中等值

有可能会变成二分查找 ，避免了出现最坏情况，从中值来比较排序，左右树都有

    public static void quickSort(int[] array) {quick2(array, 0, array.length - 1);}private static void quick2(int[] array, int start, int end) {if (start >= end) {return;//结束条件}//三数取中法int index = midThree(array, start, end);//选出的数和开头交换swap(array,index,start);int pivot = partition(array, start, end);// 进行排序，划分找到pivot//然后递归划分法左边，递归划分的右边quick2(array, start, pivot - 1);quick2(array, pivot + 1, end);}/*** 三数取中* @param array* @param left* @param right* @return*/private static int midThree(int[] array, int left, int right) {int mid = (left + right) / 2;if (array[left] < array[right]) {if (array[mid] < array[left]) {return left;} else if (array[mid] > array[right]) {return right;} else {return mid;}} else {if (array[mid] < array[right]) {return right;} else if (array[mid] > array[left]) {return left;} else {return mid;}}}
方法三：递归到最小区间时、用插入排序

进一步优化：减少递归的次数：

  • 把快排的递归想象成二叉树，最后两层包含了大部分数，我们要减少这部分的递归

  • 前几次的找基准值排序，导致后面几层趋于有序，用直接插入法来排序，进一步提高效率，有点像希尔排序

如果树的高度为h,最后一层就有 2 h-1 个结点 ，后两层占了绝大部分

设置条件：end-start+1 就是当前待排序列的长度，如果小于等于某个较小的值，直接采用插入排序来排剩下的

 private static void quick2(int[] array, int start, int end) {if (start >= end) {return;//结束条件}//优化----减少递归的次数if(end-start+1<=20){//如果当前数列的长度，小于=15的时候，// 用插入排序,然后退出insertSortQ(array,start,end);return;}//三数取中法int index = midThree(array, start, end);swap(array,index,start);int pivot = partition(array, start, end);// 进行排序，划分找到pivot//然后递归划分法左边，递归划分的右边quick2(array, start, pivot - 1);quick2(array, pivot + 1, end);}/*** 插入排序---来排剩下的待排部分，给定需要的区间*/private static void insertSortQ(int[] array,int left,int right) {for (int i = left+1; i <= right; i++) {int tmp = array[i];int j = i - 1;for (; j >= left; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {break;}}array[j + 1] = tmp;}}
5.快速排序非递归实现
  • 1.通过使用栈来实现
  • 2.每次找到基准值后，把两段序列的开头和末尾压栈
  • 3.从栈顶取出两个元素作为新序列的首尾，再次找基准值
  • 4.找到基准值后，如果右边有一个元素，不进栈，有两个元素的才能进栈
  • 5.pivot< end-1:证明右边有两个元素，pivot>s+1：证明左边有两个元素
  • 6.栈为空的时候，排完元素
    /*** 非递归实现快速排序** @param array*/public static void quickSortNonRecursive(int[] array) {Deque<Integer> stack = new LinkedList<>();//利用栈来实现int left = 0;int right = array.length - 1;//先找到基准值int pivot = partition(array, left, right);//左边有两个元素时，根据基准值进栈if (pivot > left + 1) {stack.push(left);stack.push(pivot - 1);}//有边有两个元素时，根据基准值进栈if (pivot < right - 1) {stack.push(pivot + 1);stack.push(right);}//栈不为空的时候，取两个栈顶元素做为区间//再次进栈出栈while (!stack.isEmpty()) {right = stack.pop();left = stack.pop();pivot = partition(array, left, right);//左边有两个元素时，根据基准值进栈if (pivot > left + 1) {stack.push(left);stack.push(pivot - 1);}//有边有两个元素时，根据基准值进栈if (pivot < right - 1) {stack.push(pivot + 1);stack.push(right);}}}

点击移步博客主页，欢迎光临~

偷cyk的图

这篇关于交换排序详讲：冒泡排序+快速排序+快排优化+非递归实现（多方法+思路+图解+代码）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/401573。

相关文章

Vue3 的 shallowRef 和 shallowReactive：优化性能

Vue3 的 shallowRef 和 shallowReactive：优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉，那么对 shallowRef 和 shallowReactive 是否了解呢？ 在编程和数据结构中，“shallow”（浅层）通常指对数据结构的最外层进行操作，而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素，而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层（Shallow） 定义
阅读更多...
HDFS—存储优化（纠删码）

HDFS—存储优化（纠删码）

纠删码原理 HDFS 默认情况下，一个文件有3个副本，这样提高了数据的可靠性，但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码，采用计算的方式，可以节省约50％左右的存储空间。 此种方式节约了空间，但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件，都会执行此策略。 默认只开启对 RS-6-3-1024k
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2