簡述

快速排序是屬于交換排序的一種（冒泡排序也是）。是冒泡排序的一種改進。是不穩(wěn)定的一種算法，因為假如出現(xiàn)了同樣的數(shù)字，無法確定同樣的數(shù)字出現(xiàn)的位置是否跟預(yù)測中的一樣。比如，[2, 4, 5, 3, 7, 3]，排序后是[2, 3, 3, 4, 5, 7]，無法確保第一個3是原來的第一個位置上的3。

時間復(fù)雜度：

平均情況：O（n㏒?n）

最壞情況：O（n2）

最好情況：O（n㏒?n）

空間復(fù)雜度：O（n㏒?n）

快速排序偽代碼

quickSort(A, left, right)
    if right < left
        then
            j = sort(A, left, right);
            quickSort(A, left, j - 1);
            quickSort(A, j-1, right);
end

sort(A, left, right)
    x = a[left];
    i = left;
    j = right;
    while (i < j)
        do 
            while (j > i and A[j]  >= x)
            do 
                j--
            A[i] = A[j];
            while (i < j and A[i] <= x)
            do
                i++
            A[j] = A[i];
    A[j] = x;
    return j;

算法的關(guān)鍵點在于，設(shè)置基準數(shù)（x），然后在一定范圍內(nèi)，將范圍正確劃分為小于基準數(shù)，基準數(shù)，大于基準數(shù)，這三部分，然后當范圍足夠小的時候，就是一個正確的排序的集合了。

const arr = [2, 5, 3, 8, 1, 7, 4, 9, 6, 0];

const quickSort = (arr) => {
  const sort = (arr, left, right) => {
    if (left >= right) {
      return
    }
    let i = left, j = right;
    let base = arr[i];
    console.log(arr);
    while(i < j) {
      while ( j > i && arr[j] >= base) {
        j--;
      }
      arr[i] = arr[j];
      while (i < j && arr[i] <= base) {
        i++;
      }
      arr[j] = arr[i];
    }
    arr[j] = base;
    sort(arr, left, j-1);
    sort(arr, j+1, right);
  };
  let newArr = arr.slice();
  sort(newArr, 0, newArr.length - 1)
};
quickSort(arr);

我們來分析一下:

while(i < j) 第一次循環(huán)，i = 0，j = 9， base = 2

//arr
[2, 5, 3, 8, 1, 7, 4, 9, 6, 0]

// while( j > i && arr[j] >= base)，結(jié)果是
[0, 5, 3, 8, 1, 7, 4, 9, 6, 0]
// arr[j]的結(jié)果賦予arr[i]，i = 0, j = 9, base = 2

// while (i < j && arr[i] <= base)，結(jié)果是
[0, 5, 3, 8, 1, 7, 4, 9, 6, 5]
// arr[i]的結(jié)果賦予arr[j], i = 1, j = 9, base = 2

while(i < j) 第二次循環(huán)，i = 1，j = 9， base = 2

// 上一次結(jié)果的arr
[0, 5, 3, 8, 1, 7, 4, 9, 6, 5]

// while( j > i && arr[j] >= base)，結(jié)果是
[0, 1, 3, 8, 1, 7, 4, 9, 6, 5]
// arr[j]的結(jié)果賦予arr[i]， i = 1, j = 4, base = 2

// while (i < j && arr[i] <= base)，結(jié)果是
[0, 1, 3, 8, 3, 7, 4, 9, 6, 5]
// arr[i]的結(jié)果賦予arr[j], i = 2, j = 4, base = 2

while(i < j) 第三次循環(huán)，i = 2，j = 4， base = 2

// 上一次結(jié)果的arr
[0, 1, 3, 8, 3, 7, 4, 9, 6, 5]

// while( j > i && arr[j] >= base)，結(jié)果是
[0, 1, 3, 8, 3, 7, 4, 9, 6, 5]
// arr[j]的結(jié)果賦予arr[i]， i = 2, j = 2, base = 2

// while (i < j && arr[i] <= base)，結(jié)果是
[0, 1, 3, 8, 3, 7, 4, 9, 6, 5]
// arr[i]的結(jié)果賦予arr[j], i = 2, j = 2, base = 2

// i > j 條件不成立， while(i < j) 循環(huán)結(jié)束
// 將arr[j]的值恢復(fù)為基準值，arr[j] = base
[0, 1, 2, 8, 3, 7, 4, 9, 6, 5]

所以第一次sort執(zhí)行完畢，已經(jīng)得到了已2為基準值的符合條件（小于基準值，基準值，大于基準值）的數(shù)組了，只需要將基準值左邊跟基準值右邊也遞歸一下，就能得到有序的數(shù)組了。判斷結(jié)束的條件是left >= right。

如果基準值選到最小值，那么相當于一個長度為數(shù)組長度的冒泡排序操作，如果每一次都選到最小值，那么它的時間復(fù)雜度相當于冒泡排序，其實也就是冒泡排序，因為始終沒有成功地進行分治，也就相當于總是整體地排序。同理，選到最大值也是一樣。