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

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

文章目录

  • 交换排序
      • 一.冒泡排序
      • 二.快速排序
          • 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

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain