快速排序（QuickSort）是常见的排序算法，通过将排序问题分解为较小的子问题来进行排序

一：定义

1：选择一个基准元素（通常是数组的第一个或最后一个元素），将数组分成两个子数组，一个包含比基准元素小的元素，另一个包含比基准元素大的元素。

2：:递归地对两个子数组进行快速排序

二：步骤

1：选择一个基准元素（例如，第一个元素）。

2：遍历数组，将比基准元素小的元素放在一个左子数组中，将比基准元素大的元素放在一个右子数组中。

3：递归地对左子数组和右子数组进行快速排序。

4：合并左子数组、基准元素和右子数组，形成排序后的数组。

三：代码

const arr = [7, 2, 5, 1, 9, 3];
//第一步 选择基准元素7
//第二步 分成两个自数组，小放左[2, 5, 1, 3] ，大放右[9]
//第三步 递归对左右数组进行快速排序
//第四步，指回第一步，又找基准元素，变成左[1]右[5, 3]
//左边比较完，然后对右边开始递归比较
...
//直到空数组
//第五步 合并左子数组和右子数组

四：总结

1：时间复杂度为O(n log n):

2：平均情况下具有较好的性能

3：原地排序（in-place sorting），并且在大多数情况下具有较高的效率。然而，最坏情况下的时间复杂度为 O(n^2)，当输入数组已经有序或近乎有序时，快速排序的性能可能会下降

4：需要原地排序且对时间复杂度有较高要求，可以选择快速排序