快速排序

Quick Sort 排序算法——快速排序

基础介绍

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

思路图解

第一轮找基准分两组后，以基准为界将比基准大的放在右边，比基准小的放在左边。然后交换完以后产生的左右两组在分别以第一轮的样子在交换，往下递归交换，最终有序，这个方法是非常典型的以空间换时间

代码

算法代码

此时，该算法有点不理解，代码仅仅只是会写，并没有真正领悟，代码旁边备注不够详细。

public static void quickSort ( int[] arr,int left,int right) {
    int l=left; //左下标
    int r=right; //右下标
    //pivot 中轴
    int pivot =arr[(left+right)/2];
    int temp ; //中间变量
    //while循环的目的是让比pivot的值小放到左边
    while (l<r){
        //在pivot的左边一直找，找到大于等于piovt值，才退出
        while (arr[l]<pivot){
            l++;
        }
        //在pivot的右边一直找，找到小于等于piovt值，才退出
        while (arr[ r ] > pivot) {
            r--;
        }
        //piovt左边小于piovt,piovt右边大于piovt,
        if ( l>=r ){
            break;
        }
        //交换
        temp=arr[l];
        arr[ l ] = arr[ r ];
        arr[ r ] = temp;

        //如果交换完后，发现这个arr[l]==piovt值 此时让r--，前移
        //说明到中点了，这样--或++使其退出循环
        if ( arr[ l ] == pivot ) {
            r--;
        }
        //如果交换完后，发现这个arr[r]==piovt值 此时让l++，后移
        if ( arr[ r ] == pivot ) {
            l++;
        }

    }
    //如果l==r ,必须l++，r--,否在出现栈溢出
    if ( l == r ) {
        l++;
        r--;
    }
    //向左递归
    if ( left<r ){
        quickSort ( arr, left, r );
    }
    //向右递归
    if ( right>l ){
        quickSort ( arr, l, right );
    }

}

推算

点我预览

这里有张图片：

性能测试

因为该算法处理排序较快，所以单以8万的数据量无法体现它的优越性，所以选择更加庞大的80万，按道理数据增大十倍，时间应该呈现几何式增长，单从肉眼看结果并没明显体现，这就说明它的优越性。

public class QuickSorting {
    public static void main ( String[] args ) {
        /*int[] arr = {-9, 78, 0, 23, -567, 70,-1,26,-567,256};

        quickSort ( arr, 0, arr.length - 1 );
        System.out.println ( "arr :" + Arrays.toString ( arr ) );*/
        int arr[] = new int[ 8000000 ];
        randomArr ( arr );
        System.out.println ( "插入排序所用时间" );
        String date1String = Date ( );
        System.out.println ( "排序前时间是：" + date1String );
        quickSort ( arr,0,arr.length - 1 );
        String date2String = Date ( );
        System.out.println ( "排序后时间是：" + date2String );
    }

    public static void quickSort ( int[] arr,int left,int right) {
        int l=left; //左下标
        int r=right; //右下标
        //pivot 中轴
        int pivot =arr[(left+right)/2];
        int temp ; //中间变量
        //while循环的目的是让比pivot的值小放到左边
        while (l<r){
            //在pivot的左边一直找，找到大于等于piovt值，才退出
            while (arr[l]<pivot){
                l++;
            }
            //在pivot的右边一直找，找到小于等于piovt值，才退出
            while (arr[ r ] > pivot) {
                r--;
            }
            //piovt左边小于piovt,piovt右边大于piovt,
            if ( l>=r ){
                break;
            }
            //交换
            temp=arr[l];
            arr[ l ] = arr[ r ];
            arr[ r ] = temp;

            //如果交换完后，发现这个arr[l]==piovt值 此时让r--，前移
            //说明到中点了，这样--或++使其退出循环
            if ( arr[ l ] == pivot ) {
                r--;
            }
            //如果交换完后，发现这个arr[r]==piovt值 此时让l++，后移
            if ( arr[ r ] == pivot ) {
                l++;
            }

        }
        //如果l==r ,必须l++，r--,否在出现栈溢出
        if ( l == r ) {
            l++;
            r--;
        }
        //向左递归
        if ( left<r ){
            quickSort ( arr, left, r );
        }
        //向右递归
        if ( right>l ){
            quickSort ( arr, l, right );
        }

    }
    private static void randomArr ( int[] arr ) {
        for ( int i = 0 ; i < arr.length ; i++ ) {
            arr[ i ] = (int) ( Math.random ( ) * 8000000 );  //会生成【0，8000000）直接的数
        }
    }

    /**
     * 将此时调用函数的时间格式化打出来
     *
     * @return 年-月-日 时-分秒
     */
    private static String Date ( ) {
        Date date1 = new Date ( );  //调函数的当前时间
        SimpleDateFormat simpleFormatter = new SimpleDateFormat ( "HH:mm:ss" );//格式化
        return simpleFormatter.format ( date1 );
    }


}

结果

后期，等排序学完，将7种常见排序进行速度比较。