高级排序算法之快速排序(高效排序)
ztj100 2025-05-02 22:43 5 浏览 0 评论
前言
今天继续算法学习,本次学习的是高级排序之快速排序。本文代码部分存在调用公共方法,可在文章:简单排序算法之冒泡、插入和选择排序-Java实现版 ,高级排序之归并排序、希尔排序。中查找相关方法,另外,本文也提供测试时使用的完整代码,对其他算法不感兴趣,可在文末找到完整源代码。
快速排序
快速排序的本质就是把一个数组划分为两个子数组,然后递归地调用自身为每一个数组进行“快速排序”来实现的。这里就涉及一个问题:如何划分?
在快速排序中,为了划分数组,提出了“枢纽”这个词,它代表待排序序列中的一个数据项。快速排序利用枢纽将数组划分成两部分,一部分(枢纽左侧)是所有小于该枢纽表示的数据项,另一部分(枢纽右侧)则都大于该枢纽表示的数据项(注意,此时左右两侧的数据项是无序的),枢纽放置在左右两侧的中间,此时该枢纽已经处在排序的正确位置上了(枢纽是快速排序所排序的对象,实现“排序”的关键点就是调整枢纽的位置)。通过递归的这样划分,最终出现左侧只有一个数据项(该数据项既是左侧子数组又是枢纽),则结束左侧递归,开始划分右侧数组。。。以此类推。这里又产生了一个问题,如何选择枢纽?
选择枢纽的算法:最简单的选择枢纽算法就是每次递归都选择数组的最后一个数据项做为枢纽(或者选择最左侧的数据项作枢纽)。
代码演示(枢纽始终使用子数组的最右侧数据项)
private static int partitionIt(int left,int right,int pivot,int[] array){
int leftPtr = left-1;
int rightPtr = right;
while(true){
// 查找左侧子数组大于枢纽的位置
while(compare(array[++leftPtr],pivot)<0){
}
// 查询右侧子数组小于枢纽的位置
while(rightPtr>0&&compare(array[--rightPtr],pivot)>0){
}
if(leftPtr>=rightPtr){
break;
}
// 交换需要调整位置的两个数据项
swap(leftPtr,rightPtr,array);
}
// 将枢纽挪到两侧中间
swap(leftPtr,right,array);
return leftPtr;
}
private static void recQuickSort(int left,int right,int[] array){
if(right-left<=0){
return;
}
// 选择的枢纽
int pivot = array[right];
int partition = partitionIt(left,right,pivot,array);
recQuickSort(left,partition-1,array);
recQuickSort(partition+1,right,array);
}
public static void quickSort(int[] array){
compareCount=0;
swapCount=0;
long start = new Date().getTime();
recQuickSort(0,array.length-1,array);
long end = new Date().getTime();
printResult("快速排序","交换次数",start,end);
}
运行结果
冒泡排序——比较次数:49995000,交换次数:25153125,耗时:173毫秒
选择排序——比较次数:49995000,交换次数:9987,耗时:65毫秒
插入排序——比较次数:25075792,复制次数:25075793,耗时:42毫秒
归并排序——比较次数:120459,复制次数:267232,耗时:3毫秒
希尔排序——比较次数:233896,复制次数:238266,耗时:5毫秒
对随机序列排序:快速排序——比较次数:165181,交换次数:31700,耗时:3毫秒
对逆序序列排序:快速排序——比较次数:49825881,交换次数:9976,耗时:54毫秒
从运行结果中,可以看到对于随机序列,快速排序算法执行速度是非常快的,和归并排序相同,但给逆序序列排序时,效果则非常差,几乎和选择排序一样的效率了。那这是为什么呢?
根本原因,就在于枢纽的选择上,快速排序期望枢纽能够将数组拆分成两个长度几乎相同的子数组,这样能最优的平衡比较次数和交换次数。对于随机序列,简单的选择最右侧数据项做为枢纽不至于频繁出现左右子数组极度不平衡的情况,而对于逆序序列,则几乎每次划分都是极度不平衡的两个子数组,最终导致较大侧的子数组要被划分更多次。
优化枢纽选择算法
快速排序的最优划分结果是划分的两个数组长度相等,为了达到这个目的,我们每次都要在划分前,先找到子数组的中间数据项吗?显然,不能这么做的,因为很可能你找中值的时间远远大于你排序的时间了。所以,我们只能选择一个实现既不是过于复杂,又比“选择最右侧数据项做为枢纽”的算法更具普适性。
上图所示取枢纽的方法叫“三数据项取中”,即从数组中选择第一个、最后一个以及中间的数据项,从这三个数据项中取出大小在中间的项做为枢纽,在选择过程中,我们实际上也对这三个数据项做了排序,那顺便把分别大于、小于枢纽的那两个数据项也放到正确的位置(即左侧小于枢纽,右侧大于枢纽)。
该方法每次划分都需要至少有三个数据项,所以当子数组项数不大于3个的时候,就可以结束递归划分了,此时的排序可以通过其他排序算法实现,如使用手动排序(待排序的数据项不大于3个,所以手动排序完全可以轻松搞定),也可以使用插入排序(如果使用插入排序,我们甚至可以当数据项不大于10(这个10没有具体意义,你也可以20、30)的时候就可以用插入排序来收尾了)。下面我们用该方法来选择枢纽(用插入排序来收尾),对代码进行修改。
代码演示
private static int medianOf3(int left,int right,int[] array){
int center = (left+right)/2;
if(array[left]>array[center]){
swap(left,center,array);
}
if(array[left]>array[right]){
swap(left,right,array);
}
if(array[center]>array[right]){
swap(center,right,array);
}
swap(center,right-1,array);
return array[right-1];
}
private static void insertSort(int left,int right,int[] array){
for (int i = left+1; i <= right; i++) {
int temp = array[i];
int cur = i;
// 右移数字,实现cur下标的左侧都是有序的
while (cur > 0 && compare(temp, array[cur - 1]) < 0) {
copy(cur-1,cur,array);
cur--;
}
// 如果cur==i则说明数据项已经在正确的位置了,不需要进行交换
if (cur != i) {
// 不满足temp<array[cur-1]时,则当前正在排的项temp已经找到正确位置了
copyData(temp,cur,array);
}
}
}
private static int partitionIt(int left,int right,int pivot,int[] array){
int leftPtr = left;
int rightPtr = right-1;
while(true){
// 查找左侧子数组大于枢纽的位置
while(compare(array[++leftPtr],pivot)<0){
}
// 查询右侧子数组小于枢纽的位置
while(compare(array[--rightPtr],pivot)>0){
}
if(leftPtr>=rightPtr){
break;
}
// 交换需要调整位置的两个数据项
swap(leftPtr,rightPtr,array);
}
// 将枢纽挪到两侧中间
swap(leftPtr,right-1,array);
return leftPtr;
}
private static void recQuickSort(int left,int right,int[] array){
int size = right-left+1;
if(size <10){
insertSort(left,right,array);
}else{
int median = medianOf3(left,right,array);
int partition = partitionIt(left,right,median,array);
recQuickSort(left,partition-1,array);
recQuickSort(partition+1,right,array);
}
}
public static void quickSort(int[] array){
compareCount=0;
swapCount=0;
long start = new Date().getTime();
recQuickSort(0,array.length-1,array);
long end = new Date().getTime();
printResult("快速排序","交换次数",start,end);
}
运行结果
冒泡排序——比较次数:49995000,交换次数:25138570,耗时:170毫秒
选择排序——比较次数:49995000,交换次数:9990,耗时:65毫秒
插入排序——比较次数:25069178,复制次数:25069176,耗时:34毫秒
归并排序——比较次数:120483,复制次数:267232,耗时:2毫秒
希尔排序——比较次数:231598,复制次数:235991,耗时:6毫秒
对随机序列排序:快速排序——比较次数:154857,交换次数:44570,耗时:3毫秒
对逆序序列排序:快速排序——比较次数:188034,交换次数:20067,耗时:1毫秒
从执行结果可以看出,优化过枢纽选择算法后,无论是随机序列排序还是逆序序列排序,排序速度都非常快。
至此,本文结束
完整代码
package team.ngup.study;
import java.util.Arrays;
import java.util.Date;
import java.util.concurrent.ThreadLocalRandom;
/**
* @author zww
* @date 2022/8/4 10:35
*/
public class SortStudy {
static final int ARRAY_SIZE = 10000;
static int compareCount = 0;
static int swapCount = 0;
/**
* 生成随机数数组
*
* @return
*/
public static int[] buildRandomArray() {
int[] array = new int[ARRAY_SIZE];
for (int i = 0; i < ARRAY_SIZE; i++) {
int randomWithThreadLocalRandom = ThreadLocalRandom.current().nextInt(0, 1000000);
array[i] = randomWithThreadLocalRandom;
}
return array;
}
/**
* a和b位置的数据交换
*
* @param a
* @param b
* @param array
*/
public static void swap(int a, int b, int[] array) {
swapCount++;
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
/**
* 复制 位置 a->b
* @param a
* @param b
* @param array
*/
private static void copy(int a,int b,int[] array){
swapCount++;
array[b] = array[a];
}
/**
* 复制 数值a->位置b
* @param a
* @param b
* @param array
*/
private static void copyData(int a,int b,int[] array){
swapCount++;
array[b]=a;
}
/**
* dataa大于datab返回1,否则返回-1
*
* @param dataa
* @param datab
* @return
*/
public static int compare(int dataa, int datab) {
compareCount++;
if (dataa >= datab) {
return 1;
}
return -1;
}
/**
* 输出排序结果
*
* @param name 排序方法名
* @param operName 交换/复制
* @param start 开始时间
* @param end 结束时间
*/
private static void printResult(String name,String operName,long start,long end){
System.out.print(
name
+ "——比较次数:"
+ compareCount
+ ","+operName+":"
+ swapCount
+ ",耗时:"
+ (end - start)
+ "毫秒");
}
/** 冒泡排序 */
public static void maopao(int[] array) {
compareCount = 0;
swapCount = 0;
// 待排序序列长度,
int length = array.length;
long start = new Date().getTime();
while (length > 0) {
for (int a = 0; a < length - 1; a++) {
if (compare(array[a], array[a + 1]) > 0) {
// 交换位置
swap(a, a + 1, array);
}
}
// 一次从头到尾的遍历,找出了最右端的值(最大值),这将缩短第二次遍历的序列长度
length--;
}
long end = new Date().getTime();
// 输出排序结果
printResult("冒泡排序","交换次数", start, end);
}
/** 选择排序 */
public static void xuanze(int[] array) {
compareCount = 0;
swapCount = 0;
int length = 0;
long start = new Date().getTime();
while (length != array.length - 1) {
// 最小值位置
int minPosition = -1;
// 最小值
int min = array[length];
for (int i = length + 1; i < array.length; i++) {
if (compare(array[i], min) < 0) {
min = array[i];
minPosition = i;
}
}
// 存在比当前值还要小的值,则进行位置对换,否则无需对调位置
if (minPosition != -1) {
// 交换位置
swap(length, minPosition, array);
}
length++;
}
long end = new Date().getTime();
printResult("选择排序","交换次数", start, end);
}
/** 插入排序 */
public static void charu(int[] array) {
swapCount = 0;
compareCount = 0;
// 第一次排序无需比较,所以直接从1开始
long start = new Date().getTime();
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int cur = i;
// 右移数字,实现cur下标的左侧都是有序的
while (cur > 0 && compare(temp, array[cur - 1]) < 0) {
copy(cur-1,cur,array);
cur--;
}
// 如果cur==i则说明数据项已经在正确的位置了,不需要进行交换
if (cur != i) {
// 不满足temp<array[cur-1]时,则当前正在排的项temp已经找到正确位置了
copyData(temp,cur,array);
}
}
long end = new Date().getTime();
printResult("插入排序" ,"复制次数", start, end);
}
// ------------------高级排序------------------------
private static void merge(int[] array, int[] workSpace, int lowPtr, int highPtr, int upperBound) {
int j = 0;
int lowerBound = lowPtr;
int mid = highPtr - 1;
int n = upperBound - lowerBound + 1;
while (lowPtr <= mid && highPtr <= upperBound) {
if (compare(array[lowPtr],array[highPtr])<0) {
copyData(array[lowPtr++],j++,workSpace);
} else {
copyData(array[highPtr++],j++,workSpace);
}
}
while (lowPtr <= mid) {
copyData(array[lowPtr++],j++,workSpace);
}
while (highPtr <= upperBound) {
copyData(array[highPtr++],j++,workSpace);
}
for (j = 0; j < n; j++) {
copyData(workSpace[j],lowerBound+j,array);
}
}
private static void recMergeSort(int[] array,int[] workSpace, int lowerBound, int upperBound) {
if (lowerBound == upperBound) {
return;
}
int mid = (lowerBound + upperBound) / 2;
recMergeSort(array,workSpace, lowerBound, mid); // 分割左侧
recMergeSort(array,workSpace, mid + 1, upperBound); // 分割右侧
merge(array,workSpace,lowerBound,mid+1,upperBound); // 合并排序
}
/**
* 合并排序
* @param array
*/
public static void mergeSort(int[] array){
compareCount=0;
swapCount=0;
int[] workspace = new int[array.length];
long start = new Date().getTime();
recMergeSort(array,workspace,0,array.length-1);
long end = new Date().getTime();
printResult("归并排序","复制次数",start,end);
}
/**
* 希尔排序
* @param array
*/
public static void xierSort(int[] array){
compareCount=0;
swapCount=0;
int inner,outer;
int temp;
int h=1;
// 计算跨度
while(h<=array.length/3){
h=h*3+1;
}
long start = new Date().getTime();
while(h>0){
for(outer=h;outer<array.length;outer++){
temp = array[outer];
inner = outer;
while(inner>h-1 && compare(array[inner-h],temp)>0){
copy(inner-h,inner,array);
inner -= h;
}
copyData(temp,inner,array);
}
h=(h-1)/3;
}
long end = new Date().getTime();
printResult("希尔排序","复制次数",start,end);
}
//-------------快速排序---------------------//
private static int medianOf3(int left,int right,int[] array){
int center = (left+right)/2;
if(compare(array[left],array[center])>0){
swap(left,center,array);
}
if(compare(array[left],array[right])>0){
swap(left,right,array);
}
if(compare(array[center],array[right])>0){
swap(center,right,array);
}
swap(center,right-1,array);
return array[right-1];
}
private static void insertSort(int left,int right,int[] array){
for (int i = left+1; i <= right; i++) {
int temp = array[i];
int cur = i;
// 右移数字,实现cur下标的左侧都是有序的
while (cur > 0 && compare(temp, array[cur - 1]) < 0) {
copy(cur-1,cur,array);
cur--;
}
// 如果cur==i则说明数据项已经在正确的位置了,不需要进行交换
if (cur != i) {
// 不满足temp<array[cur-1]时,则当前正在排的项temp已经找到正确位置了
copyData(temp,cur,array);
}
}
}
private static int partitionIt(int left,int right,int pivot,int[] array){
int leftPtr = left;
int rightPtr = right-1;
while(true){
// 查找左侧子数组大于枢纽的位置
while(compare(array[++leftPtr],pivot)<0){
}
// 查询右侧子数组小于枢纽的位置
while(compare(array[--rightPtr],pivot)>0){
}
if(leftPtr>=rightPtr){
break;
}
// 交换需要调整位置的两个数据项
swap(leftPtr,rightPtr,array);
}
// 将枢纽挪到两侧中间
swap(leftPtr,right-1,array);
return leftPtr;
}
private static void recQuickSort(int left,int right,int[] array){
int size = right-left+1;
if(size <10){
insertSort(left,right,array);
}else{
int median = medianOf3(left,right,array);
int partition = partitionIt(left,right,median,array);
recQuickSort(left,partition-1,array);
recQuickSort(partition+1,right,array);
}
}
public static void quickSort(int[] array){
compareCount=0;
swapCount=0;
long start = new Date().getTime();
recQuickSort(0,array.length-1,array);
long end = new Date().getTime();
printResult("快速排序","交换次数",start,end);
}
public static void main(String[] args) {
int[] array = buildRandomArray();
int[] array2 = Arrays.copyOf(array, ARRAY_SIZE);
int[] array3 = Arrays.copyOf(array, ARRAY_SIZE);
int[] array4 = Arrays.copyOf(array,ARRAY_SIZE);
int[] array5 = Arrays.copyOf(array,ARRAY_SIZE);
int[] array6 = Arrays.copyOf(array,ARRAY_SIZE);
maopao(array);
System.out.println();
xuanze(array2);
System.out.println();
charu(array3);
System.out.println();
mergeSort(array4);
System.out.println();
xierSort(array5);
System.out.println();
// 随机数据项 进行快速排序
System.out.print("对随机序列排序:");
quickSort(array6);
System.out.println();
// 将array6逆序
int[] array6a = new int[array6.length];
for(int i=array6.length-1,j=0;i>=0;i--){
array6a[j] = array6[i];
j++;
}
// 对逆序的数组使用快速排序
System.out.print("对逆序序列排序:");
quickSort(array6a);
}
}
原文格式更佳:高级排序算法之快速排序|NGUP的个人技术博客
相关推荐
- Java 8 新特性全面解读:解锁现代编程的魅力
-
Java8新特性全面解读:解锁现代编程的魅力Java8作为Java语言发展史上里程碑式的版本,不仅带来了诸多新特性,更深刻地改变了我们编写代码的方式。无论是简洁的Lambda表达式,还是强大的S...
- 教程:克隆公司饭卡 然后优雅地“蹭饭”
-
最近借了Proxmark3来娱乐性的玩下RFID技术,工资甚低的我只好拿公司饭卡实验,优雅地蹭几顿。物业大叔表打我啊!以下操作纯属学习目的,初学难免错误较多,望斧正。首先了解M1卡的结构:请参考htt...
- 新课标高中教材1030个短语大汇总(高中新课标英语词汇)
-
1.anamountof+不可数名词许多...
- 看完这篇文章你就懂 AQS 了(赛科龙aqs401参数详情)
-
前言谈到并发,我们不得不说AQS(AbstractQueuedSynchronizer),所谓的AQS即是抽象的队列式的同步器,内部定义了很多锁相关的方法,我们熟知的ReentrantLock、Ree...
- Java 8新特性全面解析:开启现代化编程之旅
-
Java8新特性全面解析:开启现代化编程之旅Java8作为Java语言发展历程中的重要里程碑,在2014年正式发布。它的到来标志着Java从传统面向对象编程向支持函数式编程迈进的重要一步。在这一版...
- Java 8新特性全面剖析:让代码更优雅、更高效
-
Java8新特性全面剖析:让代码更优雅、更高效Java8,作为Java语言发展史上的一座里程碑,带来了众多令人振奋的新特性。这些新特性不仅极大地提升了开发效率,还让代码变得更优雅、更简洁。今天,我...
- 线程安全编程方法总结(线程安全编程方法总结)
-
保护线程安全是多线程编程中的核心问题,关键在于控制共享资源的访问并协调线程间的执行顺序。以下是常用的基本方法及其适用场景:1.互斥锁(MutexLocks)机制:通过锁(如synchronize...
- 考勤数据标准化处理(考勤标准化管理制度)
-
经常做考勤的同学有没有遇到过这样的考勤数据呢?没错,从考勤机里导出来的,要统计那叫一个麻烦啊(有同学说可以导出txt文件,然后再处理会省事很多,有条件的小伙伴可以自己研究研究)看这表格数据其实挺规范的...
- SQL语句大全,所有的SQL都在这里(sql语句百度百科)
-
一、基础1、说明:创建数据库CREATEDATABASEdatabase-name2、说明:删除数据库dropdatabasedbname3、说明:备份sqlserver---创建备份数...
- 手搓Agno智能体使用Ollama模型(ollama本地智能体)
-
轻量化智能体开源框架Agno有兴趣了解WhatisAgno-Agno安装python3.12...
- 高级排序算法之快速排序(高效排序)
-
前言今天继续算法学习,本次学习的是高级排序之快速排序。本文代码部分存在调用公共方法,可在文章:...
- Linux cmp 命令使用详解(linux常用命令cp)
-
简介Linux中的...
- N张图告诉你K-DB为什么能全面兼容Oracle?
-
不是每一款数据库都能全面兼容Oracle,就像不是所有数据库都可以被称之为K-DB。一般数据库能做到的SQL标准和函数上兼容Oracle,而K-DB则能实现更多,在数据库体系架构、集群方式、数据库对象...
- 12. Langchain评估与调试:用LangSmith优化模型表现
-
引言:从"感觉不错"到"数据说话"2025年某电商平台通过LangSmith系统化的评估优化,将客服机器人的问题解决率从68%提升至92%。本文将详解如何用...
- 那些有用但不为大家所熟知的 Java 特性
-
本文最初发表于PiotrMińkowski的个人站点Medium网站,经作者授权,由InfoQ中文站翻译分享。...
你 发表评论:
欢迎- 一周热门
- 最近发表
- 标签列表
-
- idea eval reset (50)
- vue dispatch (70)
- update canceled (42)
- order by asc (53)
- spring gateway (67)
- 简单代码编程 贪吃蛇 (40)
- transforms.resize (33)
- redisson trylock (35)
- 卸载node (35)
- np.reshape (33)
- torch.arange (34)
- node卸载 (33)
- npm 源 (35)
- vue3 deep (35)
- win10 ssh (35)
- exceptionininitializererror (33)
- vue foreach (34)
- idea设置编码为utf8 (35)
- vue 数组添加元素 (34)
- std find (34)
- tablefield注解用途 (35)
- python str转json (34)
- java websocket客户端 (34)
- tensor.view (34)
- java jackson (34)