服务器之家

服务器之家 > 正文

Java实现快速排序过程分析

时间:2021-06-03 13:27     来源/作者:CGZ_PaPa

快速排序过程

没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”!光听这个名字是不是就觉得很高端呢。

假设我们现在对“52 39 67 95 70 8 25 52'”这个8个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数70作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在70的右边,比基准数小的数放在70的左边,类似下面这种排列:

 8 25 39 52 52' 67 70 95

在初始状态下,数字70在序列的第5位。我们的目标是将70挪到序列中间的某个位置,假设这个位置是k。现在就需要寻找这个k,并且以第k位为分界点,左边的数都小于等于70,右边的数都大于等于70。想一想,你有办法可以做到这点吗?

基本思想是分治的思想,说到分治,就应该想到和递归是分不开的。

有些书上会使用关键字比较的表述,有些书上会直接使用记录比较表述,这两种说法是两个维度上的说法。这里序列元素的关键字属于记录的一部分,为了简化问题,本文的讨论并不区分关键字和记录,代码实现中使用整数来表示记录。简而言之,本文的讨论简化为,对整型数组的快速排序。

通过一趟排序将要排序的记录分割成两部分,一部分的关键字值比别一部分的所有关键字都小,然后再依次对前后两部分的记录进行快速排序,递归该过程,直到序列中所有记录都是有序为止。

步骤

1)分解。选择第一个元素作为基准数,将输入序列array[m…n]划分成两个非空序列array[m…k]和array[k+1…n],使array[m…k]中任一元素的值不大于array[k+1…n]任一元素值。

2)递归求解。通过递归调用快排算法分别对array[m…k]和array[k+1…n]进行排序

3)合并。由于对分解出的两个子序列排序都是原地进行的,所以在array[m…k]和array[k+1…n]都排好序后不需要再执行任何计算,就能将array[m…n]排好序。因此这一步是不需要在程序中体现的。

排序过程分析

初始关键字:52 39 67 95 70 8 25 52' ,下面将列出每一趟执行的结果。

基准52: 52 39 67 95 70 8 25 52'

基准25: 8 25 39 52 70 95 67 52‘

基准70: 8 25 39 52 52' 67 70 95

基准52‘:8 25 39 52 52' 67 70 95

算法分析

快速排序的时间复杂度与关键字初始序列有关。

最坏时间复杂度:o(n^2):

以第一个数或最后一个数为基准时,当初始序列整体或局部有序时,快速排序的性能会下降。若整体有序,此时,每次划分只能分出一个元素,具有最坏时间复杂度,快速排序将退化成冒泡排序。

最好时间复杂度:

每次选取的基准关键字都是待排序列的中间值,也就是说每次划分可以将序列划分为长度相等的两个序列。快速排序的递归过程可以用一棵二叉树来表示,递归树的高度是2为底的对数,每层需要比较的次数是n/2,所以最好时间复杂度是o(n*以2为底n的对数),因为很多时候输入序列都是乱序的,所以最好时间复杂度也是平均时间复杂度。

三种快排和四种优化方法

三种快排

这里区分的方式是不同基准的选择方法:

1)固定位置,取第一个或最后一个元素作为基准。这种选取方法不合适局部有序的输入。

2)随机选取基准,利用随机算法,选取待排序序列中任意一个元素作为基准。

3)三数取中,取数列中第一个数,中间位置的数,最后一个数作一个平均值作为基准。

四种优化

1)当排序序列长度分割到一定程度时,使用插入排序

对于n很小或局部有序的数组,直接插入排序的效率非常高。

2)在一次分割结束后,可以把与基准数相等的元素聚在一起,下次分割时忽略掉这些元素。

对于含有重复元素比较多的序列,这种优化方法效果比较好,可以减少很多跌代次数。

具本过程:

第一步:在划分过程,把与所选取的基准数相等的元素放在数组的两端。

第二步:划分结束后,把两端的与基准数相等的元素移到基准数最终位置的两侧。

3)优化递归操作。

4)使用多线程并行处理子划分。

partition方法在求topk问题上的应用

topk问题即求序列中最大或最小的k个数。这里以求最小k个数为例。

快速排序的思想是使用一个基准元素将数组划分成两部分,左侧都比基准数小,右侧都比基准数大。

给定数组array[low…high],一趟快排划分后的结果有三种:

1)如果基准数左侧元素个数q刚好是k-1,那么在基准数左侧(包含基准数本身),即为topk的所有元素。

2)如果基准数左侧元素个数q小于k-1,那么说明基准数左侧的q个数都是topk里的元素,只需要在基准数的右侧找出剩下的k-q个元素即可。问题转化成了以基准数下标为起点,高位(high)为终点的top(k-q)。递归下去即可。

3)如果基准数左侧元素个数q大于k-1,说明第k个位置,在基准数的左侧,需要缩小搜索范围,在低位(low)至基准数位置重复递归即可,最终问题会转化成上面两种情况。

快排java实现

在手写快排算法时,最好先把一趟排序的过程写出来。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package sort;
public class quicksort {
 // 暴露只一个参数的公共接口
 public void quicksort(int a[]) {
 sort(a, 0, a.length - 1);
 }
 // 快排算法的真正实现
 private void sort(int[] a, int low, int high) {
 if (low >= high)
 return;
 int i = low, j = high; // 设置这两个变量的目的是为了保持low和high不变
 int pivotnum = a[i]; // 基准数
 while (i < j) {
 while (a[j] >= pivotnum && j > i) { // 循环结束的条件有二:一是找到比支点小的数,二是j==i
 j--;
 }
 if (j > i) { // 由于上面循环结束的功能性有两个,对于找到比支点小的数,即j!=i,要进行位置的交换,下同
 a[i] = a[j];
 i++;
 }
 while (a[i] < pivotnum && i < j) {
 i++;
 }
 if (i < j) {
 a[j] = a[i];
 j--;
 }
 }
 a[i] = pivotnum;
 sort(a, low, i - 1);
 sort(a, i + 1, high);
 }
 public static void main(string[] args) {
 int[] a = { 52, 39, 67, 95, 70, 8, 25, 52 };
 new quicksort().quicksort(a);
 for (int i : a) {
 system.out.print(i + " ");
 }
 }
}

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对服务器之家的支持。如果你想了解更多相关内容请查看下面相关链接

原文链接:https://blog.csdn.net/joson793847469/article/details/52738983

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部