前言

Quick Sort 跟 Merge Sort 一樣都是 Divide and Conquer。

• Divide and Conquer 就是將複雜問題分解成很多個簡單的問題，先解決所有的簡單的問題，再把所有簡單的問題的答案合起來作為複雜問題的答案。

  • Divide : 將n個數字分割成兩個數列分別是:比基準大的數列和比基準小的數列。
  • Conquer : 再去分割兩個數列。
  • Combine : 每個數列分割完後，最後會得到一個有序的數列。

Quick Sort

在數列中選一個作為Pivot，並讓Pivot的左邊數值都會比pivot小，且Pivot的右邊數值都會比pivot大，然後在把pivot的左邊和pivot的右邊排好。

• 時間複雜度: O(nlogn)，worst case : O(n²)
• 實作:

public class Quick_Sort 
{
	public static void main(String[] args)
	{
		int ary[] =  {52, 99, 31, 60, 7, 46, 53};
		
		// before sort
		PrintArray(ary); 
				
		System.out.println("--------------------");
		QuickSort(ary, 0, ary.length - 1);
		        
		// after sort
		PrintArray(ary);
	}
	
	public static void QuickSort(int arr[], int left, int right) 
	{
        if(left < right) 
        { 
            int pivot = Partition(arr, left, right); 
            QuickSort(arr, left, pivot - 1); 
            QuickSort(arr, pivot + 1, right); 
        } 
    }

    public static int Partition(int arr[], int left, int right) 
    {  
    	int pivot = arr[left];
    	
        int i = left + 1; //放比基準值小的數值
        
        //從左邊到右邊，找出比基準值小的數值做交換
        for(int j = left + 1; j <= right; j++) 
        { 
            if(arr[j] <= pivot)
            { 
                Swap(arr, i, j);
                i++;
            }
        } 
        //把基準值交換到中間，讓基準值大於左邊的數，小於右邊的數
        Swap(arr, left, i - 1); 
        return i - 1; 
    } 

    public static void Swap(int arr[], int x, int y)
	{
		int temp = arr[x];
		arr[x] = arr[y];
		arr[y] = temp;
	}
	
	public static void PrintArray(int arr[])
	{
		for(int i = 0; i < arr.length; i++)
	    {
			System.out.print(arr[i] + " ");
	    }
		System.out.println();
	}
    
}

輸出結果:

52 99 31 60 7 46 53 
--------------------
7 31 46 52 53 60 99