快速排序

这篇文章发表于 2021年11月28日,星期日,13:58

快速排序就是在数组中选择一个数temp作为基准,每次排完之后比temp大的在其右边,比temp小的在其左边。

有如下数组 A = [3, 6, 8, 2, 7, 5];

1、 首先从右向左移动

2、当右指针移动到2的时候,2比3小,停止移动

3、从左往右移动左指针,到6时,6比3大,停止移动

4、交换数据,交换6和2的位置

5、再次把右指针从右往左移动,到2时,因为2比3小,停止移动,此时左指针右指针相遇,本次循环结束

6、 交换3(temp)与2的位置,本次排序后的顺序如下

以上是经历过一次循环排序的结构,3的左边只有2, 右边8、6、7、5均比3大,再把左右两边的数据进行排序,依次递归下去。

下面是代码

function QuickSort(arr, begin, end) { if (begin >= end) { return; } let l = begin; let r = end; let flag = arr[begin]; while( l < r) { while(arr[r] >= flag && r > l) { r--; } while(arr[l] <= flag && l < r) { l++; } [arr[l], arr[r]] = [arr[r], arr[l]]; } [arr[l], arr[begin]] = [arr[begin], arr[l]]; QuickSort(arr, begin, l - 1); QuickSort(arr, l + 1, end); } var a = [3, 6, 8, 2, 7,5]; QuickSort(a, 0, a.length - 1); console.log(a);