冒泡排序快速排序(前后指针、挖坑、左右指针法)【Java实现】

2024-04-30 10:18

本文主要是介绍冒泡排序快速排序(前后指针、挖坑、左右指针法)【Java实现】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、冒泡排序

思想

对N个元素进行升序排列时,依次比较两个相邻的元素,如果前者大于后者就交换,一趟排序找出一个最大值并放在最后,然后缩小排序区间继续找出该区间的最大值,并放在倒数第二个位置,倒数第一个位置...,直到区间缩小至只剩一个元素,排序完成。整个排序过程要进行N-1趟排序。


原理

1.比较相邻的元素。如果前者比后者大,就交换他们两个。

2.对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤,除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。


待排序序列:  2    5    7    1    3    7

第一趟排序:

2   5   7   1   3   7     ->    2   5   7   1   3   7

2   5   7   1   3   7     ->    2   5   7   1   3   7 

2   5   7   1   3   7     ->    2   5   1   7   3   7

2   5   1   7   3   7     ->    2   5   1   3   7   7

2   5   1   3   7   7     ->    2   5   1   3   7   7

第一趟排序后的序列:2   5   1   3   7   7

第二趟排序:

2   5   1   3   7     ->     2   5   1   3   7

2   5   1   3   7     ->     2   1   5   3   7 

2   1   5   3   7     ->     2   1   3   5   7

2   1   3   5   7     ->     2   1   3   5   7

第二趟排序后的序列:2   1   3   5   7   7 

第三趟排序:

2   1   3   5     ->     1   2   3   5

1   2   3   5     ->     1   2   3   5

1   2   3   5     ->     1   2   3   5

第三趟排序后的序列:1   2   3   5   7   7

第四趟排序:

1   2   3     ->     1   2   3

1   2   3     ->     1   2   3

第四趟排序后的序列:1   2   3   5   7   7

第五趟排序:

1   2     ->     1   2

第五趟排序后的序列:1   2   3   5   7   7

排序完成!


注意

假如给定待排序序列已经有序,如{1,2,4,5,6,7},那么第一次排序便不会交换相邻元素。后续比较排序也是。所以,为了减少已经有序的待排序序列的排序时间,我们可以设置一个标志位flag,初值为false。如果某一次排序过程中有交换元素,便将flag置为true。下一次排序之前又将flag置为1;如果此次排序完成flag仍为1,说明此次排序没有交换任何元素,那么证明该序列已经有序,则不需要再继续进行排序。整个排序过程就完成了。所以最多可进行n-1趟排序。


public class BubbleSort {private int[] arr;private int len;public BubbleSort(int[] arr) {this.arr = arr;this.len = arr.length;}public void bubbleSort() {for (int i = len - 1; i > 0; i--) {//len个元素,总共进行len-1趟排序boolean flag = false;//标识此趟排序是否有元素交换了位置,flag为false表示没交换for (int j = 0; j < i; j++) {//每进行完一趟排序,将要排序的区间缩小1个元素if (arr[j] > arr[j + 1]) {swap(j, j + 1);flag = true;//有元素交换,flag置为true}}//如果一趟排序下来flag一直为false,表明此趟排序没有元素交换位置,说明此时数组已经有序,可结束排序if (flag == false) {return;}}}public void swap(int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}public void print() {for (int i = 0; i < len; i++) {System.out.print(arr[i] + " ");}System.out.println("");}}

稳定性判断

因为冒泡排序是不断把大的元素往后调的过程,此过程是不断比较相邻元素并交换的过程,所以如果两个相邻元素相等的话,我们并不会交换它俩的位置;如果两个元素相等不相邻的话,就算通过交换会将两个相等元素调到相邻,此时我们也不会交换它俩的位置,所以排序前后相同元素的位置顺序并没有改变,所以冒泡排序是一个稳定的排序算法。 

测试类代码如下: 

package com.myself.sort;import java.util.Scanner;public class TestSort {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()) {int len = scanner.nextInt();int[] arr = new int[len];for (int i = 0; i < len; i++) {arr[i] = scanner.nextInt();}//冒泡排序BubbleSort sortArr = new BubbleSort(arr);sortArr.bubbleSort();sortArr.print();}}
}

二、快速排序

快速排序是对冒泡排序的一种改进

思想

通过选择一个基准值将要排序的数据分成两个区间,其中一个区间的所有元素都比基准值小,另一个区间的所有元素都比基准值大。然后采用分而治之的方法对这两部分数据分别进行快速排序,当区间中只剩一个数或者为空时停止此次排序,以此达到整个数据变成有序序列。


快排主要有3种实现方法:hoare法,又称左右指针法;挖坑法前后指针法(现为了简便,下面三种方法均以区间右端点所在元素作为基准值)

左右指针法:定义两个指针begin和end,其初值分别为待排序区间左端点、右端点,begin从左往右走,寻找比基准值小或等的元素,end从右往左走,寻找比基准值大或等的元素。当begin停下时,表面此时的元素大于基准值;当end停下时,表面此时的元素小于基准值。此时交换对应的两个元素,继续上述过程。最后当begin和end相等时,交换其中一个元素和基准值,并返回基准值此时的下标。

以数组{2,9,3,6,7,5}为例,具体排序过程如下图所示

此时基准值5将区间分成两个小区间 ,一个区间内的元素都小于等于5,另一个区间内的元素都大于等于5。

左区间排序如下:

右区间排序如下:

代码实现如下:

//1. 左右指针法private int parition1(int left, int right) {int begin = left;int end = right;while (begin < end) {while ((begin < end) && (arr[begin] <= arr[right])) {//此步的begin<end一定要写,因为如果区间本身已经有序,begin会一直往右走,直到走到end,还会继续往右走begin++;}//此时begin所指向的元素比基准值大while ((begin < end) && (arr[end] >= arr[right])) {//同理,此步的begin<end也一定要写end--;}//此时end所指向的元素比基准值小swap(begin, end);//交换begin和end所指向的元素}swap(begin,right);return begin;}

挖坑法:先将基准值保存起来,此时相当于基准值的位置就空出来了。然后定义两个指针begin和end,其初始值分别为待排序区间的左端点和右端点,begin寻找比基准值大的元素,end寻找比基准值小的元素。当begin找到比基准值大的元素之后,此时将其赋给end所指位置,那么begin所指位置便又空出来了;当end找到比基准值小的元素之后,此时将其赋给begin所指位置,那么此时end所指位置又空出来了。重复上述过程,直到begin==end。此时将基准值赋给begin所指位置并返回下标begin。

以{2,9,3,6,7,5}为例,具体排序过程如下

此时基准值5将区间分成了两个小区间,其中左区间的元素全部小于等于5,右区间的元素全部大于等于5

其中左区间排序如下:

右区间排序如下:

代码实现如下: 

//2. 挖坑法private int parition2(int left, int right) {int key = arr[right];//记录基准值int begin = left;int end = right;while (begin < end) {while ((begin < end) && (arr[begin] <= key)) {begin++;}//此时begin所指向的值比基准值大arr[end] = arr[begin];while ((begin < end) && (arr[end] >= key)) {end--;}arr[begin] = arr[end];}arr[begin] = key;return begin;}

前后指针法:定义两个指针div和cur,初始值均为待排序区间的左端点,其中div所指位置之前表示比基准值小或等的元素,div和cur之间表示比基准值大的元素,cur之后表示待排序部分。在cur遍历整个待排序区域期间,如果cur所指元素小于div所指元素,则交换,此时div++。最后交换div所指元素和基准值,并返回基准值此时的下标。

以数组{2,9,3,6,7,5}为例

此时5将区间分成了两个小区间,分别对两个小区间按同样的方法进行排序。

左区间排序如下所示:

右区间排序如下所示:

代码实现如下: 

//3. 前后指针法private int parition3(int left, int right) {int div = left;int cur;for (cur = left; cur < right; cur++) {if (arr[cur] <= arr[right]) {//遇到cur指向的值小于等于基准值就交换div和cur指向的值,并让div往右走一步,以保证div之前的值都小于等于基准值swap(div, cur);div++;}}//此时cur=rightswap(div, cur);return div;}

快速排序三种方法完整代码如下: 

public class QuickSort {private int[] arr;private int len;public QuickSort(int[] arr) {this.arr = arr;this.len = arr.length;}public void quickSort() {__quickSort(0, len - 1);}private void __quickSort(int left, int right) {if (left == right) {//区间只剩一个元素的情况下不用再进行排序return;}if (left > right) {//区间没有元素了return;}int div = parition3(left, right);__quickSort(left, div - 1);__quickSort(div + 1, right);}
//以下三种方法均以区间最后一个元素作为基准值//1. 左右指针法private int parition1(int left, int right) {int begin = left;int end = right;while (begin < end) {while ((begin < end) && (arr[begin] <= arr[right])) {//此步的begin<end一定要写,因为如果区间本身已经有序,begin会一直往右走,直到走到end,还会继续往右走begin++;}//此时begin所指向的元素比基准值大while ((begin < end) && (arr[end] >= arr[right])) {//同理,此步的begin<end也一定要写end--;}//此时end所指向的元素比基准值小swap(begin, end);//交换begin和end所指向的元素}swap(begin,right);return begin;}//2. 挖坑法private int parition2(int left, int right) {int key = arr[right];//记录基准值int begin = left;int end = right;while (begin < end) {while ((begin < end) && (arr[begin] <= key)) {begin++;}//此时begin所指向的值比基准值大arr[end] = arr[begin];while ((begin < end) && (arr[end] >= key)) {end--;}arr[begin] = arr[end];}arr[begin] = key;return begin;}//3. 前后指针法private int parition3(int left, int right) {int div = left;int cur;for (cur = left; cur < right; cur++) {if (arr[cur] <= arr[right]) {//遇到cur指向的值小于等于基准值就交换div和cur指向的值,并让div往右走一步,以保证div之前的值都小于等于基准值swap(div, cur);div++;}}//此时cur=rightswap(div, cur);return div;}//交换两个元素的值public void swap(int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}public void print() {for (int i = 0; i < len; i++) {System.out.print(arr[i] + " ");}System.out.println("");}
}

测试类代码如下: 

package com.myself.sort;import java.util.Scanner;public class TestSort {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()) {int len = scanner.nextInt();int[] arr = new int[len];for (int i = 0; i < len; i++) {arr[i] = scanner.nextInt();}//快速排序QuickSort quickSort=new QuickSort(arr);quickSort.quickSort();quickSort.print();}}
}

稳定性判断

由于以上三种方法实现快速排序的基本思想都一样,现以左右指针法为例,在左右指针begin和end不断向中间靠拢的过程中,只有begin遇到大于基准值或begin等于end的时候才会停下来,同样,end在遇到小于基准值或begin==end时也会停下来,此时进行begin和end所指元素交换操作,然后继续该过程,直到begin==end。此时交换begin所指元素和基准值,而该过程很有可能会把前面元素的稳定性打乱,以{2,9,3,6,5,5}为例,交换基准值5和9的位置,会让基准值(第二个5)跑到第一个5的前面,导致排序前后相同元素的前后顺序不一致,所以快速排序是一个不稳定的排序算法。

这篇关于冒泡排序快速排序(前后指针、挖坑、左右指针法)【Java实现】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/948592

相关文章

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Java操作Word文档的全面指南

《Java操作Word文档的全面指南》在Java开发中,操作Word文档是常见的业务需求,广泛应用于合同生成、报表输出、通知发布、法律文书生成、病历模板填写等场景,本文将全面介绍Java操作Word文... 目录简介段落页头与页脚页码表格图片批注文本框目录图表简介Word编程最重要的类是org.apach

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

SpringBoot+Docker+Graylog 如何让错误自动报警

《SpringBoot+Docker+Graylog如何让错误自动报警》SpringBoot默认使用SLF4J与Logback,支持多日志级别和配置方式,可输出到控制台、文件及远程服务器,集成ELK... 目录01 Spring Boot 默认日志框架解析02 Spring Boot 日志级别详解03 Sp

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

java中反射Reflection的4个作用详解

《java中反射Reflection的4个作用详解》反射Reflection是Java等编程语言中的一个重要特性,它允许程序在运行时进行自我检查和对内部成员(如字段、方法、类等)的操作,本文将详细介绍... 目录作用1、在运行时判断任意一个对象所属的类作用2、在运行时构造任意一个类的对象作用3、在运行时判断