快速排序

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

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

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

快速排序的名字起的是简单，当听到这个名字的时候其实你就知道它存在的意义，就是快速排序，而且效率高！它是处理大数据最快的排序算法之一了。

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

算法原理

快速排序的算法原理:

  • 从数列中挑出一个元素，称为 “基准”(pivot).
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作.
  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序.

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

快速排序 - 图1

快速排序算法实现：

  2. func main() {
  3.     var arr = []int{19,8,16,15,23,34,6,3,1,0,2,9,7}
  4.     quickAscendingSort(arr, 0, len(arr)-1)
  5.     fmt.Println("quickAscendingSort:",arr)
  7.     quickDescendingSort(arr, 0, len(arr)-1)
  8.     fmt.Println("quickDescendingSort:",arr)
  9. }
  11. //升序
  12. func quickAscendingSort(arr []int, start, end int) {
  13.     if (start < end) {
  14.         i, j := start, end
  15.         key := arr[(start + end)/2]
  16.         for i <= j {
  17.             for arr[i] < key {
  18.                 i++
  19.             }
  20.             for arr[j] > key {
  21.                 j--
  22.             }
  23.             if i <= j {
  24.                 arr[i], arr[j] = arr[j], arr[i]
  25.                 i++
  26.                 j--
  27.             }
  28.         }
  30.         if start < j {
  31.             quickAscendingSort(arr, start, j)
  32.         }
  33.         if end > i {
  34.             quickAscendingSort(arr, i, end)
  35.         }
  36.     }
  37. }
  39. //降序
  40. func quickDescendingSort(arr []int, start, end int) {
  41.     if (start < end) {
  42.         i, j := start, end
  43.         key := arr[(start + end)/2]
  44.         for i <= j {
  45.             for arr[i] > key {
  46.                 i++
  47.             }
  48.             for arr[j] < key {
  49.                 j--
  50.             }
  51.             if i <= j {
  52.                 arr[i], arr[j] = arr[j], arr[i]
  53.                 i++
  54.                 j--
  55.             }
  56.         }
  58.         if start < j {
  59.             quickDescendingSort(arr, start, j)
  60.         }
  61.         if end > i {
  62.             quickDescendingSort(arr, i, end)
  63.         }
  64.     }
  65. }

运行结果:

  1. quickAscendingSort: [0 1 2 3 6 7 8 9 15 16 19 23 34]
  2. quickDescendingSort: [34 23 19 16 15 9 8 7 6 3 2 1 0]