快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²),但是人家就是优秀,在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好,可是这是为什么呢,我也不知道。好在我的强迫症又犯了,查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案:

快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

1. 算法步骤

  1. 从数列中挑出一个元素,称为 “基准”(pivot);

  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

2. 动图演示

动图演示

3. 代码实现

1. JavaScript 代码实现

  1. function quickSort(arr, left, right) {
  2. var len = arr.length,
  3. partitionIndex,
  4. left = typeof left != 'number' ? 0 : left,
  5. right = typeof right != 'number' ? len - 1 : right;
  6. if (left < right) {
  7. partitionIndex = partition(arr, left, right);
  8. quickSort(arr, left, partitionIndex-1);
  9. quickSort(arr, partitionIndex+1, right);
  10. }
  11. return arr;
  12. }
  13. function partition(arr, left ,right) { // 分区操作
  14. var pivot = left, // 设定基准值(pivot)
  15. index = pivot + 1;
  16. for (var i = index; i <= right; i++) {
  17. if (arr[i] < arr[pivot]) {
  18. swap(arr, i, index);
  19. index++;
  20. }
  21. }
  22. swap(arr, pivot, index - 1);
  23. return index-1;
  24. }
  25. function swap(arr, i, j) {
  26. var temp = arr[i];
  27. arr[i] = arr[j];
  28. arr[j] = temp;
  29. }
  30. function partition2(arr, low, high) {
  31. let pivot = arr[low];
  32. while (low < high) {
  33. while (low < high && arr[high] > pivot) {
  34. --high;
  35. }
  36. arr[low] = arr[high];
  37. while (low < high && arr[low] <= pivot) {
  38. ++low;
  39. }
  40. arr[high] = arr[low];
  41. }
  42. arr[low] = pivot;
  43. return low;
  44. }
  45. function quickSort2(arr, low, high) {
  46. if (low < high) {
  47. let pivot = partition2(arr, low, high);
  48. quickSort2(arr, low, pivot - 1);
  49. quickSort2(arr, pivot + 1, high);
  50. }
  51. return arr;
  52. }

2. Python 代码实现

  1. def quickSort(arr, left=None, right=None):
  2. left = 0 if not isinstance(left,(int, float)) else left
  3. right = len(arr)-1 if not isinstance(right,(int, float)) else right
  4. if left < right:
  5. partitionIndex = partition(arr, left, right)
  6. quickSort(arr, left, partitionIndex-1)
  7. quickSort(arr, partitionIndex+1, right)
  8. return arr
  9. def partition(arr, left, right):
  10. pivot = left
  11. index = pivot+1
  12. i = index
  13. while i <= right:
  14. if arr[i] < arr[pivot]:
  15. swap(arr, i, index)
  16. index+=1
  17. i+=1
  18. swap(arr,pivot,index-1)
  19. return index-1
  20. def swap(arr, i, j):
  21. arr[i], arr[j] = arr[j], arr[i]

3. Go 代码实现

  1. func quickSort(arr []int) []int {
  2. return _quickSort(arr, 0, len(arr)-1)
  3. }
  4. func _quickSort(arr []int, left, right int) []int {
  5. if left < right {
  6. partitionIndex := partition(arr, left, right)
  7. _quickSort(arr, left, partitionIndex-1)
  8. _quickSort(arr, partitionIndex+1, right)
  9. }
  10. return arr
  11. }
  12. func partition(arr []int, left, right int) int {
  13. pivot := left
  14. index := pivot + 1
  15. for i := index; i <= right; i++ {
  16. if arr[i] < arr[pivot] {
  17. swap(arr, i, index)
  18. index += 1
  19. }
  20. }
  21. swap(arr, pivot, index-1)
  22. return index - 1
  23. }
  24. func swap(arr []int, i, j int) {
  25. arr[i], arr[j] = arr[j], arr[i]
  26. }

4. C++版

  1. //严蔚敏《数据结构》标准分割函数
  2. Paritition1(int A[], int low, int high) {
  3. int pivot = A[low];
  4. while (low < high) {
  5. while (low < high && A[high] >= pivot) {
  6. --high;
  7. }
  8. A[low] = A[high];
  9. while (low < high && A[low] <= pivot) {
  10. ++low;
  11. }
  12. A[high] = A[low];
  13. }
  14. A[low] = pivot;
  15. return low;
  16. }
  17. void QuickSort(int A[], int low, int high) //快排母函数
  18. {
  19. if (low < high) {
  20. int pivot = Paritition1(A, low, high);
  21. QuickSort(A, low, pivot - 1);
  22. QuickSort(A, pivot + 1, high);
  23. }
  24. }

5. Java 代码实现

  1. public class QuickSort implements IArraySort {
  2. @Override
  3. public int[] sort(int[] sourceArray) throws Exception {
  4. // 对 arr 进行拷贝,不改变参数内容
  5. int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  6. return quickSort(arr, 0, arr.length - 1);
  7. }
  8. private int[] quickSort(int[] arr, int left, int right) {
  9. if (left < right) {
  10. int partitionIndex = partition(arr, left, right);
  11. quickSort(arr, left, partitionIndex - 1);
  12. quickSort(arr, partitionIndex + 1, right);
  13. }
  14. return arr;
  15. }
  16. private int partition(int[] arr, int left, int right) {
  17. // 设定基准值(pivot)
  18. int pivot = left;
  19. int index = pivot + 1;
  20. for (int i = index; i <= right; i++) {
  21. if (arr[i] < arr[pivot]) {
  22. swap(arr, i, index);
  23. index++;
  24. }
  25. }
  26. swap(arr, pivot, index - 1);
  27. return index - 1;
  28. }
  29. private void swap(int[] arr, int i, int j) {
  30. int temp = arr[i];
  31. arr[i] = arr[j];
  32. arr[j] = temp;
  33. }
  34. }

6. PHP 代码实现

  1. function quickSort($arr)
  2. {
  3. if (count($arr) <= 1)
  4. return $arr;
  5. $middle = $arr[0];
  6. $leftArray = array();
  7. $rightArray = array();
  8. for ($i = 1; $i < count($arr); $i++) {
  9. if ($arr[$i] > $middle)
  10. $rightArray[] = $arr[$i];
  11. else
  12. $leftArray[] = $arr[$i];
  13. }
  14. $leftArray = quickSort($leftArray);
  15. $leftArray[] = $middle;
  16. $rightArray = quickSort($rightArray);
  17. return array_merge($leftArray, $rightArray);
  18. }