快速排序

测试了一下，当数据量为十万的时候，快速排序 是冒泡排序的100倍左右

package com.cts.elt.sort;

import java.util.Arrays;

public class FastSortTest {

    public int[] arr;

    public void sort(){


        quickSort(0,arr.length-1);

    }

    public void quickSort(int left,int right){

        int size =right-left+1;

        if (size<10){


            insertSort(left,right);
            return;

        }
        int compare =getMedium(left,right);

        int pattion =  pattionSort(left,right,compare);

        quickSort(left,pattion-1);

        quickSort(pattion+1,right);
    }


    public int pattionSort(int left,int right,int compare){

        int leftPtr =left;

        int rightPtr=right-1;

        while (true){

            while (arr[++leftPtr]<compare);

            while (rightPtr>0&&arr[--rightPtr]>compare);

            if (leftPtr>=rightPtr)
                break;

            if (arr[leftPtr]>arr[rightPtr])
                swap(leftPtr,rightPtr);

        }
        swap(leftPtr,right-1);
        return leftPtr;
    }

    public void swap(int left,int right){

        int t =arr[left];
        arr[left]=arr[right];
        arr[right] =t;

    }

    public void insertSort(int left,int right){

        int out;
        int in;
        for (out=left+1;out<=right;out++){
            in =out;
            int temp =arr[out];
            while (in>left&&arr[in-1]>temp){

                arr[in] =arr[in-1];

                in--;

            }
            arr[in] =temp;
        }


    }

    public int getMedium(int left,int right){

        int center =(left+right)>>>1;

        if (arr[left]>arr[center])
            swap(left,center);

        if (arr[left]>arr[right])
            swap(left,right);

        if (arr[center]>arr[right])
            swap(center,right);

        swap(center,right-1);

        return arr[right-1];

    }

    public static void main(String[] args){

        int size =1000;
        int[] arr =new int[size];

        for (int i=0;i<size;i++){

            arr[i]=(int)(Math.random()*size);
        }

        FastSortTest fastSort =new FastSortTest();
        fastSort.arr =arr;
//        fastSort.arr =new  int[]{7, 5, 5, 1, 7, 3, 1, 8, 9, 8};

        System.out.println("原数组");
        long startTime= System.currentTimeMillis();
        System.out.println(Arrays.toString(fastSort.arr));
        fastSort.sort();
        long endTime= System.currentTimeMillis();

        long time =endTime -startTime;
        System.out.println("时间"+time);
        System.out.println("排序以后数组"+(endTime-startTime));
        System.out.println(Arrays.toString(fastSort.arr));
//        System.out.println("次数="+fastSort.count);

//        long startTime= System.currentTimeMillis();
//         MaopaoSort maopaoSort =new MaopaoSort();
//        maopaoSort.arr =arr;
//        maopaoSort.sort();
//
//        long endTime= System.currentTimeMillis();
//
//        long time =endTime -startTime;
//        System.out.println("时间"+time);



    }


}