快速排序的深入详解以及java实现
2023-06-13 09:15:02 时间
快排采用了经典的分治思想(divideandconquer):
Divide:选取一个基元X(一般选取数组第一个元素),通过某种分区操作(partitioning)将数组划分为两个部分:左半部分小于等于X,右半部分大于等于X。
Conquer:左右两个子数组递归地调用Divide过程。
Combine:快排作为就地排序算法(inplacesort),不需要任何合并操作
可以看出快排的核心部分就是划分过程(partitioning),下面以一个实例来详细解释如何划分数组(图取自于《算法导论》)
初始化:选取基元P=2,就是数组首元素。i=1,j=i+1=2(数组下标以1开头)
循环不变量:2~i之间的元素都小于或等于P,i+1~j之间的元素都大于或等于P
循环过程:j从2到n,考察j位置的元素,如果大于等于P,就继续循环。如果小于P,就将j位置的元素(不应该出现在i+1~j这个区间)和i+1位置(交换之后仍在i+1~j区间)的元素交换位置,同时将i+1.这样就维持了循环不变量(见上述循环不变量说明)。直到j=n,完成最后一次循环操作。
要注意的是在完成循环后,还需要将i位置的元素和数组首元素交换以满足我们最先设定的要求(对应图中的第i步)。
细心的读者可能会想到另一种更直白的分区方法,即将基元取出存在另一相同大小数组中,遇到比基元小的元素就存储在数组左半部分,遇到比基元大的元素就存储在数组右半部分。这样的操作复杂度也是线性的,即Theta(n)。但是空间复杂度提高了一倍。这也是快排就地排序的优势所在。
publicclassQuickSort{
privatestaticvoidQuickSort(int[]array,intstart,intend)
{
if(start<end)
{
intkey=array[start];//初始化保存基元
inti=start,j;//初始化i,j
for(j=start+1;j<=end;j++)
if(array[j]<key)//如果此处元素小于基元,则把此元素和i+1处元素交换,并将i加1,如大于或等于基元则继续循环
{
inttemp=array[j];
array[j]=array[i+1];
array[i+1]=temp;
i++;
}
}
array[start]=array[i];//交换i处元素和基元
array[i]=key;
QuickSort(array,start,i-1);//递归调用
QuickSort(array,i+1,end);
}
}
publicstaticvoidmain(String[]args)
{
int[]array=newint[]{11,213,134,44,77,78,23,43};
QuickSort(array,0,array.length-1);
for(inti=0;i<array.length;i++)
{
System.out.println((i+1)+"th:"+array[i]);
}
}
}
相关文章
- JAVA多线程面试题_java多线程的实现方式
- java 调用.asmx_Java调用asmx的一个例子
- java 登录 qq_Java实现QQ登录
- java启动器_JAVA基础:Java 启动器如何查找类
- java redis锁_Java中Redis锁的实现[通俗易懂]
- 八大排序算法(java实现) 冒泡排序 快速排序 堆排序 归并排序 等[通俗易懂]
- java arraydeque poll,Java ArrayDeque「建议收藏」
- 用递归实现数组求和的函数_JAVA数组递归排序
- JAVA外文参考文献_java参考文献近五年
- 从java到JavaScript(2):对比Java/Go/Swift/Rust看Dart
- Java Activiti6.0 spring5 SSM 工作流引擎 审批流程 java项目框架详解编程语言
- 希尔排序 java 实现详解编程语言
- Java封装MySQL让编程更简单(java封装mysql)
- Linux下Java编程之旅(linux执行java)
- 实现Java实现Redis集合的技术研究(redis集合java)
- MySQL与Java的结合:实现强大的数据持久化功能(mysql与java)
- 实现Java实现的Redis封装类:强化Redis技术支持(redis封装类java)
- Java操作Redis实现数据快速存取(java访问redis)
- Java程序如何在Linux上顺利部署?快来了解一下!(java部署到Linux)
- Linux下Java命令的使用方法简介(linux下java命令)
- Linux Java时区调整:让处理日期更加方便(linux java时区)
- Java编程实现MySQL数据库连接(java连mysql数据库)
- Java程序在Linux系统中实现命令操作(java运行linux命令)
- Java数据库之MySQL学习使用教程(mysql中java教程)
- 构建基于Java和Oracle的强大技术栈(java架构oracle)
- Java程序建立Oracle数据库表的实现方式(java建oracle表)
- Java存入Oracle数据库实现快速高效的数据存储(java存入oracle)
- Java使用Oracle实现优雅数据查询(java.oracle)
- Oracle中实现Java程序设计的极限可能性(oracle中的java)
- 实现基于Redis的分布式锁Java实现(redis锁java代码)
- JAVA实现单例模式的四种方法和一些特点
- java操作mongodb基础(查询排序输出list)