> ### 快速排序 * 快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下： * 從數列中挑出一個元素，稱為 “基準”（pivot）； * 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作； * 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。 * **時間復雜度**：`O(nlogn)` * 最壞情況 `O(n^2)`，劃分之后一邊是一個，一邊是n-1個，這種是最壞的極端情況，**不穩定** ```java public int[] quickSort(int[] arr, int left, int right) { if(left < right) { int p = partition(arr, left, right); //基準值 quickSort(arr, left, p - 1); quickSort(arr, p + 1, right); } return arr; } public int partition(int[] arr, int left, int right) { int p = left; // 根據基準值交換 int index = left + 1; for(int i = index; i <= right; i++) { if(arr[i] < arr[p]) { swap(arr, index, i); index++; } } swap(arr, p, index - 1); return index - 1; } public void swap(int[] arr, int t1, int t2){ int temp = arr[t1]; //交換數組元素 arr[t1] = arr[t2]; arr[t2] = temp; } ``` <br/> <br/> *** 參考： [十大經典排序算法](https://github.com/hustcc/JS-Sorting-Algorithm)