快速排序算法原理與實作

快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一不部分的所有資料都要小，然後再按次方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。

    假設要排序的數組是A[1]……A[N]，首先任意選取一個資料（通常選用第一個資料）作為關鍵資料，然後将所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一躺快速排序的算法是：

   1）、設定兩個變量I、J，排序開始的時候I：=1，J：=N；

   2）以第一個數組元素作為關鍵資料，指派給X，即X：=A[1]；

   3）、從J開始向前搜尋，即由後開始向前搜尋（J：=J-1），找到第一個小于X的值，兩者交換；

   4）、從I開始向後搜尋，即由前開始向後搜尋（I：=I+1），找到第一個大于X的值，兩者交換；

   5）、重複第3、4步，直到I=J；

   例如：待排序的數組A的值分别是：（初始關鍵資料X：=49）

                   A[1]     A[2]     A[3]     A[4]     A[5]      A[6]     A[7]：

                     49        38       65       97       76       13        27

進行第一次交換後：   27        38       65       97       76       13        49

                   ( 按照算法的第三步從後面開始找

進行第二次交換後：   27        38       49       97       76       13        65

                  ( 按照算法的第四步從前面開始找>X的值，65>49,兩者交換，此時I：=3 )

進行第三次交換後：   27        38       13       97       76       49        65

( 按照算法的第五步将又一次執行算法的第三步從後開始找

進行第四次交換後：   27        38       13       49       76       97        65

( 按照算法的第四步從前面開始找大于X的值，97>49,兩者交換，此時J：=4 )

      此時再執行第三不的時候就發現I=J，進而結束一躺快速排序，那麼經過一躺快速排序之後的結果是：27        38       13       49       76       97        65，即是以大于49的數全部在49的後面，是以小于49的數全部在49的前面。

      快速排序就是遞歸調用此過程——在以49為中點分割這個資料序列，分别對前面一部分和後面一部分進行類似的快速排序，進而完成全部資料序列的快速排序，最後把此資料序列變成一個有序的序列，根據這種思想對于上述數組A的快速排序的全過程如圖6所示：

初始狀态                        {49     38     65     97     76     13     27}   

進行一次快速排序之後劃分為      {27     38     13}     49   {76     97     65}

分别對前後兩部分進行快速排序    {13}    27    {38}

                                結束         結束    {49    65}    76    {97}

                                                    49   {65}         結束

                                                        結束

                          圖6    快速排序全過程

java實作快速排序算法

package com.huxin.javatest.quicksort.test;

public class Test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Integer[] integer = {8,12,6,9,11,16,78,2};
		Test.quick(integer);
		for(int i : integer){
			System.out.print(i+" ");
		}

	}
	//8 12 6 9 11
    public static int getMiddle(Integer[] integer,int low ,int high){
    	//取第一個數為中值
       int temp = integer[low];
       while(low < high){
	    	while(low < high && temp < integer[high]){
	    		high --;
	    	}
	    	//将比中值大的數移到最左邊
	    	integer[low] = integer[high];
	    	integer[high] = temp ;
	    	while(low < high && temp > integer[low]){
	    		low ++;
	    	}
	    	integer[high] = integer[low];
	    	integer[low] = temp;
       }
    	return low;
    }
    
    public static void quick(Integer[] integer){
    	if(integer.length > 0){
    		quickSort(integer,0,integer.length-1);
    	}
    }
    
    public static void quickSort(Integer[] integer,int low ,int high){
    	if(low < high){
	    	int middle = getMiddle(integer,low,high);
	    	quickSort(integer,low,middle-1);
	    	quickSort(integer,middle+1,high);
    	}
    }
}