常用算法Java实现之快速排序
2024-08-26 08:07:03
快速排序和冒泡排序相似,都是通过多次比较和交换来实现排序。
具体流程如下:
1、首先设定一个分界值,通过分界值将数组分成左右两部分,将大于等于分界值的数据交换集中到右侧数组,将小于分界值的数据交换集中到左侧数组;
2、然后,左侧数组和右侧数组可以独立排序。对于左侧数组可以取一个分界值,将左侧数组分成左右两个部分,同样将左边放置小于分界值的数据,右侧放置大于等于分界值的数据。对右侧数组做类似处理。
3、重复上述过程,其实就是递归。通过递归将左侧数组排好序后,再递归处理右侧数据。当左、右两部分数据都排好序后,整个数组的排序也就完成了。
假如有初始数据:25 11 45 26 12 78。
1、首先设定一个分界值,这里选择第一个元素---25。在变量left中保存数组的最小序号0,在变量right中保存数组的最大序号6,在变量base中保存分界值25。
2、从数组右侧开始,逐个与分界值25比较,直到找到小于base的数据为止。这里,12 就比分界值25小。
3、将右侧比分界值小的数据,保存到 A[left](A[0])元素中。
4、从数组左侧开始,逐个与分界值25比较,直到找到大于等于base的数据为止。这里,数组最左侧的数据为12,比分界值小,将left自增1,再取A[left](A[1])的值为45,因45大于25,结束查找。
5、将左侧比分界值大的数保存到A[right]元素中。
6、将分界值保存到A[left]中。经过一轮比较和交换,base数据左侧的数都是比base值小的数,右侧都是比base值大的数。
7、接下来,通过递归调用,将left左侧的数据进行同样的排序,再将left右侧的数据进行同样的排序。
快速排序对冒泡排序进行了改进,因此具有更好的执行效率。平均时间复杂度是O(nlogn)。
Java 代码实现如下:(https://github.com/xbk417/algorithm)
public void sort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
} private static void quickSort(int[] arr, int left, int right){
int t;
int ltemp = left;
int rtemp = right;
// 分界值
int fIndex = arr[(left + right)/ 2];
while(ltemp < rtemp) {
// 从左侧开始查找比分界值大的数
while(arr[ltemp] < fIndex) {
// 元素小于分界值,继续查找
++ltemp;
}
// 从右侧开始查找比分界值小的数
while(arr[rtemp] > fIndex) {
// 元素大于分界值,继续查找
--rtemp;
}
// 如果查到的比分界值大的数的下标小于等于比分界值小的数的下标,则进行交换
if(ltemp <= rtemp) {
t = arr[ltemp];
arr[ltemp] = arr[rtemp];
arr[rtemp] = t;
--rtemp;
++ltemp;
}
if(ltemp == rtemp) {
ltemp++;
}
System.out.println( Arrays.toString(arr));
if(left < rtemp) {
quickSort(arr, left, ltemp - 1);
}
if(ltemp < right) {
quickSort(arr, rtemp + 1, right);
}
}
}
最新文章
- 精简版StringBuilder,提速字符串拼接
- bzoj1503
- 【Oracle】ORA-00257:archiver error. Connect internal only, until freed 错误的处理方法
- Android HTTPS(2)HttpURLConnection.getInputStream异常的原因及解决方案
- mysql的top n查询
- 逐行返回http响应的内容
- ArcGIS Runtime SDK for Android开发之调用GP服务(异步调用)
- IO库 8.4
- 二.redis 数据类型
- 最新的css3动画按钮效果
- Java - Instrumentation
- 解决Linux系统下Mysql数据库中文显示成问号的问题
- GIT导出差异版本更新的文件列表
- windows计划任务启动bat执行java文件
- 老男孩python学习自修【第一天】文件IO用法
- node.js中fs文件系统模块的使用
- python 目录切换
- Python调用sqlAlchemy
- Android开发者不可或缺的四大工具
- MongoDB多文档查询
热门文章
- ;(function($,window,document,undefined){})(jQuery,window,document)
- 使用Hbuilder开发IOS应用上架审核提示请指定用户在位置许可模式警报中使用位置的预定用途。
- Win7装在其他盘 (非C盘)办法
- Rsync+inotify实现文件实时同步#附shell脚本
- python 两个面试题
- MongoDB入门---文档操作之增删改
- linux 网络编程 1---(基本概念)
- PHP.49-TP框架商城应用实例-前台1-公共布局、制作首页
- 根据exe获取图标的方法
- 【公司动态添加行】前台穿一个json的字符串到后台,并解析