简介：

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

它的基本思想是：首先选择一个关键数据作为基准，通过一趟排序将要排序的数据分割成独立的两部分，其中左边的数据小于或等于基准，右边的数据大于或等于基准，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以进行，以此达到整个数据变成有序。

 

实现：

package suanfa;/* * 快速排序 */public class QuickSort {     public static void sort(int a[], int low, int hight) {        if (low > hight) {            return;        }        int i, j, key;        i = low;        j = hight;        key = a[i]; // 用第一个元素作为基准        while (i < j) { // 从表的两端交替向中间扫描            while (i < j && a[j] >= key) {                j--;            }            if (i < j) {                a[i] = a[j];                i++;            }            while (i < j && a[i] < key) {                i++;            }                            if (i < j) {                      a[j] = a[i];               j--;            }                 }                a[i] = key;//将基准数值替换回 a[i]                          sort(a, low, i - 1); //递归调用，把key前面的完成排序               sort(a, i + 1, hight); //递归调用，把key后面的完成排序           }     public static void print(int src[]) {         for (int i = 0; i < src.length; i++) {                         System.out.print(src[i] + " ");            }         System.out.println();    }         public static void main(String[] args) {        int a[] = {6,2,7,3,8,9};        print(a);        sort(a, 0, a.length - 1);        print(a);     }}

 

分析：

在快速排序算法中，比较关键的一个部分是主元的选择。

在最差情况下，划分由n个元素构成的数组需要进行n次比较和n次移动，因此划分需要的时间是O(n)。在最差情况下，每次主元会将数组划分为一个大的子数组和一个空数组，这个大的子数组的规模是在上次划分的子数组的规模上减1，这样在最差情况下算法需要(n-1)+(n-2)+...+1= O(n^2) 时间。

最佳情况下，每次主元将数组划分为规模大致相等的两部分，时间复杂度为 O(nlogn) 。