实现快速排序

[nmsn]

No description provided.

[nmsn]

容易理解的版本

但是是非原地快排，需要占用额外的空间

function quickSort(array) {
  if (array.length <= 1) {
    return array;
  }

  const pivotIndex = Math.floor(array.length / 2);
  const pivotValue = array[pivotIndex];
  const left = [];
  const right = [];

  for (let i = 0; i < array.length; i++) {
    if (i === pivotIndex) {
      continue;
    }
    const current = array[i];
    current < pivotValue ? left.push(current) : right.push(current);
  }

  return [...quickSort(left), pivotValue, ...quickSort(right)];
}

缺点是会额外使用空间

[nmsn]

原地排序版本

function quickSort(arr) {
    function swap(arr, i, k) {
        let temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }

    // 数组分区，左小右大
    function partition(arr, left, right) {
        let storeIndex = left;
        let pivot = arr[right]; // 直接选最右边的元素为基准元素
        for(let i = left; i < right; i++) {
            if(arr[i] < pivot) {
                swap(arr, storeIndex, i);
                storeIndex++; // 交换位置后，storeIndex 自增 1，代表下一个可能要交换的位置
            } 
        }
        swap(arr, storeIndex, right); // 将基准元素放置到最后的正确位置上
        return storeIndex;
    }

    function sort(arr, left, right) {
        if(left > right) {
            return;
        }
        let storeIndex = partition(arr, left, right);
        sort(arr, left, storeIndex - 1);
        sort(arr, storeIndex + 1, right);
    }

    sort(arr, 0, arr.length - 1);
    return arr;
}

[nmsn]

快速排序（Quick Sort）是一种常用的排序算法，其平均时间复杂度为 O(n log n)。这意味着在平均情况下，快速排序的运行时间与要排序的元素数量的乘积成正比。

具体来说，快速排序的时间复杂度可以用以下递推式表示：

T(n) = T(k) + T(n-k-1) + O(n)

其中，T(n) 表示对 n 个元素进行排序所需的时间。

在最佳情况下，即每次划分都能均匀地将数组分成两个近似相等的子数组时，快速排序的时间复杂度可以达到 O(n log n)。而在最坏情况下，即每次划分只能将数组分成一个较大的子数组和一个较小的子数组时，快速排序的时间复杂度退化为 O(n^2)。

然而，通过选择合适的划分元素（如随机选择、三数中值法等），可以有效地降低最坏情况的概率，从而减少快速排序的时间复杂度接近平均情况的性能。

需要注意的是，快速排序的空间复杂度为 O(log n)，因为它需要递归调用并使用栈空间来存储中间结果。但在最坏情况下，递归深度可能达到 n，导致空间复杂度为 O(n)。