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

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。

相关文章

Java实现检查多个时间段是否有重合

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1：定义时间段类步骤2：添加时间段步骤3：检查时间段是否有重合步骤4：输出结果示例代码结语作
阅读更多...
Nginx设置连接超时并进行测试的方法步骤

Nginx设置连接超时并进行测试的方法步骤

《Nginx设置连接超时并进行测试的方法步骤》在高并发场景下,如果客户端与服务器的连接长时间未响应,会占用大量的系统资源,影响其他正常请求的处理效率,为了解决这个问题,可以通过设置Nginx的连接... 目录设置连接超时目的操作步骤测试连接超时测试方法：总结：设置连接超时目的设置客户端与服务器之间的连接
阅读更多...
Java判断多个时间段是否重合的方法小结

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D
阅读更多...
Python使用国内镜像加速pip安装的方法讲解

Python使用国内镜像加速pip安装的方法讲解

《Python使用国内镜像加速pip安装的方法讲解》在Python开发中,pip是一个非常重要的工具,用于安装和管理Python的第三方库,然而,在国内使用pip安装依赖时,往往会因为网络问题而导致速... 目录一、pip 工具简介1. 什么是 pip？2. 什么是 -i 参数？二、国内镜像源的选择三、如何
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
IDEA编译报错“java: 常量字符串过长”的原因及解决方法

IDEA编译报错“java: 常量字符串过长”的原因及解决方法

《IDEA编译报错“java:常量字符串过长”的原因及解决方法》今天在开发过程中,由于尝试将一个文件的Base64字符串设置为常量,结果导致IDEA编译的时候出现了如下报错java:常量字符串过长,... 目录一、问题描述二、问题原因2.1 理论角度2.2 源码角度三、解决方案解决方案①：StringBui
阅读更多...
Linux使用nload监控网络流量的方法

Linux使用nload监控网络流量的方法

《Linux使用nload监控网络流量的方法》Linux中的nload命令是一个用于实时监控网络流量的工具,它提供了传入和传出流量的可视化表示,帮助用户一目了然地了解网络活动,本文给大家介绍了Linu... 目录简介安装示例用法基础用法指定网络接口限制显示特定流量类型指定刷新率设置流量速率的显示单位监控多个
阅读更多...
Java覆盖第三方jar包中的某一个类的实现方法

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下：需要在
阅读更多...
JavaScript中的reduce方法执行过程、使用场景及进阶用法

JavaScript中的reduce方法执行过程、使用场景及进阶用法

《JavaScript中的reduce方法执行过程、使用场景及进阶用法》：本文主要介绍JavaScript中的reduce方法执行过程、使用场景及进阶用法的相关资料,reduce是JavaScri... 目录1. 什么是reduce2. reduce语法2.1 语法2.2 参数说明3. reduce执行过程
阅读更多...
C#中读取XML文件的四种常用方法

C#中读取XML文件的四种常用方法

《C#中读取XML文件的四种常用方法》Xml是Internet环境中跨平台的,依赖于内容的技术,是当前处理结构化文档信息的有力工具,下面我们就来看看C#中读取XML文件的方法都有哪些吧... 目录XML简介格式C#读取XML文件方法使用XmlDocument使用XmlTextReader/XmlTextWr
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2