八大排序算法之快速排序（二）

朱雀 2022-05-15 08:46 171阅读 0赞

public static void kuaisu(int arr[],int low,int high) {
    if(high>low) {
    	int i=low;
    	int j=high;
    	
    	int x=arr[i];
    	while(j>i && arr[j]>=x) {
    		j--;
    	}
    	if(j>i) {
    		arr[i++]=arr[j];
    	
    	}
    	while(j>i && arr[i]<x) {
    		i++;
    	}
    	if(j>i) {
    		arr[j--]=arr[i];
    	
    	}
    	arr[i]=x;
    	kuaisu(arr,i+1,high);
    	kuaisu(arr,low,i-1);
    }
    	
    	
    }
    public static void main(String[] args) {
    	// TODO Auto-generated method stub
    	int arr1[]=new int[] {2,3,46,78,96,53,76,32,67,9,7,4,54,37,19,10};
    	int arr3[]={6,5,4,3,2,1,0};
    	int arr2[]={2,3,46,78,96,53,76,32,67,9,7,4,54,37,19,10};
    	kuaisu(arr3, 0, arr3.length-1);
    for(int s:arr3) {
    System.out.print(s+",");
    }
    }

快速排序的基本思想是

> 1、先从数列中取出一个数作为基准数
> 
> 2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
> 
> 3、再对左右区间重复第二步，直到各区间只有一个数

概括来说为 **挖坑填数**\+**分治法**

下面举例来进行说明，主要有三个参数，i为区间的开始地址，j为区间的结束地址，X为当前的开始的值

第一步，i=0,j=9,X=21

<table> 
 <thead> 
  <tr> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
   <th>9</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong>21</strong></td> 
   <td>32</td> 
   <td>43</td> 
   <td>98</td> 
   <td>54</td> 
   <td>45</td> 
   <td>23</td> 
   <td>4</td> 
   <td>66</td> 
   <td>86</td> 
  </tr> 
 </tbody> 
</table>

第二步，从j开始由，后向前找，找到比X小的第一个数a\[7\]=4,此时i=0,j=6,X=21  
进行替换

<table> 
 <thead> 
  <tr> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
   <th>9</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>4</td> 
   <td>32</td> 
   <td>43</td> 
   <td>98</td> 
   <td>54</td> 
   <td>45</td> 
   <td>23</td> 
   <td><strong>21</strong></td> 
   <td>66</td> 
   <td>86</td> 
  </tr> 
 </tbody> 
</table>

第三步，由前往后找，找到比X大的第一个数a\[1\]=32,此时i=2,j=6,X=21

<table> 
 <thead> 
  <tr> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
   <th>9</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>4</td> 
   <td><strong>21</strong></td> 
   <td>43</td> 
   <td>98</td> 
   <td>54</td> 
   <td>45</td> 
   <td>23</td> 
   <td>32</td> 
   <td>66</td> 
   <td>86</td> 
  </tr> 
 </tbody> 
</table>

第四步，从j=6开始由，由后向前找，找到比X小的第一个数a\[0\]=4,此时i=2,j=0,X=21，发现j<=i,所以第一回结束

可以发现**21**前面的数字都比21小，后面的数字都比21大  
接下来对两个子区间\[0,0\]和\[2,9\]重复上面的操作即可

下面直接给出过程，就步详细解说了

i=2,j=6,X=43

<table> 
 <thead> 
  <tr> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
   <th>9</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>4</td> 
   <td>21</td> 
   <td><strong>43</strong></td> 
   <td>98</td> 
   <td>54</td> 
   <td>45</td> 
   <td>23</td> 
   <td><strong>32</strong></td> 
   <td>66</td> 
   <td>86</td> 
  </tr> 
 </tbody> 
</table>

i=4,j=6,X=43

<table> 
 <thead> 
  <tr> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
   <th>9</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>4</td> 
   <td>21</td> 
   <td>32</td> 
   <td><strong>98</strong></td> 
   <td>54</td> 
   <td>45</td> 
   <td>23</td> 
   <td><strong>43</strong></td> 
   <td>66</td> 
   <td>86</td> 
  </tr> 
 </tbody> 
</table>

i=4,j=5,x=43

<table> 
 <thead> 
  <tr> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
   <th>9</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>4</td> 
   <td>21</td> 
   <td>32</td> 
   <td><strong>43</strong></td> 
   <td>54</td> 
   <td>45</td> 
   <td><strong>23</strong></td> 
   <td>98</td> 
   <td>66</td> 
   <td>86</td> 
  </tr> 
 </tbody> 
</table>

i=5,j=5,x=43

<table> 
 <thead> 
  <tr> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
   <th>9</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>4</td> 
   <td>21</td> 
   <td>32</td> 
   <td>23</td> 
   <td><strong>43</strong></td> 
   <td>45</td> 
   <td>54</td> 
   <td>98</td> 
   <td>66</td> 
   <td>86</td> 
  </tr> 
 </tbody> 
</table>

然后被分为了两个子区间\[2,3\]和\[5,9\]

….最后排序下去就是最终的答案

<table> 
 <thead> 
  <tr> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
   <th>9</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>4</td> 
   <td>21</td> 
   <td>23</td> 
   <td>32</td> 
   <td>43</td> 
   <td>45</td> 
   <td>54</td> 
   <td>66</td> 
   <td>86</td> 
   <td>98</td> 
  </tr> 
 </tbody> 
</table>

**总结：**

> 1．i =L; j = R; 将基准数挖出形成第一个坑a\[i\]。
> 
> 2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a\[i\]中。
> 
> 3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a\[j\]中。
> 
> 4．再重复执行2，3二步，直到i==j，将基准数填入a\[i\]中。

快速排序：平均时间复杂度log2(n)\*n，所有内部排序方法中最高好的，大多数情况下总是最好的。

快速排序是不稳定的。

稳定性简单来说就是：

如果A i == A j，Ai 原来在 Aj 位置前，排序后 Ai 仍然是在 Aj 位置前，这样就是稳定的。

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

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

相关阅读

相关十大排序算法之快速排序

题：对a\[\]=\{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48\}排序要求从小到大排列。介绍：快速排序是改...

阳光穿透心脏的1/2处/ 2024年04月18日 16:27/ 0 赞/ 69 阅读

相关八大排序算法-快速排序

快速排序算法的定义是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排

ゝ一世哀愁。/ 2022年06月07日 10:55/ 0 赞/ 193 阅读

相关八大排序算法之堆排序

例如数组 a=\{19,3,60,7,1,15,33,24,45,32,79,85\}; 排序思想： 1，堆排序也是选择排序的一种，根据堆得特性，每次把最大或最小值（本次以

待我称王封你为后i/ 2022年05月30日 02:38/ 0 赞/ 174 阅读

相关八大排序（三）：快速排序

源码地址： [https://github.com/TimePickerWang/aimed-at-offer/blob/master/java%E6%BA%90%E7%A

布满荆棘的人生/ 2022年05月25日 03:34/ 0 赞/ 175 阅读

相关八大排序算法之基数排序

一、简单介绍 1、基数排序也就是桶排序，属于分配式排序。 2、特点：按照分配、按序回收(分配到不同的位置上,然后回收...)，不断分配....不断按序回收，直到有序为止。

素颜马尾好姑娘i/ 2022年05月20日 08:06/ 0 赞/ 257 阅读

相关八大排序算法——快速排序

package com.wjw; / @author wjw 快速排序的思想：通过一趟排序将要排序的数据分割成独立

向右看齐/ 2022年05月16日 09:07/ 0 赞/ 202 阅读

相关八大排序算法之快速排序（二）

public static void kuaisu(int arr[],int low,int high) { if(high>low) { int

朱雀/ 2022年05月15日 08:46/ 0 赞/ 172 阅读

相关八大排序之交换排序—快速排序

快速排序快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。 `基本思想`：选取一个记录作为枢轴，经过一趟

落日映苍穹つ/ 2022年05月13日 04:44/ 0 赞/ 203 阅读

相关八大排序之快速排序

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分

﹏ヽ暗。殇╰゛Y/ 2022年04月22日 06:16/ 0 赞/ 196 阅读

相关排序算法—八大排序

八大排序算法 1.冒泡排序冒泡排序是一种交换排序, 就是两两比较待排序的元素, 若次序不满足要求则交换, 知道整个数组有序基本思想 : 每次找到最大或最小值,

系统管理员/ 2021年11月08日 21:32/ 0 赞/ 439 阅读