## **快速排序** 快速排序是一個知名度極高的排序算法，其對于大數據的優秀排序性能和相同復雜度算法中相對簡單的實現使它注定得到比其他算法更多的寵愛。 ## **算法描述** 1. 從數列中挑出一個元素，稱為"基準"（pivot）， 2. 重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（相同的數可以到任何一邊）。在這個分區結束之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。 3. 遞歸地（recursively）把小于基準值元素的子數列和大于基準值元素的子數列排序。 ## **穩定性** 快速排序并不是穩定的。這是因為我們無法保證相等的數據按順序被掃描到和按順序存放。 ## **適用場景** 快速排序在大多數情況下都是適用的，尤其在數據量大的時候性能優越性更加明顯。但是在必要的時候，需要考慮下優化以提高其在最壞情況下的性能。 ## **JAVA代碼實現** ``` public static void quickSort(int[] arr){ qsort(arr, 0, arr.length-1); } private static void qsort(int[] arr, int low, int high){ if (low >= high) return; int pivot = partition(arr, low, high); //將數組分為兩部分 qsort(arr, low, pivot-1); //遞歸排序左子數組 qsort(arr, pivot+1, high); //遞歸排序右子數組 } private static int partition(int[] arr, int low, int high){ int pivot = arr[low]; //基準 while (low < high){ while (low < high && arr[high] >= pivot) --high; arr[low]=arr[high]; //交換比基準大的記錄到左端 while (low < high && arr[low] <= pivot) ++low; arr[high] = arr[low]; //交換比基準小的記錄到右端 } //掃描完成，基準到位 arr[low] = pivot; //返回的是基準的位置 return low; } ```