> ### 快速排序 * 快速排序使用分治法来把一个串（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)