Java实现快速排序过程分析
作者:CGZ_PaPa 发布时间:2023-07-27 18:40:57
快速排序过程
没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”!光听这个名字是不是就觉得很高端呢。
假设我们现在对“52 39 67 95 70 8 25 52'”这个8个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数70作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在70的右边,比基准数小的数放在70的左边,类似下面这种排列:
8 25 39 52 52' 67 70 95
在初始状态下,数字70在序列的第5位。我们的目标是将70挪到序列中间的某个位置,假设这个位置是k。现在就需要寻找这个k,并且以第k位为分界点,左边的数都小于等于70,右边的数都大于等于70。想一想,你有办法可以做到这点吗?
基本思想是分治的思想,说到分治,就应该想到和递归是分不开的。
有些书上会使用关键字比较的表述,有些书上会直接使用记录比较表述,这两种说法是两个维度上的说法。这里序列元素的关键字属于记录的一部分,为了简化问题,本文的讨论并不区分关键字和记录,代码实现中使用整数来表示记录。简而言之,本文的讨论简化为,对整型数组的快速排序。
通过一趟排序将要排序的记录分割成两部分,一部分的关键字值比别一部分的所有关键字都小,然后再依次对前后两部分的记录进行快速排序,递归该过程,直到序列中所有记录都是有序为止。
步骤
1)分解。选择第一个元素作为基准数,将输入序列array[m…n]划分成两个非空序列array[m…k]和array[k+1…n],使array[m…k]中任一元素的值不大于array[k+1…n]任一元素值。
2)递归求解。通过递归调用快排算法分别对array[m…k]和array[k+1…n]进行排序
3)合并。由于对分解出的两个子序列排序都是原地进行的,所以在array[m…k]和array[k+1…n]都排好序后不需要再执行任何计算,就能将array[m…n]排好序。因此这一步是不需要在程序中体现的。
排序过程分析
初始关键字:52 39 67 95 70 8 25 52' ,下面将列出每一趟执行的结果。
基准52: 52 39 67 95 70 8 25 52'
基准25: 8 25 39 52 70 95 67 52‘
基准70: 8 25 39 52 52' 67 70 95
基准52‘:8 25 39 52 52' 67 70 95
算法分析
快速排序的时间复杂度与关键字初始序列有关。
最坏时间复杂度:O(n^2):
以第一个数或最后一个数为基准时,当初始序列整体或局部有序时,快速排序的性能会下降。若整体有序,此时,每次划分只能分出一个元素,具有最坏时间复杂度,快速排序将退化成冒泡排序。
最好时间复杂度:
每次选取的基准关键字都是待排序列的中间值,也就是说每次划分可以将序列划分为长度相等的两个序列。快速排序的递归过程可以用一棵二叉树来表示,递归树的高度是2为底的对数,每层需要比较的次数是n/2,所以最好时间复杂度是O(n*以2为底n的对数),因为很多时候输入序列都是乱序的,所以最好时间复杂度也是平均时间复杂度。
三种快排和四种优化方法
三种快排
这里区分的方式是不同基准的选择方法:
1)固定位置,取第一个或最后一个元素作为基准。这种选取方法不合适局部有序的输入。
2)随机选取基准,利用随机算法,选取待排序序列中任意一个元素作为基准。
3)三数取中,取数列中第一个数,中间位置的数,最后一个数作一个平均值作为基准。
四种优化
1)当排序序列长度分割到一定程度时,使用插入排序
对于N很小或局部有序的数组,直接插入排序的效率非常高。
2)在一次分割结束后,可以把与基准数相等的元素聚在一起,下次分割时忽略掉这些元素。
对于含有重复元素比较多的序列,这种优化方法效果比较好,可以减少很多跌代次数。
具本过程:
第一步:在划分过程,把与所选取的基准数相等的元素放在数组的两端。
第二步:划分结束后,把两端的与基准数相等的元素移到基准数最终位置的两侧。
3)优化递归操作。
4)使用多线程并行处理子划分。
Partition方法在求TopK问题上的应用
TopK问题即求序列中最大或最小的K个数。这里以求最小K个数为例。
快速排序的思想是使用一个基准元素将数组划分成两部分,左侧都比基准数小,右侧都比基准数大。
给定数组array[low…high],一趟快排划分后的结果有三种:
1)如果基准数左侧元素个数Q刚好是K-1,那么在基准数左侧(包含基准数本身),即为TopK的所有元素。
2)如果基准数左侧元素个数Q小于K-1,那么说明基准数左侧的Q个数都是TopK里的元素,只需要在基准数的右侧找出剩下的K-Q个元素即可。问题转化成了以基准数下标为起点,高位(high)为终点的Top(K-Q)。递归下去即可。
3)如果基准数左侧元素个数Q大于K-1,说明第K个位置,在基准数的左侧,需要缩小搜索范围,在低位(low)至基准数位置重复递归即可,最终问题会转化成上面两种情况。
快排java实现
在手写快排算法时,最好先把一趟排序的过程写出来。
package sort;
public class QuickSort {
// 暴露只一个参数的公共接口
public void quickSort(int a[]) {
sort(a, 0, a.length - 1);
}
// 快排算法的真正实现
private void sort(int[] a, int low, int high) {
if (low >= high)
return;
int i = low, j = high; // 设置这两个变量的目的是为了保持low和high不变
int pivotNum = a[i]; // 基准数
while (i < j) {
while (a[j] >= pivotNum && j > i) { // 循环结束的条件有二:一是找到比支点小的数,二是j==i
j--;
}
if (j > i) { // 由于上面循环结束的功能性有两个,对于找到比支点小的数,即j!=i,要进行位置的交换,下同
a[i] = a[j];
i++;
}
while (a[i] < pivotNum && i < j) {
i++;
}
if (i < j) {
a[j] = a[i];
j--;
}
}
a[i] = pivotNum;
sort(a, low, i - 1);
sort(a, i + 1, high);
}
public static void main(String[] args) {
int[] a = { 52, 39, 67, 95, 70, 8, 25, 52 };
new QuickSort().quickSort(a);
for (int i : a) {
System.out.print(i + " ");
}
}
}
来源:https://blog.csdn.net/joson793847469/article/details/52738983
猜你喜欢
- 大致思路:注解实现方式:就是用 反射机制. 获取指定的包下使用了注解的类,存储在一个map容器, 然后获取map容器下类的属性, 利用反射给
- 接口回调是指:可以把使用某一接口的类创建的对象的引用赋给该接口声明的接口变量,那么该接口变量就可以调用被类实现的接口的方法。实际上,当接口变
- 一,问题采取eureka集群、客户端通过Ribbon调用服务,Ribbon端报下列异常java.net.UnknownHostExcepti
- 这篇文章向大家分享了几段代码,主要是关于Thread+IO文件的加密解密,下面看看具体代码:加密启动线程package com.hz.sub
- 什么是注解在早期的工作的时候 ,自定义注解写的比较多,可大多都只是因为 这样看起来 不会存在一堆代码耦合在一起的情况,所以使用了自定义注解,
- 1 问题手写一个程序,完成List集合对象的逆序遍历2 方法创建List接口的多态对象向创建好list集合添加元素使用hasPrevious
- 如下所示: /** * 判断某个界面是否在前台 * * @param context
- 一、java final基本概念:1、主要用于修饰类、属性和方法:被final修饰的类不可以被继承被final修饰的方法不可以被重写被fin
- Collections是一个工具类,sort是其中的静态方法,是用来对List类型进行排序的,它有两种参数形式: public static
- static :静态常量,静态方法,静态代码块静态变量: 静态变量属于类的,使用类名来访问,非静态变量是属于对象的,"必须&quo
- 本文实例讲述了Java Web项目部署在Tomcat运行出错与解决方法。分享给大家供大家参考,具体如下:1、在部署Java Web项目的过程
- Java-关键字:final1 .final可以用来修饰的结构:类、方法、变量2.final 用来修饰一个类:此类不能被其他类所继承比如:S
- 本文实例为大家分享了java实现五子棋程序的具体代码,供大家参考,具体内容如下知识点1、Swing 编程2、ImageIO 类的使用3、图片
- 前言 短时间提升自己最快的手段就是背面试题,最近总结了Java常用的面试题,分享给大家,希望大家都能圆梦大厂,加油,我命由我不由天
- 传统的web项目,只需要在web.xml里配置多个即可,并且支持多个url-pattern在spring boot中,我们默认无需配置,系统
- 本文实例为大家分享了java实现随机数生成器的具体代码,供大家参考,具体内容如下自己编的随机数生成器,比较简陋,功能也单一,当作练手。App
- 可能导致问题的原因:1.nacos中的配置文件名不规范,官网有命名规则:“前缀”-&ldqu
- 0. Iochttps://docs.spring.io/spring-framework/docs/current/spring-fram
- Android Build类的详解及简单实例一、类结构:java.lang.Object? android.os.Build二、类概述:从系
- 题目一链表题——操作链表根据给定的链表按照指定条件删除其中节点并返回新的头节点具体题目如下解法/**