·5 分钟阅读·管理员
排序算法-快速排序
快速排序(Quick Sort)是一种非常高效的排序算法,由 C. A. R. Hoare 在 1960 年代提出。它利用分治法(Divide and Conquer)的思想来进行排序。快速排序在平均情况下的时间复杂度为 O(n log n),但在最坏情况下可能会退化为 O(n^2)。 快速排序的基本步骤:快速排序的核心思想是通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所
JavaScript快速排序
孤独的我们才有人类的样子
排序算法-快速排序
快速排序(Quick Sort)是一种非常高效的排序算法,由 C. A. R. Hoare 在 1960 年代提出。它利用分治法(Divide and Conquer)的思想来进行排序。快速排序在平均情况下的时间复杂度为 O(n log n),但在最坏情况下可能会退化为 O(n^2)。
快速排序的基本步骤:
快速排序的核心思想是通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
- 选择基准:从数组中选择一个元素作为基准(pivot)。
- 分区操作:重新排列数组,使得所有比基准小的元素都排在基准前面,所有比基准大的元素都排在基准后面(相同的数可以到任一边)。在这个分割结束之后,该基准就处于数组的中间位置。
- 递归排序:递归地对左右两边的子数组进行快速排序。
- 一句话就是,小于基准点的放在左边,否则放在右边,最后递归合并
动画模拟

快速排序的实现:
-
返回新数组
- 在数据集之中,选择一个元素作为"基准"(pivot)
- 所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边
- 对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止
该方法是最简单也是最容易理解的,但是会**返回一个新的数组*
javascript/** * 快速排序 * 该方法是最简单也是最容易理解的,但是会返回一个新的数组 * @param arr{Array} */ const quickSortNew = (arr) => { if (arr.length <= 1) return arr let left = [] // 左侧的值,存放小于基准点 let right = [] // 左侧的值 存放大于基准点 const pivot = arr.splice(0, 1) // 选择第一个作为基准点 for (let i = 0; i < arr.length; i++) { if (arr[i] > pivot) { right.push(arr[i]) } else { left.push(arr[i]) } } // 递归,并将基准点拼接进去 return quickSortNew(left).concat([pivot], quickSortNew(right)); } console.log(quickSortNew([34, 10, 64, 51, 32, 21])); // 输出: [10, 21, 32, 34, 51, 64] console.log(quickSortNew([5, 1, 4, 2, 8])); // 输出: [1, 2, 4, 5, 8] console.log(quickSortNew([])); // 输出: [] console.log(quickSortNew([1])); // 输出: [1] console.log(quickSortNew([9, 7, 7, 3, 1, 2, 4])); // 输出: [1, 2, 3, 4, 7, 7, 9] -
改变原数组
javascript/** * 该方法使用的是以最后一个值为基准点, * @param arr{Array} * @param left * @param right */ const quickSort = (arr, left=0, right=arr.length-1) => { // 寻找基准点的位置 const partition = (_arr, _left, _right)=> { // 以右侧基准为例 const pivot = arr[_right]; let l = _left for (let j = _left; j < _right; j++) { // 当前的元素_arr[j]小于基准pivot时,才需要与前面适当的位置上的元素进行交换,以确保小于基准的元素都在基准左边。 // 这是因为我们的目标是在一轮遍历后,让基准元素到达其最终排序后的位置,并且保证基准左右两侧的元素顺序符合要求。 if (_arr[j] < pivot) { [_arr[l], _arr[j]] = [_arr[j], _arr[l]] l++ } } [_arr[l], _arr[_right]] = [_arr[_right], _arr[l]] return l } if (left < right) { const p = partition(arr, left, right) quickSort(arr, left, p-1) quickSort(arr, p+1, right) } return arr }
时间复杂度分析:
- 最好情况:每次都能均匀地分割数组,时间复杂度为 O(n log n)。
- 最坏情况:每次选择的基准都是最大或最小元素,导致分割不均匀,时间复杂度为 O(n^2)。
- 平均情况:时间复杂度为 O(n log n)。
尽管快速排序在最坏情况下效率较低,但在实际应用中,由于其平均性能很好,且具有原地排序的优点,因此它仍然是广泛使用的排序算法之一。为了避免最坏情况的发生,可以采取一些措施,如随机选择基准、三数取中法等。