快速排序时间复杂度

快速排序是一种常用的排序算法，其时间复杂度为O(nlogn)，具有较高的效率和稳定性。快速排序采用了分治的思想，将一个大问题分成若干个小问题，然后分别解决，最后将结果组合起来。

快速排序的基本思路是：选择一个基准数，将数组分成两个部分，一部分比基准数小，一部分比基准数大，然后递归地对两个部分进行排序。

快速排序的时间复杂度分析

在最坏的情况下，即每次选择的基准数都是最大或最小值时，快速排序的时间复杂度会退化成O(n^2)。但是，在平均情况下，快速排序的时间复杂度为O(nlogn)。

假设待排序的数组长度为n，每次划分时，平均需要比较n次，所以总的比较次数为nlogn。而每次划分时，需要移动元素，每次移动的元素个数为n，所以总的移动次数也为nlogn。因此，快速排序的时间复杂度为O(nlogn)。

快速排序的优化

快速排序的时间复杂度虽然已经很优秀了，但是还有一些优化方法可以进一步提高效率：

1. 随机化选择基准数

在实际的应用中，如果每次选择的基准数都是最大或最小值，那么快速排序的效率会很低。因此，可以采用随机化的方法来选择基准数，减少最坏情况的出现。

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left