Java实现快速排序原理分析

Java实现快速排序过程

快速排序过程

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

假设我们现在对“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 + " ");
 }
 }
}