前几回，在前面已经对冒泡排序、直接插入排序、希尔排序、选择排序做了说明分析。这回，将对快速排序进行相关说明分析。

一、排序算法系列目录说明

  • 冒泡排序（Bubble Sort）
  • 插入排序（Insertion Sort）
  • 希尔排序（Shell Sort）
  • 选择排序（Selection Sort）
  • 快速排序（Quick Sort）
  • 归并排序（Merge Sort）
  • 堆排序（Heap Sort）
  • 计数排序（Counting Sort）
  • 桶排序（Bucket Sort）
  • 基数排序（Radix Sort）

二、快速排序（Quick Sort）

快速排序，又称划分交换排序（partition-exchange sort）

1.基本思想

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

2. 实现逻辑

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。 ① 从数列中挑出一个元素，称为 “基准”（pivot），② 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。③ 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

3. 动图演示

排序算法之快速排序 - 图1
快速排序

4. 复杂度

平均时间复杂度：O(NlogN)最佳时间复杂度：O(NlogN)最差时间复杂度：O(N^2)空间复杂度：根据实现方式的不同而不同

5. 代码实现

C版本（递归法）：

  1. void swap(int *x, int *y) {
  2.     int t = *x;
  3.     *x = *y;
  4.     *y = t;
  5. }
  6. void quick_sort_recursive(int arr[], int start, int end) {
  7.     if (start >= end)
  8.         return;
  9.     int mid = arr[end];
  10.     int left = start, right = end - 1;
  11.     while (left < right) {
  12.         while (arr[left] < mid && left < right)
  13.             left++;
  14.         while (arr[right] >= mid && left < right)
  15.             right--;
  16.         swap(&arr[left], &arr[right]);
  17.     }
  18.     if (arr[left] >= arr[end])
  19.         swap(&arr[left], &arr[end]);
  20.     else
  21.         left++;
  22.     if (left) {
  23.         quick_sort_recursive(arr, start, left - 1);
  24.     }
  25.     quick_sort_recursive(arr, left + 1, end);
  26. }
  27. void quick_sort(int arr[], int len) {
  28.     quick_sort_recursive(arr, 0, len - 1);
  29. }

C++版本（递归法）：

  1. template<typename T>
  2. void quick_sort_recursive(T arr[], int start, int end) {
  3.     if (start >= end) return;
  4.     T mid = arr[end];
  5.     int left = start, right = end - 1;
  6.     while (left < right) {
  7.         while (arr[left] < mid && left < right) left++;
  8.         while (arr[right] >= mid && left < right) right--;
  9.         std::swap(arr[left], arr[right]);
  10.     }
  11.     if (arr[left] >= arr[end])
  12.         std::swap(arr[left], arr[end]);
  13.     else
  14.         left++;
  15.     quick_sort_recursive(arr, start, left - 1);
  16.     quick_sort_recursive(arr, left + 1, end);
  17. }
  18. template<typename T>
  19. void quick_sort(T arr[], int len) {
  20.     quick_sort_recursive(arr, 0, len - 1);
  21. }

Java版本：

  1. class quick_sort {
  2.     int[] arr;
  3.     private void swap(int x, int y) {
  4.         int temp = arr[x];
  5.         arr[x] = arr[y];
  6.         arr[y] = temp;
  7.     }
  8.     private void quick_sort_recursive(int start, int end) {
  9.         if (start >= end)
  10.             return;
  11.         int mid = arr[end];
  12.         int left = start, right = end - 1;
  13.         while (left < right) {
  14.             while (arr[left] <= mid && left < right)
  15.                 left++;
  16.             while (arr[right] >= mid && left < right)
  17.                 right--;
  18.             swap(left, right);
  19.         }
  20.         if (arr[left] >= arr[end])
  21.             swap(left, end);
  22.         else
  23.             left++;
  24.         quick_sort_recursive(start, left - 1);
  25.         quick_sort_recursive(left + 1, end);
  26.     }
  27.     public void sort(int[] arrin) {
  28.         arr = arrin;
  29.         quick_sort_recursive(0, arr.length - 1);
  30.     }
  31. }

6. 优化改进

场景分析： 递归是一种使用相同的方法，通过解决问题的子集以达到解决整个问题的方法，是一种使用有限代码解决“无限”计算的方法。在C/C++语言中递归表现在函数对自身的直接/间接的调用上，在实现上，递归依赖于语言的运行时调用堆栈，使用堆栈来保存每一次递归调用返回时所需要的条件。递归通常具有简洁的编码和清晰的思路，但这种简洁是有代价的。一方面，是函数调用的负担；另一方面，是堆栈占用的负担（堆栈的大小是有限的）。
改进思路：递归转化为迭代。迭代的思想主要在于，在同一栈帧中不断使用现有数据计算出新的数据，然后使用新的数据来替换原有数据。
改进代码：
C版本（迭代法）：

  1. typedef struct _Range {
  2.     int start, end;
  3. } Range;
  4. Range new_Range(int s, int e) {
  5.     Range r;
  6.     r.start = s;
  7.     r.end = e;
  8.     return r;
  9. }
  10. void swap(int *x, int *y) {
  11.     int t = *x;
  12.     *x = *y;
  13.     *y = t;
  14. }
  15. void quick_sort(int arr[], const int len) {
  16.     if (len <= 0)
  17.         return; //避免len等于负值时错误
  18.     //r[]模拟堆疊,p为数量,r[p++]为push,r[--p]为pop且取得元素
  19.     Range r[len];
  20.     int p = 0;
  21.     r[p++] = new_Range(0, len - 1);
  22.     while (p) {
  23.         Range range = r[--p];
  24.         if (range.start >= range.end)
  25.             continue;
  26.         int mid = arr[range.end];
  27.         int left = range.start, right = range.end - 1;
  28.         while (left < right) {
  29.             while (arr[left] < mid && left < right)
  30.                 left++;
  31.             while (arr[right] >= mid && left < right)
  32.                 right--;
  33.             swap(&arr[left], &arr[right]);
  34.         }
  35.         if (arr[left] >= arr[range.end])
  36.             swap(&arr[left], &arr[range.end]);
  37.         else
  38.             left++;
  39.         r[p++] = new_Range(range.start, left - 1);
  40.         r[p++] = new_Range(left + 1, range.end);
  41.     }
  42. }

C++版（迭代法）：

  1. struct Range {
  2.     int start, end;
  3.     Range(int s = 0, int e = 0) {start = s, end = e;}
  4. };
  5. template<typename T> 
  6. void quick_sort(T arr[], const int len) {
  7.     if (len <= 0) return; //避免len等于负值时错误
  8.     //r[]模拟堆疊,p为数量,r[p++]为push,r[--p]为pop且取得元素
  9.     Range r[len]; int p = 0;
  10.     r[p++] = Range(0, len - 1);
  11.     while (p) {
  12.         Range range = r[--p];
  13.         if(range.start >= range.end) continue;
  14.         T mid = arr[range.end];
  15.         int left = range.start, right = range.end - 1;
  16.         while (left < right) {
  17.             while (arr[left] < mid && left < right) left++;
  18.             while (arr[right] >= mid && left < right) right--;
  19.             std::swap(arr[left], arr[right]);
  20.         }
  21.         if (arr[left] >= arr[range.end])
  22.             std::swap(arr[left], arr[range.end]);
  23.         else
  24.             left++;
  25.         r[p++] = Range(range.start, left - 1);
  26.         r[p++] = Range(left + 1, range.end);
  27.     }
  28. }

三、总结

快速排序在排序算法中具有排序速度快，而且是就地排序等优点，使得在许多编程语言的内部元素排序实现中采用的就是快速排序，很多面试题中也经常遇到。对于其算法的改进，除了刚刚上文中提到的意外，根据实际场景还有诸多改进方法，包括对小序列采用插入排序替代，三平均划分，三分区划分等改进方法（相关的改进方法就不一一说明，有兴趣的读者可上网查阅了解）。
下一篇预告：归并排序（Merge Sort）。欲知详情，且听下回分解。