冒泡排序快速排序(前后指针、挖坑、左右指针法)【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

相关文章

IDEA运行spring项目时,控制台未出现的解决方案

《IDEA运行spring项目时,控制台未出现的解决方案》文章总结了在使用IDEA运行代码时,控制台未出现的问题和解决方案,问题可能是由于点击图标或重启IDEA后控制台仍未显示,解决方案提供了解决方法... 目录问题分析解决方案总结问题js使用IDEA,点击运行按钮,运行结束,但控制台未出现http://

解决Spring运行时报错:Consider defining a bean of type ‘xxx.xxx.xxx.Xxx‘ in your configuration

《解决Spring运行时报错:Considerdefiningabeanoftype‘xxx.xxx.xxx.Xxx‘inyourconfiguration》该文章主要讲述了在使用S... 目录问题分析解决方案总结问题Description:Parameter 0 of constructor in x

解决IDEA使用springBoot创建项目,lombok标注实体类后编译无报错,但是运行时报错问题

《解决IDEA使用springBoot创建项目,lombok标注实体类后编译无报错,但是运行时报错问题》文章详细描述了在使用lombok的@Data注解标注实体类时遇到编译无误但运行时报错的问题,分析... 目录问题分析问题解决方案步骤一步骤二步骤三总结问题使用lombok注解@Data标注实体类,编译时

JSON字符串转成java的Map对象详细步骤

《JSON字符串转成java的Map对象详细步骤》:本文主要介绍如何将JSON字符串转换为Java对象的步骤,包括定义Element类、使用Jackson库解析JSON和添加依赖,文中通过代码介绍... 目录步骤 1: 定义 Element 类步骤 2: 使用 Jackson 库解析 jsON步骤 3: 添

Java中注解与元数据示例详解

《Java中注解与元数据示例详解》Java注解和元数据是编程中重要的概念,用于描述程序元素的属性和用途,:本文主要介绍Java中注解与元数据的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参... 目录一、引言二、元数据的概念2.1 定义2.2 作用三、Java 注解的基础3.1 注解的定义3.2 内

Java中使用Java Mail实现邮件服务功能示例

《Java中使用JavaMail实现邮件服务功能示例》:本文主要介绍Java中使用JavaMail实现邮件服务功能的相关资料,文章还提供了一个发送邮件的示例代码,包括创建参数类、邮件类和执行结... 目录前言一、历史背景二编程、pom依赖三、API说明(一)Session (会话)(二)Message编程客

Java中List转Map的几种具体实现方式和特点

《Java中List转Map的几种具体实现方式和特点》:本文主要介绍几种常用的List转Map的方式,包括使用for循环遍历、Java8StreamAPI、ApacheCommonsCollect... 目录前言1、使用for循环遍历:2、Java8 Stream API:3、Apache Commons

JavaScript中的isTrusted属性及其应用场景详解

《JavaScript中的isTrusted属性及其应用场景详解》在现代Web开发中,JavaScript是构建交互式应用的核心语言,随着前端技术的不断发展,开发者需要处理越来越多的复杂场景,例如事件... 目录引言一、问题背景二、isTrusted 属性的来源与作用1. isTrusted 的定义2. 为

C#提取PDF表单数据的实现流程

《C#提取PDF表单数据的实现流程》PDF表单是一种常见的数据收集工具,广泛应用于调查问卷、业务合同等场景,凭借出色的跨平台兼容性和标准化特点,PDF表单在各行各业中得到了广泛应用,本文将探讨如何使用... 目录引言使用工具C# 提取多个PDF表单域的数据C# 提取特定PDF表单域的数据引言PDF表单是一

使用Python实现高效的端口扫描器

《使用Python实现高效的端口扫描器》在网络安全领域,端口扫描是一项基本而重要的技能,通过端口扫描,可以发现目标主机上开放的服务和端口,这对于安全评估、渗透测试等有着不可忽视的作用,本文将介绍如何使... 目录1. 端口扫描的基本原理2. 使用python实现端口扫描2.1 安装必要的库2.2 编写端口扫