快速排序算法在Java中的实现
作者:Hong_Jerry 发布时间:2022-05-25 01:06:15
快速排序的原理:选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的)。一般选择序列的第一个元素。
一次循环:从后往前比较,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换。找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引,结束第一次循环,此时,对于基准值来说,左右两边就是有序的了。
接着分别比较左右两边的序列,重复上述的循环。
public class FastSort{
public static void main(String []args){
System.out.println("Hello World");
int[] a = {12,20,5,16,15,1,30,45,23,9};
int start = 0;
int end = a.length-1;
sort(a,start,end);
for (int i = 0; i<a.length; i++){
System.out.println(a[i]);
}
}
public void sort(int[] a,int low,int high){
int start = low;
int end = high;
int key = a[low];
while(end>start){
//从后往前比较
while(end>start&&a[end]>=key) //如果没有比关键值小的,比较下一个,直到有比关键值小的交换位置,然后又从前往后比较
end--;
if(a[end]<=key){
int temp = a[end];
a[end] = a[start];
a[start] = temp;
}
//从前往后比较
while(end>start&&a[start]<=key)//如果没有比关键值大的,比较下一个,直到有比关键值大的交换位置
start++;
if(a[start]>=key){
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
//此时第一次循环比较结束,关键值的位置已经确定了。左边的值都比关键值小,右边的值都比关键值大,但是两边的顺序还有可能是不一样的,进行下面的递归调用
}
//递归
if(start>low) sort(a,low,start-1);
//左边序列。第一个索引位置到关键值索引-1
if(end<high) sort(a,end+1,high);
//右边序列。从关键值索引+1到最后一个
}
}
上面最后一句不是基准值的意思是,不是直接用基准值交换,是用基准值所在的索引交换。
下面我们看看另一种实现方式。
一趟快速排序的过程如下
(1)先从序列中选取一个数作为基准数
(2)将比这个数大的数全部放到它的右边,把小于或者等于它的数全部放到它的左边
一趟快速排序也叫做Partion,即将序列划分为两部分,一部分比基准数小,另一部分比基准数大,然后
再进行分治过程,因为每一次Partion不一定都能保证划分得很均匀,所以最坏情况下的时间复杂度不能
保证总是为。
对于Partion过程,通常有两种方法
(1)两个指针从首尾向中间扫描(双向扫描)
这种方法可以用挖坑填数来形容,比如
初始化:i=0;j=9;pivot=a[0];
现在a[0]保存到了变量pivot中了,相当于在数组a[0]处挖了个坑,那么可以将其它的数填到这里来。从j开始向前找一个小于或者等于pivot的数,即将a[8]填入a[0],但a[8]又形成了一个新坑,再从i开始向后找一个大于pivot的数,即a[3]填入a[8],那么a[3]又形成了一个新坑......
就这样,直到i==j才停止,最终得到结果如下
上述过程就是一趟快速排序。
/**
* 功能描述: 快速排序,双向扫描
*
* @date 2017-09-12 10:17
* @since V1.0.0
*/
public class QuickSort {
public static void main(String[] args){
Integer[] arr = {8, 2, 9, 1, 5, 10, 12, 3, 18, 6};
System.out.println(Arrays.asList(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.asList(arr));
}
public static void quickSort(Integer[] arr, int left, int right) {
if(left < right) {
int partition = partition(arr, left, right);
quickSort(arr, left, partition - 1);
quickSort(arr, partition + 1, right);
}
}
public static int partition(Integer[] arr, int left, int right) {
Integer pivot = arr[left];
int i = left, j = right;
while (i < j) {
while (arr[j] >= pivot && i < j) {
j--;
}
arr[i] = arr[j];
while (arr[i] <= pivot && i < j) {
i++;
}
arr[j] = arr[i];
}
arr[i] = pivot;
return i;
}
}
来源:https://www.cnblogs.com/hjy9420/p/5032309.html
猜你喜欢
- Mybatis的Dao层实现传统开发方式1、编写UserDao接口public interface UserMapper {public L
- 1、dose not point to a valid jvm installation出错问题按照以下方法设置一定可以不会出现这个错误。我
- 前2天有读者问到是否有带分页功能的表格控件,今天分页功能的表格控件详细解析。PaginatedDataTablePaginatedDataT
- 我们知道 Spring Boot 已经提供了一套默认的异常处理机制,但是 Spring Boot 提供的默认异常处理机制却并不一定适合我们实
- 英文设置加粗可以在xml里面设置: <SPAN style="FONT-SIZE: 18px">androi
- Java定义Long数据类型Long lg=10L;只需要在定义的的整型后面加个L;就和定义float数据类型一样Float ft=5.20
- Java 继承与多态的深入理解1、 什么是继承,继承的特点?子类继承父类的特征和行为,使得子类具有父类的各种属性和方法。或子类从
- 简介AccessibilityService的设计初衷是为了辅助有身体缺陷的群体使用Android应用,它的设计贯穿着Android的控件树
- ImageCacheconst int _kDefaultSize = 1000;const int _kDefaultSizeBytes
- java 获取字节码文件的几种方法总结在本文中,以Person类为例,将分别演示获取该类字节码文件的三种方式,其具体思想及代码如下所示:pu
- 目录为什么要实现调用链跟踪?如何实现?第一步,看图、看场景,用户浏览器的一次请求行为所走的路径是什么样的第二步,实现。不想看代码可直接拉最后
- 目录项目地址示例图片项目结构机器人平滑碰撞其它特性使用打包文件项目文件声明主要代码项目地址https://github.com/SCNU-A
- 目录一,功能二,工具三、效果图:四、数据库设计五、JAVA层次分析六、主要Java代码分析一,功能管理员登录图书借阅信息管理图书信息管理管理
- 一、HashMap初始化方法HashMap() 不带参数,默认初始化大小为16,加载因子为0.75;HashMap(int initialC
- 爱java 爱dota,突发奇想想用java开发dota操作最华丽的英雄之一的卡尔的技能,因为本人系小白,代码不足的地方还请包涵,有同样爱好
- 在本博客中,可以找到一篇《c#实现输出的字符靠右对齐的示例》它有教大家怎样实现字符串输出进行左齐或者是右对齐。本篇的方法,超简单,是使用st
- 项目需求最近项目中有一个需求就是让Java代码去代替人工操作,自动生成PPT,具体就是查询数据库数据,然后根据模板文件(PPT),将数据库数
- 【题目】 汉诺塔问题比较经典,这里修改一下游戏规则:现在限制不能从最左侧的塔直接移动到最右侧,也不能从最右侧直接移动到最左侧,而是必须经过中
- 一般来讲,项目更换JDK版本的情况比较少,但是有时难免会遇到。电脑安装不同版本的JDK这里不做介绍。这里记录一下修改项目JDK版本要注意的几
- 前言本文主要介绍了关于JDK源码分析之String、StringBuilder和StringBuffer的相关内容,分享出来供大家参考学习,