C語言中文網 目錄
首頁 > Java教程 > Java數組處理 閱讀:1,249

Java數組排序:Java快速排序(Quicksort)法

快速排序(Quicksort)是對冒泡排序的一種改進。

快速排序的基本思想是:通過一趟排序,將要排序的數據分隔成獨立的兩部分,其中一部分的所有數據比另外一部分的所有數據都要小,然后再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此使整個數據變成有序序列。

具體做法是:假設要對某個數組進行排序,首先需要任意選取一個數據(通常選用第一個數據)作為關鍵數據,然后將所有比它小的數都放到它的前面,所有比它大的數都放到它的后面。這個過程稱為一趟快速排序;遞歸調用此過程,即可實現數據的快速排序。

例 1

利用快速排序法對一數組進行排序,實現步驟如下。

(1) 聲明靜態的 getMiddle() 方法,該方法需要返回一個 int 類型的參數值,在該方法中傳入 3 個參數。代碼如下:
public static int getMiddle(int[] list,int low,int high)
{
    int tmp=list[low];    //數組的第一個值作為中軸(分界點或關鍵數據)
    while(low<high)
    {
        while(low<high&&list[high]>tmp)
        {
            high--;
        }
        list[low]=list[high];    //比中軸小的記錄移到低端
        while(low<high&&list[low]<tmp)
        {
            low++;
        }
        list[high]=list[low];    //比中軸大的記錄移到高端
    }
    list[low]=tmp;    //中軸記錄到尾
    return low;    //返回中軸的位置
}

(2) 創建靜態的 unckSort() 方法,在該方法中判斷 low 參數是否小于 high 參數,如果是則調用 getMiddle() 方法,將數組一分為二,并且調用自身的方法進行遞歸排序。代碼如下:
public static void unckSort(int[] list,int low,int high)
{
    if(low<high)
    {
        int middle=getMiddle(list,low,high);    //將list數組一分為二
        unckSort(list,low,middle-1);    //對低字表進行遞歸排序
        unckSort(list,middle+1,high);    //對高字表進行遞歸排序
    }
}

(3) 聲明靜態的 quick() 方法,在該方法中判斷傳入的數組是否為空,如果不為空,則調用 unckSort() 方法進行排序。代碼如下:
public static void quick(int[] str)
{
    if(str.length>0)
    {
        //查看數組是否為空
        unckSort(str,0,str.length-1);
    }
}

(4) 在 main() 方法中聲明 int 類型的 number 數組,接著輸出該數組中的元素。然后調用自定義的 quick() 方法進行排序,排序后重新輸出數組中的元素。代碼如下:
int[] number={13,15,24,99,14,11,1,2,3};
System.out.println("排序前:");
for(int val:number)
{
    System.out.print(val+" ");
}
quick(number);
System.out.println("\n排序后:");
for(int val:number)
{
    System.out.print(val +" ");
}

運行前面的代碼進行測試,輸出結果如下:
排序前:
13 15 24 99 14 11 1 2 3
排序后:
1 2 3 11 13 14 15 24 99 

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo