vlambda博客
学习文章列表

【算法】排序算法之快速排序

前几回，在前面已经对、、、做了说明分析。这回，将对快速排序进行相关说明分析。

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

  • 冒泡排序（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.动图演示

4.复杂度

  • 平均时间复杂度：O(NlogN)

  • 最佳时间复杂度：O(NlogN)

  • 最差时间复杂度：O(N^2)

  • 空间复杂度：根据实现方式的不同而不同

5.代码实现

C版本（递归法）：

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

C++版本（递归法）：

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

    19. 
  
    
    
  
  19. // quick_sort
    20. 
  
    
    
  
  20. template<typename T>
    21. 
  
    
    
  
  21. void quick_sort(T arr[], int len) {
    22. 
  
    
    
  
  22.  quick_sort_recursive(arr, 0, len - 1);
    23. 
  
    
    
  
  23. }
    24.

Java版本：

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

6.优化改进

场景分析：

递归是一种使用相同的方法，通过解决问题的子集以达到解决整个问题的方法，是一种使用有限代码解决“无限”计算的方法。在C/C++语言中递归表现在函数对自身的直接/间接的调用上，在实现上，递归依赖于语言的运行时调用堆栈，使用堆栈来保存每一次递归调用返回时所需要的条件。递归通常具有简洁的编码和清晰的思路，但这种简洁是有代价的。一方面，是函数调用的负担；另一方面，是堆栈占用的负担（堆栈的大小是有限的）。

改进思路：

递归转化为迭代。迭代的思想主要在于，在同一栈帧中不断使用现有数据计算出新的数据，然后使用新的数据来替换原有数据。

改进代码：

C版本（迭代法）：

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

C++版（迭代法）：

struct Range { int start, end; Range(int s = 0, int e = 0) {start = s, end = e;}};template<typename T> void quick_sort(T arr[], const int len) { if (len <= 0) return; //避免len等于负值时错误 //r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素 Range r[len]; int p = 0; r[p++] = Range(0, len - 1); while (p) { Range range = r[--p]; if(range.start >= range.end) continue; T mid = arr[range.end]; int left = range.start, right = range.end - 1; while (left < right) { while (arr[left] < mid && left < right) left++; while (arr[right] >= mid && left < right) right--; std::swap(arr[left], arr[right]); } if (arr[left] >= arr[range.end]) std::swap(arr[left], arr[range.end]); else left++; r[p++] = Range(range.start, left - 1); r[p++] = Range(left + 1, range.end); }}


三、总结

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

下一篇预告：归并排序（Merge Sort）。欲知详情，且听下回分解。

推荐阅读

[5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档 [5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档
【算法】排序算法之堆排序 【算法】排序算法之堆排序

相关文章