java中简单的快速排序_【新手自白书】简单快速排序的实现（JAVA）

今天药忘吃喽~ 2022-11-08 11:48 108阅读 0赞

复习一下快速排序

快速排序(Quicksort)是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。(来自百度百科)

冒泡排序传送门

快速排序的思路大概可以这样理解：

有两个人，L和R分别站在数据data的两端，这两个人规定了一个值K，只要R头顶的值不小于K，R就走一步，直到走到一个值比K小，L恰恰相反，L头顶的值如果不大于K，L就走一步，直到走到一个值比K大。当两个人都停下的时候，就交换头顶的值，如果两个人相遇在一个地方，就把相遇的那个值和K交换，然后两个人停止前行。

![AAffA0nNPuCLAAAAAElFTkSuQmCC][]

这样操作后，LR相遇点之前的值一定小于K，LR相遇点之后的值一定大于K，可以自行手动验证(\#滑稽)。

之后我们可以以相遇点为分界，得到两个子表，这两个子表分别以这种方式进行操作，就可以把无序列变为有序列。本质上是递归。

需要注意的是，我们进行操作的时候必须按照先R后L的顺序才可以正确的递归，而K值一般取data\[0\]。

在方法设计上，要注意如何递归，我们给LR相遇点的下标取名mid，表总长length，左子表的下标值在0~mid-1,右子表的下标值在mid+1~length-1。所以我们每次递归都要返回mid值，才能正确的递归。

public int getMid(int\[\] list,int left,int right)\{

right = right - 1 ;

int key = list\[left\] ;

while(left < right)\{

while(left < right && list\[right\] > key)\{

right -- ;

while(left < right && list\[left\] < key)\{

left ++ ;

//mid = left ;

int temp = list\[left\] ;

list\[left\] = list\[right\] ;

list\[right\] = temp ;

int temp = list\[left\] ;

list\[left\] = key ;

key = temp ;

return left ;

每次获取mid的方法完成。

递归方法很简单，只需要在一个方法里调用获取mid的方法即可。

public void sort(int\[\] list,int left,int right)\{

int mid = 0 ;

if(left < right)\{

mid = this.getMid(list,left,right) ;

this.sort(list, 0, mid-1) ;

this.sort(list, mid+1, right) ;

总体类设计如下：

public class QSort\{

private int\[\] data = null ;

//private int\[\] array = null ;

public QSort(int\[\] data,int left,int right)\{

this.setData(data) ;

this.sort(data, left, right) ;

private void setData(int\[\] data)\{

this.data = data ;

public String getArray()\{

String s = "排序后：" ;

for(int i : this.data)\{

s = s + i + " " ;

return s ;

public void sort(int\[\] list,int left,int right)\{

int mid = 0 ;

if(left < right)\{

mid = this.getMid(list,left,right) ;

this.sort(list, 0, mid-1) ;

this.sort(list, mid+1, right) ;

public int getMid(int\[\] list,int left,int right)\{

right = right - 1 ;

int key = list\[left\] ;

while(left < right)\{

while(left < right && list\[right\] > key)\{

right -- ;

while(left < right && list\[left\] < key)\{

left ++ ;

//mid = left ;

int temp = list\[left\] ;

list\[left\] = list\[right\] ;

list\[right\] = temp ;

int temp = list\[left\] ;

list\[left\] = key ;

key = temp ;

return left ;

测试

public class Test \{

public static void main(String\[\] args) \{

System.out.println(new QSort(new int\[\]\{7,1,4,2,9,3,8,5,10,6\},0,10)

.getArray());

结果

排序后：1 2 3 4 5 6 7 8 9 10

[AAffA0nNPuCLAAAAAElFTkSuQmCC]:

java中简单的快速排序_【新手自白书】简单快速排序的实现（JAVA）

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关快速排序（Java）新手导入

相关 java中简单的快速排序_【新手自白书】简单快速排序的实现（JAVA）

相关快速排序的java_快速排序的Java实现

相关 [排序算法]--快速排序的Java实现

相关快速排序的简单实现

相关 C++快速排序的简单实现

相关快速排序--Java简单实现

相关快速排序的java实现

相关最简单的快速排序

相关 JAVA-最简单的快速排序