图解快速排序_Java_Woo_home的博客-CSDN博客

时间:2020-03-07 来源:www.adxplorer.com.cn

什么是快速分类的文章目录?深思熟虑的动画演示代码实现了

什么是快速排序?

Quicksort是对冒泡排序的改进

quick sort是由霍尔在1960年提出的。其基本思想是通过一次排序将待排序的数据分成两个独立的部分,其中一部分中的所有数据都小于另一部分中的所有数据,然后根据这种方法分别对这两部分数据进行快速排序。整个排序过程可以递归地进行,这样整个数据就变成了一个有序的序列

思路

假设我们现在正在排序10个数字(6 1 2 7 9 3 4 5 10 8)。首先,在这个序列中随机找到一个数字作为轴点。为了方便起见,让第一个数字6作为参考数字。接下来,该序列中所有大于参考号的数字都需要放在6的右侧,小于参考号的数字需要放在6的左侧,类似于下面的sort

在初始状态,数字6位于序列的第一个位置。我们的目标是将6移动到序列中间的某个位置,假设这个位置是k,我们现在需要找到这个k,以第k位为分界点,左边是6或更少,右边是6或更多。该方法实际上非常简单:从初始序列的两端开始检测(6 1 2 7 9 3 4 5 10 8)。首先从右到左找出一个小于6的数字,然后从左到右找出一个大于6的数字,并交换它们。

我相信聪明人看完这部动画后已经学会了

我相信聪明人看完这部动画后已经学会了

了。快速排序之所以更快,是因为与冒泡排序相比,每个交换都在跳跃。每次

设置参考点排序时,小于或等于参考点的所有数字都放在参考点的左边,大于或等于参考点的所有数字都放在参考点的右边。这样,每次交换就不会像冒泡排序一样,相邻号码之间只能交换

行,交换距离会大得多。因此,比较和交流的总数将减少,速度自然会提高。当

但在最坏的情况下,仍然有可能交换两个相邻的号码。因此,快速排序的最差时间复杂度与

bubble排序相同,都是0(N2),其平均时间复杂度为0(NlogN)。事实上,快速排序是基于一个名为“二分法”的