【Java】数据结构-快速排序（完整代码）

快速排序执行耗时结果截图

快速排序执行（完整代码）

QuickSort.java（进行了三层优化之后的算法时间进行比较）

import java.util.Arrays;
import java.util.Random;

public class QuickSort {

    private QuickSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr){
        Random rnd = new Random();
        sort(arr, 0, arr.length-1, rnd);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l , int r, Random rnd){

        if(l >= r) return;

        int p = partition(arr, l , r, rnd);
        sort(arr, l, p-1, rnd);
        sort(arr, p+1 , r, rnd);
    }

    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r, Random rnd){

        //生成[l,r]之间的随机索引
        int p = l + rnd.nextInt(r-l+1);
        swap(arr, l , p);
        // arr[l+1...j] < v; arr[j+1...i] >v
        int j=l;
        for(int i = l + 1; i<= r; i++){
            if(arr[i].compareTo(arr[l]) < 0){
                j ++;
                swap(arr, j, i);
            }
        }
        swap(arr, l,j);
        return j;

    }

    public static <E extends Comparable<E>> void sort2ways(E[] arr){
        Random rnd = new Random();
        sort2ways(arr, 0, arr.length-1, rnd);
    }

    private static <E extends Comparable<E>> void sort2ways(E[] arr, int l , int r, Random rnd){

        if(l >= r) return;

        int p = partition2(arr, l , r, rnd);
        sort2ways(arr, l, p-1, rnd);
        sort2ways(arr, p+1 , r, rnd);
    }

    private static <E extends Comparable<E>> int partition2(E[] arr, int l, int r, Random rnd){

        //生成[l,r]之间的随机索引
        int p = l + rnd.nextInt(r-l+1);
        swap(arr, l , p);
        // arr[l+1...j] < v; arr[j+1...i] >v
//        int j=l;
//        for(int i = l + 1; i<= r; i++){
//            if(arr[i].compareTo(arr[l]) < 0){
//                j ++;
//                swap(arr, j, i);
//            }
//        }
//        swap(arr, l,j);
//        return j;

        // arr[l+1...i-1] <= v; arr[j+1...r] >= v
        int i = l+1 , j = r;
        while(true){

            while(i <= j && arr[i].compareTo(arr[l]) < 0)
                i ++;
            while(j >= i && arr[j].compareTo(arr[l]) > 0)
                j --;

            if(i >= j) break;

            swap(arr, i , j);
            i ++;
            j --;
        }
        swap(arr, l , j);
        return j;
    }

    public static <E extends Comparable<E>> void sort3ways(E[] arr){
        Random rnd = new Random();
        sort3ways(arr, 0, arr.length-1, rnd);
    }

    private static <E extends Comparable<E>> void sort3ways(E[] arr, int l , int r, Random rnd){

        if(l >= r) return;

        //生成[l,r]之间的随机索引
        int p = l + rnd.nextInt(r-l+1);
        swap(arr, l , p);

        // arr[l + 1, lt] < v, arr[lt + 1, i - 1] == v , arr[gt, r] > v
        int lt = l , i = l + 1, gt = r + 1; //初始空区间
        while(i < gt){

            if(arr[i].compareTo(arr[l])<0){
                lt ++;
                swap(arr, i , lt );
                i ++;
            }
            else if(arr[i].compareTo(arr[l])>0){
                gt --;
                swap(arr, i, gt);
            }
            else{ // arr[i] == arr[l]
                i ++;
            }
        }
        swap(arr,l ,lt);
        // arr[l, lt - 1 ] < v, arr[lt , gt - 1] == v, arr[gt, r ] > v
        sort3ways(arr, l , lt-1, rnd);
        sort3ways(arr, gt , r, rnd);
    }


    private static <E> void swap(E[] arr, int i , int j){

        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }



    public static void main(String[] args) {

        int n = 10000000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);

        SortingHelper.sortTest("QuickSort", arr);
        SortingHelper.sortTest("QuickSort2", arr2);

        arr = ArrayGenerator.generateOrderedArray(n);
        arr2 = Arrays.copyOf(arr, arr.length);

        SortingHelper.sortTest("QuickSort", arr);
        SortingHelper.sortTest("QuickSort2", arr2);

        arr = ArrayGenerator.generateRandomArray(n, 1);
        arr2 = Arrays.copyOf(arr, arr.length);
        Integer[] arr3 = Arrays.copyOf(arr, arr.length);
        SortingHelper.sortTest("QuickSort2", arr2);
        SortingHelper.sortTest("QuickSort3", arr3);





    }
}

ArrayGenerator.java(生成随机n个元素的数组)

import java.util.Random;

public class ArrayGenerator {

    private ArrayGenerator(){}

    public static Integer[] generateOrderedArray(int n){

       Integer[] arr = new Integer[n];
       for(int i = 0; i < n ; i++)
           arr[i] = i;
       return arr;
    }

    // 生成一个长度为 n 的随机数组， 每个数字的范围是[ 0 , bound)
    public static Integer[] generateRandomArray(int n, int bound){

        Integer[] arr = new Integer[n];
        Random rnd = new Random();
        for(int i = 0 ; i < n; i++)
            arr[i] = rnd.nextInt(bound); //从0到bound前闭后开
        return arr;
    }
}

SortingHelper.java（辅助进行算法时间输出的）

public class SortingHelper {

    private SortingHelper(){} //私有类

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){

        for(int i = 1; i< arr.length; i++)
            if (arr[i - 1].compareTo(arr[i]) > 0)
            return false;
        return true;
    }

    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
        long startTime = System.nanoTime();
        if(sortname.equals("SelectionSort")) {
            SelectionSort.sort(arr);
        } else if(sortname.equals("InsertionSort"))
            InsertionSort.sort(arr);
        else if(sortname.equals("InsertionSort2"))
            InsertionSort.sort2(arr);
        else if(sortname.equals("MergeSort"))
            MergeSort.sort(arr);
        else if(sortname.equals("MergeSort2"))
            MergeSort.sort2(arr);
        else if(sortname.equals("MergeSort3"))
            MergeSort.sort3(arr);
        else if(sortname.equals("MergeSort4"))
            MergeSort.sort4(arr);
        else if(sortname.equals("MergeSortBU"))
            MergeSort.sortBU(arr);
        else if(sortname.equals("QuickSort"))
            QuickSort.sort(arr);
        else if(sortname.equals("QuickSort2"))
            QuickSort.sort2ways(arr);
        else if(sortname.equals("QuickSort3"))
            QuickSort.sort3ways(arr);
        long endTime = System.nanoTime();

        double time = (endTime - startTime) / 1000000000.0; //纳米要/9个零

        if(!SortingHelper.isSorted(arr))
            throw new RuntimeException(sortname + "failed");
        System.out.println(String.format("%s , n = %d : %f s ", sortname, arr.length, time));
    }
}

我的个人博客

孤桜懶契：http://gylq.github.io