快速排序算法（Java實作）

快速排序（Quick Sort）

快速排序的基本思想：通過一趟排序将待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分别對這兩部分記錄繼續進行排序，以達到整個序列有序。

算法描述

快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下：

• 從數列中挑出一個元素，稱為 “基準”（pivot）；
• 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
• 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

代碼實作

import java.util.Arrays;

public class TestQuickSort {
        private static int partition(int[] arr, int low, int high) {
                //指定左指針i和右指針j
                int i = low;
                int j= high;
                
                //将第一個數作為基準值。挖坑
                int x = arr[low];
                
                //使用循環實作分區操作
                while(i<j){//5  8
                        //1.從右向左移動j，找到第一個小于基準值的值 arr[j]
                        while(arr[j]>=x && i<j){
                                j--;
                        }
                        //2.将右側找到小于基準數的值加入到左邊的（坑）位置， 左指針想中間移動一個位置i++
                        if(i<j){
                                arr[i] = arr[j];
                                i++;
                        }
                        //3.從左向右移動i，找到第一個大于等于基準值的值 arr[i]
                        while(arr[i]<x && i<j){
                                i++;
                        }
                        //4.将左側找到的列印等于基準值的值加入到右邊的坑中，右指針向中間移動一個位置 j--
                        if(i<j){
                                arr[j] = arr[i];
                                j--;
                        }
                }
                
                //使用基準值填坑，這就是基準值的最終位置
                arr[i] = x;//arr[j] = y;
                //傳回基準值的位置索引
                return i; //return j;
        }
        private static void quickSort(int[] arr, int low, int high) {//???遞歸何時結束
                if(low < high){
                        //分區操作，将一個數組分成兩個分區，傳回分區界限索引
                        int index = partition(arr,low,high);
                        //對左分區進行快排
                        quickSort(arr,low,index-1);
                        //對右分區進行快排
                        quickSort(arr,index+1,high);
                }
        
        }

        public static void quickSort(int[] arr) {
                int low = 0;
                int high = arr.length-1;
                quickSort(arr,low,high);
        }
        
        public static void main(String[] args) {
                //給出無序數組
                int arr[] = {72,6,57,88,60,42,83,73,48,85};

        //輸出無序數組
        System.out.println(Arrays.toString(arr));
        //快速排序
        quickSort(arr);
        //partition(arr,0,arr.length-1);
        //輸出有序數組
        System.out.println(Arrays.toString(arr));
        }

        
}

           

最佳情況：T(n) = O(nlogn) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(nlogn)