【JAVA】快速排序

快速排序的概念：

快速排序（Quicksort）是对冒泡排序的一种改进。

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

一趟快速排序的算法：

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

此过程可以理解为按个子排队。

代码：

package 排序方法;

public class QuickSort {
    public static void Qs(int[] arr, int n, int m) {
        //定义一个数组，其中s为它的其实索引（通常定义为0）
        //x为它的结束索引（通常为array.length-1)

        if (n >= m) {
            // 递归结束条件：s>=x的时候
            return;
        }
        
        // 否则得到基准元素位置，也就是对换的元素
        int pivot= part(arr, n, m);
        // 用分治法递归数列的两部分
        Qs(arr, n, pivot - 1);
        Qs(arr, pivot + 1,m);
    }

    private static int part(int[] arr, int n, int m) {
        // 取第一个位置的元素作为基准元素
        int pivot = arr[n]; 
        // 初始等于pivot的位置
        int left = n;
        int right = m;
       
        int index = n;

        while (right >= left) {
            // 大在左右指针重合或者交错时结束
            while (right >= left) {
                if (arr[right] < pivot) {
                    arr[left] = arr[right];
                    index = right;
                    left++;
                    break;
                }
                right--;
            }
            // left指针从左向右进行比较
            while (right >= left) {
                if (arr[left] > pivot) {
                    arr[right] = arr[left];
                    index = left;
                    right--;
                    break;
                }
                left++;
            }
        }
        arr[index] = pivot;
        return index;
    }
    public static void main(String[] args) {
        int[] arr = { 80, 83, 84, 87, 61, 50, 70, 60, 88, 99};
        Qs(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]+"");
        }
    }
}

50 60 61 70 80 83 84 87 88 99

复杂度分析：
（1）最坏时间复杂度 
最坏情况是指每次区间划分的结果都是基准关键字的左边（或右边）序列为空，而另一边区间中的记录仅比排序前少了一项，即选择的关键字是待排序记录的最小值或最大值。最坏情况下快速排序的时间复杂度为。 
（2）最好时间复杂度 
最好情况是指每次区间划分的结果都是基准关键字的左右两边长度相等或者相差为1，即选择的基准关键字为待排序的记录的中间值。此时进行比较次数总共为 nlogn，所以最好情况下快速排序的时间复杂度为。 
（3）平均时间复杂度 
快速排序的平均时间复杂度为。在所有平均时间复杂度为O(nlogn)的算法中，快速排序的平均性能是最好的。 
（4）空间复杂度 
快速排序的过程中需要一个栈空间来实现递归。最好情况，递归树的深度为，其空间复杂度也就是O(nlogn)；最坏情况下，需要进行 n-1次递归，其空间复杂度为O(n)；平均情况，空间复杂度为O(nlogn). 
（5）基准关键字的选取，基准关键字的选取是决定快速排序算法的关键，常用的基准关键字的选取方式如下： 
第一种：三者取中。将序列首、尾和中间位置上的记录进行比较，选择三者中值作为基准关键字。 
第二种：取left和right之间的一个随机数，用n[m]作为基准关键字。采用这种方法得到的快速排序一般称为随机的快速排序。