快速排序的java实现

Dear 丶 2022-03-14 16:34 199阅读 0赞

快排是分治法的一个应用，快排主要是通过一个设定枢轴，然后以这个枢轴为标杆，将待排序列按大小分成比枢轴大的，和比枢轴小的两部分。然后在对划分完的子序列进行快排，知道子序列中元素的个数为1位置。

### 快速排序实现 ###

快排是程序员必须掌握的，举一个例子来解释，如下图：

![db35e3d7-d3f1-3e4b-bc7f-656b861d748a.jpg][]

首先选定枢轴，一般设置low所对应的元素位置为枢轴，如图选定的枢轴为26。

在高位指针始终不小于低位指针的前提下：

高位指针开始判断其是否比枢轴值大，如果符合，高位指针减1，继续寻找，直到找到不符合的情况，然后把该值赋给此时低位所在位置。

低位指针开始判断其是否比枢轴值小，如果符合，低位指针加1，继续寻找，直到找到不符合情况，然后将该值赋给此时高位指针所指位置。

如此反复，知道低位与高位指针重合，此时，在讲当前的枢轴值赋给低位指针所指的值。这样就完成了一次排序。

此时枢轴值就到了其最终位置上，然后继续对以枢轴为轴的两部分进行排序。

### JAVA实现快速排序 ###

Java代码 [![复制代码][icon_copy.gif]][icon_copy.gif 1]  ![收藏代码][icon_star.png]![spinner.gif][]

1.  package cn.edu.heut.zcl;   
2.      
3.  public class QuickSort \{   
4.             
5.           /\*\*  
6.            \* 快速排序，对整数型数组o进行  
7.            \* @param o  
8.            \* @param low  
9.            \* @param hight  
10.           \*/  
11.          public static void quiteSort( int\[\] o , int low , int hight )\{   
12.                    if(low < hight)\{   
13.                             int povitePosition = adjust(o,low,hight);   
14.                             quiteSort( o , low , povitePosition - 1);   
15.                             quiteSort( o , povitePosition + 1 , hight );   
16.                    \}   
17.          \}   
18.          /\*\*  
19.           \* 进行调整  
20.           \* @param o  
21.           \* @param low  
22.           \* @param hight  
23.           \* @return  
24.           \*/  
25.          private static int adjust( int\[\] o , int low , int hight )\{//选定枢轴为low所对应的值   
26.                    int pivote = o\[low\];   
27.                    while(low < hight)\{   
28.                             while(hight > low && compare( pivote , o\[hight\] ) <= 0 )\{// 高位找到比povite大，则符合要求，继续寻找   
29.                                      hight -- ;   
30.                             \}   
31.                             o\[low\] = o\[hight\] ;   
32.                             while(low < hight && compare( pivote , o\[low\] ) >= 0)\{ //低位开始找到比povite小，符合要求，继续寻找   
33.                                      low ++ ;   
34.                             \}   
35.                             o\[hight\] = o\[low\];   
36.                    \}   
37.                    o\[low\] = pivote ;   
38.                    return low;   
39.          \}   
40.            
41.          /\*\*  
42.           \*  
43.           \* @param num1 减数  
44.           \* @param num2 被减数  
45.           \* @return  
46.           \*/  
47.          private static int compare(int num1, int num2) \{   
48.                    return num1 - num2 ;   
49.          \}   
50.          /\*\*  
51.           \* @param args  
52.           \*/  
53.          public static void main(String\[\] args) \{   
54.                    int\[\] i = \{ 26,53,48,15,13,46,32,15\};   
55.                    quiteSort(i, 0, i.length-1);   
56.                    for(int ii:i)\{   
57.                             System.out.print(ii+" ");   
58.                    \}   
59.          \}   
60. \}

[db35e3d7-d3f1-3e4b-bc7f-656b861d748a.jpg]: /images/20220312/fddf13af11cd476588eed2eb794d988a.png
[icon_copy.gif]: http://158067568.iteye.com/images/icon_copy.gif
[icon_copy.gif 1]: http://158067568.iteye.com/blog/914049#
[icon_star.png]: http://158067568.iteye.com/images/icon_star.png
[spinner.gif]: /images/20220312/99fc594a49c64d71884de10d3f92afd0.png