快速排序算法为什么要双指针

JavaScript012

快速排序算法为什么要双指针,第1张

这是快速排序的思路决定的。快速排序的思想是这样的:

从数组中选取一个元素作为基准值,将待排序的数组分成左右两部分,左边的部分小于基准值,右边的部分大于基准值。左右两部分继续如此递归下去,不断分裂,直到待排序数组的元素为1,此时递归条件结束。

所以使用双指针交替向中间移动,左边的指针在比基准值大的下标时停下,右边的指针在比基准小的下标时停下,双方交换数组元素,继续向左、向右移动。

这一轮的移动到什么地方停止呢?那就是在左右指针下标值相等的时候,将这个下标值的元素与基准值元素交换。

一轮下来,这个基准值位置确定,就不会再发生改变了。以它为分界线,分成左右两部分,剩下的排序它都不用参与了。

分开了左右两段之后,我们把左右段看成各自独立的待排序数组就好,做法与上面一致,只不过此时的待排序数组比较短了。使用递归实现就非常方便。

在不断的分裂过后,待排序数组只为一个元素的时候,排序就结束了。

快速排序的思想总结: 设定pivot,通过左右双指针与pivot进行比较,若发现左边大于pivot,右边小于pivot,则进行左右数字位置对调,最终最终保证数组靠左侧数值都小于povit,数组靠右侧数值都大于pivot。

设定头部数字8位pivot(可自由设定);

(图解如下)

编码: