快速排序过程
没有既不浪费空间又可以快一点的排序算法呢？那就是“快速排序”！光听这个名字是不是就觉得很高端呢。
假设我们现在对“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
