java实现快速排序图解_快速排序图文详解
2023-06-13 09:14:31 时间
快速排序
快速排序法介绍
- 快速排序(QuickSort)是对冒泡排序的一种改进,基本思想是:通过一趟排序将 要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
图解
代码理解
public class QuickSort {
//从小到大排序
public void quickSort(int left, int right, int[] nums){
if(left<right){
//将小于nums[left]的值放左边,大于nums[left]的值放右边
int index = partition(left, right, nums);
//对左边部分进行快速排序
quickSort(left, index, nums);
//对右边部分进行快速排序
quickSort(index+1, right, nums);
}
}
private int partition(int left, int right, int[] nums) {
/** * 这一部分的理解,我们可以假设此时数组排序为【2,1,3,4,5】 * 那么while (left<right&&nums[right]>base) * 会循环到right=1 * 之后数组变化如下 * nums[left]=nums[right] * 【1,1,3,4,5】 * while (left<right&&nums[left]<base)循环到left=1 * nums[right]=nums[left]相当于什么都没做 * 此时left等于right,跳出循环 * 整个过程可以简化为 * base = nums[left] * nums[left]=nums[right] * nums[right]=base */
int base = nums[left];
while (left<right){
while (left<right&&nums[right]>=base){
right--;
}
nums[left] = nums[right];
while (left<right&&nums[left]<=base){
left++;
}
nums[right] = nums[left];
}
nums[right] = base;
return left;
}
public static void main(String[] args) {
int[] nums = {
2,3,1,5,4};
QuickSort quickSort = new QuickSort();
quickSort.quickSort(0,nums.length-1, nums);
for(int num:nums){
System.out.println(num);
}
}
}
快速排序算法性能分析
- 快速排序的时间性能取决于快速排序递归的深度。
- 在最优的情况下,Partition每次都划分得很均匀,如果排序n个数值,那么递归树的深度就为.log2n.+1(.x.表示不大于x的最大整数),即仅需递归log2n次,其时间复杂度为O(nlogn)
- 在最坏的情况下,待排序的序列为正序或者逆序,每次划分只得到一个比上一次划分少一个数值的子序列,此时需要执行n-1次递归调用且第i次划分需要经过n-i次比较才能得到第i个数值,其时间复杂度为O(n^2)
算法图
- 口诀:堆归选基与初始序列无关 快选希堆排序不稳定
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/179508.html原文链接:https://javaforall.cn
相关文章
- Java多线程详解_java支持多线程
- 快速排序算法详细图解JAVA_实现快速排序
- 编写java判断闰年_用Java程序判断是否是闰年的简单实例[通俗易懂]
- java启动器_JAVA基础:Java 启动器如何查找类
- java冒泡排序经典代码_Java 8大经典排序算法(含源代码),必须收藏!
- java 工厂模式例子_java 工厂模式简单介绍及例子[通俗易懂]
- JAVA中的数组插入与删除指定元素
- Java XML解析工具类
- java常用类之Calendar类[通俗易懂]
- Java的学习笔记(16)异常处理
- Java连接Mysql:探索数据库之路。(java链接mysql)
- MySQL与Java的无缝互联(java与mysql连接)
- java spring boot 定时器详解编程语言
- Java远程登录Linux服务器入门指南(java远程linux)
- 服务器上的文件Java获取Linux服务器文件:简单又高效的操作方法(java获取linux)
- Java神器:集成Redis,提高效率!(java集成redis)
- 深入学习:Linux下Java环境建设与配置(linux下java环境)
- 如何在Linux系统下成功安装Java?(linux下安装java)
- 器使用Java管理Linux服务器变得如此容易(javalinux服务)
- 通往成功的道路通过Java考证Oracle获取更高的成就(java考证oracle)
- 在Java中利用Oracle数据库进行应用开发(java中oracle)
- 深入java垃圾回收的详解
- Java设计模式之中介者模式(MediatorPattern)简介