快速排序算法的java实现

快速排序思想：

    一趟快速排序是：

1，随机产生一数列，选取第一个数（这里也可选其他的数）作为比较的基石，假设这个数为X,这样X=A[0]；设两个变量i=0，j=n-1；n是这个数列的长度

2，从前面开始找，找到第一个比A[0]大的数，找到了就与X交换

3，从后面开始找，找到第一个比A[0]小的数，找到了就与X交换

4，重复步骤2，3，直到i=j；

这样一趟快速排序就完成了；第一趟完成之后，X左边的数就全部小于X了，X右边的数九全部大于X，然后采用递归方式对X左边的数和X右边的数进行快速排序。

java实现代码如下：

Java代码

 

1. public class QSort {   
2.    /**  
3.       * @param pData 需要排序的数组  
4.       * @param left  左边的位置,初始值为0  
5.       * @param right 右边的位置,初始值为数组长度  
6.       */   
7.      public static void QuickSort(int[] pData,int left,int right)   
8.      {   
9.        int i,j;   
10.        int first,temp;   
11.        i = left;   
12.        j = right;   
13.        first = pData[left]; //这里选其他的数也行，不过一般选第一个  
14.        //一趟快速排序   
15.        while(true)   
16.        {   
17.        //从第二个数开始找大于中枢的数 ,从前面开始找大于pData[left]的数  
18.            while((++i)<right-1 && pData[i]<first);   
19.            //从最后一个数开始找第一个小于中枢pData[left]的数   
20.            while((--j)>left && pData[j]>first);   
21.            if(i>=j)   
22.                break;   
23.            //交换两边找到的数   
24.            temp = pData[i];   
25.            pData[i] = pData[j];   
26.            pData[j] = temp;   
27.     
28.        }   
29.        //交换中枢   
30.        pData[left] = pData[j];   
31.        pData[j] = first;   
32.        //递归快排中枢左边的数据   
33.        if(left<j)   
34.          QuickSort(pData,left,j);   
35.        //递归快排中枢右边的数据   
36.        if(right>i)   
37.          QuickSort(pData,i,right);   
38.      }   
39.     
40.      public static void main(String[] args){   
41.       
42.         int [] pData = new int[5];   
43.         for(int i = 0; i< 5; i++)   
44.              pData[i] = (int)(Math.random()*100);//Produce 10 random integers   
45.           
46.          for(int i = 0; i<pData.length; i++){   
47.              System.out.print(pData[i]+" ");    
48.          }  
49.          QSort.QuickSort(pData, 0, pData.length);   
50.           
51.          System.out.println("\n***********************");   
52.           
53.          for(int i = 0; i<pData.length; i++){   
54.              System.out.print(pData[i]+" ");   
55.          }  
56.      }    
57. }