快速排序

算法描述

快速排序利用了传递性的概念, "如果 x > y, y > z, 则 x > z".

  • 从数组中选择一个元素, 具体哪个并不重要, 称该元素为 pivot
  • 算法将数组分为三个部分, 比 pivot 小的元素, 与 pivot 相等的元素, 比 pivot 大的元素
  • 算法对 小于 pivot 的元素集 和 大于 pivot 的元素集 进行递归
  • 当所有元素均被排序后, 程序结束
  • 当每一部分都仅剩一个元素或没有元素时, 程序结束

每一次递归:

  1. 决定 pivot 的值, 可以选第一个元素
  2. 采用两个下标 low 和 high, low 的初值比 pivot 的下标大 1, high 的初值是问题范围内的最大下标
  3. 从左起, 如果元素小于 pivot, low 加 1, 如果元素大于 pivot, low 保持不变
  4. 从右起, 如果元素大于 pivot, high 减 1, 如果元素小于 pivot, high 保持不变
  5. 交换下标为 low 和 high 的元素
  6. 继续步骤 3 ~ 5, 直至 low 的值大于 high
  7. 将 pivot 置于两个部分之间

第 7 步完成后, 所有小于 pivot 的元素都在一起, 所有大于 pivot 的元素也都在一起.
而这两部分之间, 就是最终排序完成后, pivot 应该在的位置.

举例 | 待排序数组 { 53, 77, 31, 7, 81, 40, 16, 21, 46, 55, 68, 9 }

arr: { 53, 77, 31, 7, 81, 40, 16, 21, 46, 55, 68, 9 }
first: 0, last: 11
pivot: 53, low: 1, high: 11

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 77 31 7 81 40 16 21 46 55 68 9
  first low                   last, high

下标为 low 的元素大于 pivot, low 的值不变
下标为 high 的元素小于 pivot, high 的值不变
交换下标为 low 和 high 的元素

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 77 => 9 31 7 81 40 16 21 46 55 68 9 => 77
  first low                   last, high

下标为 low 的元素小于 pivot, low 加 1

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 9 31 7 81 40 16 21 46 55 68 77
  first   low                 last, high

下标为 low 的元素小于 pivot, low 加 1

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 9 31 7 81 40 16 21 46 55 68 77
  first     low               last, high

下标为 low 元素小于 pivot, low 加 1

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 9 31 7 81 40 16 21 46 55 68 77
  first       low             last, high

下标为 low 的元素大于 pivot, low 的值不变
下标为 high 的元素大于 pivot, high 减 1

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 9 31 7 81 40 16 21 46 55 68 77
  first       low           high last

下标为 high 的元素大于 pivot, high 减 1

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 9 31 7 81 40 16 21 46 55 68 77
  first       low         high   last

下标为 high 的元素大于 pivot, high 减 1

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 9 31 7 81 40 16 21 46 55 68 77
  first       low       high     last

下标为 high 的元素小于 pivot, high 的值不变
交换下标为 low 和 high 的元素

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 9 31 7 81 => 46 40 16 21 46 => 81 55 68 77
  first       low       high     last

下标为 low 的元素小于 pivot, low 加 1

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 9 31 7 46 40 16 21 81 55 68 77
  first         low     high     last

下标为 low 的元素小于 pivot, low 加 1

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 9 31 7 46 40 16 21 81 55 68 77
  first           low   high     last

下标为 low 的元素小于 pivot, low 加 1

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 9 31 7 46 40 16 21 81 55 68 77
  first             low high     last

下标为 low 的元素小于 pivot, low 加 1

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 9 31 7 46 40 16 21 81 55 68 77
  first               low, high     last

下标为 low 的元素大于 pivot, low 保持不变
下标为 high 的元素大于 pivot, high 减 1

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 53, pivot 9 31 7 46 40 16 21 81 55 68 77
  first             high low     last

此时, low > high, 交换 pivot 和 arr[high]

下标 0 1 2 3 4 5 6 7 8 9 10 11
元素 (53, pivot) => 21 9 31 7 46 40 16 21 => (53, pivot) 81 55 68 77
  first             high low     last

交换完成后, 数组被分成了三个部分:

  • 小于 pivot 的部分, arr[first] ... arr[high-1]
  • 等于 pivot 的部分, arr[high]
  • 大于 pivot 的部分, arr[low] ... arr[last]

对小于 pivot 的部分, 大于 pivot 的部分进行递归, 直至排序完成.

代码 ( C 语言 )

  1. void swap(int * a, int * b) {
  2. int temp = *a;
  3. *a = *b;
  4. *b = temp;
  5. }
  6.  
  7. void quick_sort(int * arr, int first, int last) {
  8. if ( first >= last )
  9. return;
  10.  
  11. int pivot = arr[first];
  12. int low = first + 1;
  13. int high = last;
  14.  
  15. while ( low < high ) {
  16. while ( low < last && arr[low] <= pivot )
  17. low++;
  18. while ( high > first && arr[high] > pivot )
  19. high--;
  20. if ( low < high )
  21. swap(&arr[low], &arr[high]);
  22. }
  23. if ( pivot > arr[high] )
  24. swap(&arr[first], &arr[high]);
  25.  
  26. quick_sort(arr, first, high-1);
  27. quick_sort(arr, low, last);
  28. }

随机选取数组元素作为 pivot 的好处

对于初始数组是已排序的, 如果选第一个元素做 pivot, 那么, 比 pivot 小的部分将是空的.
程序并没有利用到传递性, 排序的效率并没有提升.
《算法笔记》(刁瑞, 谢妍) 关于快速排序的讨论, 随机选取 pivot 也有问题, 推荐采用 {首元素, 中间元素, 末尾元素} 的中位数作为 pivot.

《 C 语言程序设计进阶教程》