快速排序法（详解）

作者：人工智能逻辑思维 | 2024-01-29 20:39:53

踩

快速排序

假设对以下10个数进行快速排序：

我们先模拟快速排序的过程：首先，在这个序列中随便找一个数作为基准数，通常为了方便，以第一个数作为基准数。

在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置是 $k$ 。现在就需要寻找这个 $k$ ，并且以第k位为分界点，左边的数都 $\le6$ ，右边的数都 $\ge6$ 。那么如何找到这个位置 $k$ 呢？

我们要知道，快速排序其实是冒泡排序的一种改进，冒泡排序每次对相邻的两个数进行比较，这显然是一种比较浪费时间的。

而快速排序是分别从两端开始”探测”的，先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量 $i$ 和 $j$ ，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵 $i$ ”和“哨兵 $j$ ”。刚开始的时候让哨兵 $i$ 指向序列的最左边，指向数字6。让哨兵 $j$ 指向序列的最右边，指向数字8。

6	1	2	7	9	3	4	5	10	8
i

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/44768