欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java实现快速排序过程分析

程序员文章站 2024-02-26 19:14:58
快速排序过程 没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”!光听这个名字是不是就觉得很高端呢。 假设我们现在对“52 39 67 95 70 8 25...

快速排序过程

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

假设我们现在对“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实现

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

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 + " ");
 }
 }
}

总结

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