天天看點

快速排序算法原理與實作

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

    假設要排序的數組是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);
    	}
    }
}
           

繼續閱讀