java快速排序法

2018年9月6日01:51:56 评论 651

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

1、快速排序思想及原理

事实上,快速排序是堆冒泡排序的一种改进。
它的基本思想是:通过一趟排序将要排序的数据分割为两部分,第一部分所有数据比第二部分的所有数据小,按照这种思路将两部分数据再次分别进行快速排序,可以使用递归完成,最终使得整个数据序列有序。

具体来讲,在待排数据中找一个基准数据(通常取第一个数),接下来将待排数据中比基准数据小的放在待排数据的左侧,将比待排数据中比基准数据大的放在待排数据右侧。此时,左右两个分区的元素相对有序,接着采用上述思路继续对左右两个分区继续排序,直到各分区只有一个元素位置。这里用到了一个典型的分治思想。

下面我们用图解的方式来演示这个排序过程:

假设下面这个数组是待排序数组:

(6, 1, 2, 7, 9, 3, 4, 5, 10, 8)

按照快速排序的思想,首先得把这组数分成相互独立的两部分,其中一部分比中的数比另一部分的数都小。如何实现这一步呢?

方法其实很简单:首先选取待排序数组的第一个数为基准数,也就是6,然后分别从初始序列“(6,1,2,7,9,3,4,5,10,8)”两端开始“探测”。先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们。这里可以用两个变量i和j,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边(即i=1),指向数字6。让哨兵j指向序列的最右边(即j=10),指向数字8。

首先哨兵j开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵j先出动,这一点非常重要(请自己想一想为什么)。哨兵j一步一步地向左挪动(即j--),直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动(即i++),直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前,哨兵i停在了数字7面前。

现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列为(6, 1, 2, 5, 9, 3, 4, 7, 10, 8)。

接下来开始哨兵j继续向左挪动(再友情提醒,每次必须是哨兵j先出发)。他发现了4(比基准数6要小,满足要求)之后停了下来。哨兵i也继续向右挪动的,他发现了9(比基准数6要大,满足要求)之后停了下来。此时再次进行交换,交换之后的序列为(6, 1, 2, 5, 4, 3, 9, 7, 10, 8)。

哨兵j继续向左挪动,他发现了3(比基准数6要小,满足要求)之后又停了下来。哨兵i继续向右移动,糟啦!此时哨兵i和哨兵j相遇了,哨兵i和哨兵j都走到3面前。说明此时“探测”结束。3比6小所以我们将基准数6和3进行交换。交换之后的序列为(3, 1, 2, 5, 4, 6, 9, 7, 10, 8)。

此时第一趟排序结束,我们已经把待排序数组分成了以6为基准,左边一列序列,右边一序列,左边序列的数比右边序列的数都小。不过此时左右两部分中的数各自的排序仍然是混乱的,还要继续排序。

快速排序的排序过程已经通过上面的图解讲解清楚了,接下来左右两部分的数据继续按照快速排序的方式来排序。

下面举例说明:

待排序列依次为3、5、7、2、11、6、1、3、8、4、10、12。

2、java快排代码

3、快排的特点及性能

快排是在冒泡排序之上改进而来的,冒泡排序每次只能交换相邻的两个元素,而快排则是跳跃式的交换,交换距离很大,总的比较次数和交换次数少了很多,速度也快了很多。
快排的平均时间复杂度为O(nlogn),事实上,大多数情况下,排序速度要快于这个时间复杂度。快排实际上是采用的一种分而治之的思想,把问题分解为一个个的小问题去逐一解决,最终在把结果组合起来。
快排因为递归调用,所以空间复杂度为O(logn)。
快排是一种不稳定的排序算法,在经过排序后,等值的元素的相对位置可能发生改变。
快排基本上被认为是相同数量级中所有排序算法中平均性能最好的。

4、快排的适用场景

快排由于相对简单而且性能不错,所以快排适用于几乎绝大多数场合。

本文已通过「原本」原创作品认证,未经作者授权请勿直接转载,负责将依法追究其法律责任。
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: