java排序算法（五）：快速排序

　　快速排序是一个速度非常快的交换排序算法，它的基本思路很简单，从待排的数据序列中任取一个数据（如第一个数据）作为分界值，所有比它小的元素放到左边。所有比它大的元素放到右边。经过这样一趟下来，该序列形成左右两个子序列，左边序列中的数据元素的值都比分界值小，右边序列中数据元素的值都比分界值大。接下来对左右两个序列进行递归排序。对两个子序列重新选择中心元素并依此规则调整。直到每个元素子表的元素只剩下一个元素则排序成功

　　思路

　　1、定义一个变量 i变量从左边第一个索引开始，找大于分界值的元素的索引，并用i来记录它。

　　2、定义一个j变量，j变量从右边第一个索引开始，找小于分界值的元素的索引，并用j来记录它。

　　3、如果i < j,交换i、j两个索引处的元素

　　重复执行以上1、2、3步骤，直到i>=j,可以判断j左边的数据元素都小于分界值，j右边的数据元素都大于分界值，最后将分界值j索引处的元素交换即可

　　时间复杂度

　　最好情况（每次总是选到中间值枢轴）Tn = o(nlogn)

　　最坏情况：（每次总是选到最小或者最大元素作为枢轴）

　　做n-1趟，每次比较n-i次。总的比较次数最大；[o(n2)]

　　平均时间复杂度是T(n) = o(logn)

　　代码实现

　　

package com.spring.test;import com.sun.org.apache.bcel.internal.generic.SWAP;import java.awt.print.PrinterGraphics;/** * 快速排序 */public class QuickSortTest {    public static void main(String[] args) {        int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };        print(data);        quickSort(data,0,data.length-1);        System.out.println("排序后的数组");        print(data);    }    /**     * 快速排序     * @param data     * @param start     * @param end     */    public static void quickSort(int[] data,int start,int end){        if(start >= end){            return;        }        //以起始索引为临界点        int point = data[start];        int i = start + 1;        int j = end;        while(true){            while(i
     
       start && data[j] > point){                j--;            }            if(i < j){                swap(data,i,j);            }else{                break;            }        }        //交换j和分界点的值        swap(data,start,j);        print(data);        //递归在子序列        quickSort(data,start,j-1);        quickSort(data,j+1,end);    }    /**     * 交换数据     */    public static void swap(int[] data,int i,int j){        if(i==j){            return;        }        data[i] = data[i]+data[j];        data[j] = data[i]-data[j];        data[i] = data[i]-data[j];    }    /**     * 打印输出     */    public static void print(int[] data){        for(int i=0;i
     

 

运行结果