时间复杂度 最坏情况下O(快速排序 - 图1), 平均的复杂度为O(快速排序 - 图2)

快速排序也是一种分治的递归算法。将数组S排序的基本算法由下滤简单的四步组成：

  1. 如果S中元素的个数为0或者1，则返回；
  2. 取S中任意一元素快速排序 - 图3，称之为枢纽元(pivot)
  3. 将快速排序 - 图4(S中剩余元素)分成两个不想交的集合： 和
  4. 返回quicksort(快速排序 - 图5)后，即随快速排序 - 图6 继而quicksort(快速排序 - 图7)

枢纽元的选择

  1. 随机选取枢纽元，利用随机数生成器，产生一个随机数充当枢纽元。
  2. 选取中值，
  3. void quickSort(int *arr, int size)
  4. {
  5.     qSort(arr, 0, size - 1);
  6. };
  8. void qSort(int *arr, int start, int end)
  9. {
  10.     if (start < end)
  11.     {
  12.         int q = partition(arr, start, end);
  13.         qSort2(arr, start, q - 1);
  14.         qSort2(arr, q + 1, end);
  15.     }
  16. };
  18. int partition(int *arr, int start, int end)
  19. {
  20.     int pivot = arr[start];
  21.     int i = start;
  22.     for (int j = start + 1; j <= end; j++)
  23.     {
  24.         if (arr[j] <= pivot)
  25.         {
  26.             i++;
  27.             swap(&arr[i], &arr[j]);
  28.         }
  29.     }
  30.     swap(&arr[start], &arr[i]);
  31.     return i;
  32. };
  3. /**
  4.  * 
  5.  * @param {number[]} arr 
  6.  */
  7. const quickSort = (arr) => {
  8.     debugger
  9.     _qs(arr, 0, arr.length - 1);
  10. }
  11. /**
  12.  * 
  13.  * @param {number[]} arr 
  14.  * @param {number} left 
  15.  * @param {number} right 
  16.  */
  17. const _qs = (arr, left, right) => {
  18.     if (left < right) {
  19.         const idx = partition(arr, left, right);
  20.         _qs(arr, left, idx - 1);
  21.         _qs(arr, idx + 1, right);
  22.     }
  23. }
  24. /**
  25.  * 
  26.  * @param {number[]} arr 
  27.  * @param {number} left 
  28.  * @param {number} right 
  29.  * @returns {number}
  30.  */
  31. const partition = (arr, left, right) => {
  32.     let i = left;
  33.     let j = right - 1;
  34.     let mid = (left + right) >> 1
  35.     let item = arr[mid];
  36.     swap(arr, mid, right);
  37.     while (i <= j) {
  38.         while (i <= j && item > arr[i]) { i++ }
  39.         while (i <= j && item < arr[j]) { j-- }
  40.         if (i == j) break;
  41.         if (i < j) {
  42.             swap(arr, i, j)
  43.         }
  44.     }
  45.     swap(arr, i, right);
  46.     return i;
  47. }
  49. const swap = (arr, a, b) => {
  50.     let t = arr[a];
  51.     arr[a] = arr[b];
  52.     arr[b] = t;
  53. }
  55. const arr = [50, 63, 41, 5, 9, 78, 30, 46, 84, 12, 1, 53, 63, 85, 9];
  56. // const arr = [6, 4, 2, 5, 9, 8, 3, 7]
  57. console.log(arr.join(" "));
  58. quickSort(arr);
  59. console.log(arr.join(" "));