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. 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. // quick_sort

  19. template<typename T>

  20. void quick_sort(T arr[], int len) {

  21. quick_sort_recursive(arr, 0, len - 1);

  22. }

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++版(迭代法):

struct Range { int start, end; Range(int s = 0, int e = 0) {start = s, end = e;}};template<typename Tvoid 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)。欲知详情,且听下回分解。