快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²),但是人家就是优秀,在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好,可是这是为什么呢,我也不知道。好在我的强迫症又犯了,查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案:
functionquickSort(arr, left, right) {var len =arr.length, partitionIndex, left =typeof left !='number'?0: left, right =typeof right !='number'? len -1: right;if (left < right) { partitionIndex =partition(arr, left, right);quickSort(arr, left, partitionIndex-1);quickSort(arr, partitionIndex+1, right); }return arr;}functionpartition(arr, left ,right) { // 分区操作var pivot = left,// 设定基准值(pivot) index = pivot +1;for (var i = index; i <= right; i++) {if (arr[i] < arr[pivot]) {swap(arr, i, index); index++; } }swap(arr, pivot, index -1);return index-1;}functionswap(arr, i, j) {var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}functionpartition2(arr, low, high) {let 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;}functionquickSort2(arr, low, high) {if (low < high) {let pivot =partition2(arr, low, high);quickSort2(arr, low, pivot -1);quickSort2(arr, pivot +1, high); }return arr;}
4. Python 代码实现
defquickSort(arr,left=None,right=None): left =0ifnotisinstance(left,(int, float))else left right =len(arr)-1ifnotisinstance(right,(int, float))else rightif left < right: partitionIndex =partition(arr, left, right)quickSort(arr, left, partitionIndex-1)quickSort(arr, partitionIndex+1, right)return arrdefpartition(arr,left,right): pivot = left index = pivot+1 i = indexwhile i <= right:if arr[i]< arr[pivot]:swap(arr, i, index) index+=1 i+=1swap(arr,pivot,index-1)return index-1defswap(arr,i,j): arr[i], arr[j]= arr[j], arr[i]
5. Go 代码实现
funcquickSort(arr []int) []int {return _quickSort(arr, 0, len(arr)-1)}func_quickSort(arr []int, left, right int) []int {if left < right { partitionIndex := partition(arr, left, right) _quickSort(arr, left, partitionIndex-1) _quickSort(arr, partitionIndex+1, right) }return arr}funcpartition(arr []int, left, right int) int { pivot := left index := pivot +1for i := index; i <= right; i++ {if arr[i] < arr[pivot] { swap(arr, i, index) index +=1 } } swap(arr, pivot, index-1)return index -1}funcswap(arr []int, i, j int) { arr[i], arr[j] = arr[j], arr[i]}