本文為原創(chuàng)文章，轉(zhuǎn)載請(qǐng)注明出處宵膨，謝謝你……
喜歡java并發(fā)編程的請(qǐng)加群：736156823
開(kāi)始-->

import java.util.concurrent.ThreadLocalRandom;

public class QSort {

    // 選擇樞軸時(shí)候要求數(shù)據(jù)個(gè)數(shù)大于3
    private static final int OFF_SIT = 3;
    // 選擇快排還是插入的界限
    private static final int INSERT_FLAG = 13;

    // 數(shù)組的有效下標(biāo)
    public void sort(int[] array, int left, int right) {
        // 一些無(wú)用的校驗(yàn)
        if (null == array) {
            return;
        } else if (array.length <= 1) {
            return;
        } else if (left < 0 || right < 0) {
            return;
        } else if (right - left <= 1) {
            return;
        } else {
            quick(array, left, right);
        }
    }

    private void quick(int[] array, int left, int right) {
        // 如果數(shù)組中的數(shù)據(jù)太少皱炉，使用插入排序
        // 根據(jù)下面選擇樞軸的方法，太少也是不允許的
        // 大量實(shí)驗(yàn)證明，數(shù)據(jù)在5到20內(nèi)的數(shù)據(jù)另萤，插入排序快于快速排序
        // 這里選擇的是13梯影，實(shí)驗(yàn)發(fā)現(xiàn)13比較好
        if (left + OFF_SIT <= right) {
            if (left + INSERT_FLAG <= right) {
                int p = partition(array, left, right);
                // 實(shí)際比較是從left-1巫员，right-2開(kāi)始的
                // 因?yàn)閘eft，right-1甲棍，right三者已經(jīng)有序
                // 具體參考樞軸的選擇策略partition
                int i = left, j = right - 1;
                for (; ; ) {
                    for (; ; ) {
                        // 直接加就好了简识，不需要判斷是否越界
                        // 原因就是有三個(gè)數(shù)已經(jīng)控制了邊界
                        i = i + 1;
                        // 這里說(shuō)明下:
                        // 為什么大于或者等于都要停止指針移動(dòng)？
                        // 因?yàn)榇罅繉?shí)驗(yàn)發(fā)現(xiàn)，當(dāng)?shù)扔诘臅r(shí)候也停止指針移動(dòng)是較好的
                        // 從工程角度看兩個(gè)指針都要判斷等于才行
                        // 因?yàn)槿绻挥幸贿吪袛鄷?huì)造成不平衡性問(wèn)題
                        // 也就是因?yàn)榭炫琶刻硕紩?huì)分大于小于樞軸的兩個(gè)集合的
                        // 如果只有一邊判斷等于那么很容易將等于樞軸的數(shù)分到一個(gè)集合中
                        // 造成了另一個(gè)集合沒(méi)有等于樞軸的數(shù)
                        // 從工程學(xué)角度是不合理的
                        if (array[i] >= p) {
                            break;
                        }
                    }
                    for (; ; ) {
                        j = j - 1;
                        if (array[j] <= p) {
                            break;
                        }
                    }
                    // i>=j七扰，說(shuō)明都比較完了奢赂，應(yīng)該跳出循環(huán)
                    if (i < j) {
                        swap(array, i, j);
                    } else {
                        break;
                    }
                }
                // {left,2,3,4,5,i,i+1,8,9,right-1,right}
                // 對(duì)照數(shù)組就很明了了
                swap(array, i, right - 1);
                // 是一個(gè)遞歸調(diào)用，后續(xù)考慮實(shí)現(xiàn)非遞歸調(diào)用的高效算法
                // 因?yàn)槭且獙?shí)現(xiàn)并發(fā)的快排的
                quick(array, left, i - 1);
                quick(array, i + 1, right);
            } else {
                insertion(array, left, right);
            }
        } else {
            insertion(array, left, right);
        }
    }

    // 樞軸的選擇颈走，采用中位數(shù)法
    // 1)對(duì)頭膳灶，中，尾三個(gè)數(shù)進(jìn)行排序
    // 2)將已經(jīng)排好序的中間位置的數(shù)與倒數(shù)第二個(gè)數(shù)交換
    // 3)這樣做的好處是:排序的部分就是第二個(gè)位置與倒數(shù)第三個(gè)位置的中間部分
    // 中間沒(méi)有樞軸立由，移動(dòng)指針的時(shí)候無(wú)需判斷越界
    // 因?yàn)閮蛇叺倪吔缫呀?jīng)確定了
    // 這樣還有個(gè)好處就是數(shù)組中已經(jīng)有三個(gè)數(shù)的排好序的了
    // 并且這三個(gè)數(shù)不需要參與移動(dòng)
    // 僅僅作為一些判斷標(biāo)志以及控制
    private int partition(int[] array, int left, int right) {
        int c = (left + right) / 2;
        if (array[left] > array[c]) {
            swap(array, left, c);
        }
        if (array[left] > array[right]) {
            swap(array, left, right);
        }
        if (array[c] > array[right]) {
            swap(array, c, right);
        }
        swap(array, c, right - 1);
        return array[right - 1];
    }

    private void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    // 插入排序
    public void insertion(int[] array, int left, int right) {
        first(array, left, right);
        for (int i = left + 2; i <= right; i++) {
            int temp = array[i];
            int j = i;
            for (; temp < array[j - 1]; j--) {
                array[j] = array[j - 1];
            }
            array[j] = temp;
        }
    }

    // 這里的選擇最小數(shù)也是控制手段轧钓，簡(jiǎn)單的選擇，并不是像冒泡那樣
    // 正確方法還是參考之前的具體算法吧
    private void first(int[] array, int left, int right) {
        int sm = left;
        for (int i = left; i <= right; i++) {
            if (array[i] < array[sm]) {
                sm = i;
            }
        }
        // 僅僅將最小的數(shù)置于最開(kāi)始的位置
        swap(array, left, sm);
    }

    // 至于時(shí)間復(fù)雜度锐膜，空間復(fù)雜度大家百度吧毕箍，或者參考算法導(dǎo)論
    public static void main(String args[]) {
        QSort qs = new QSort();
        // 每次都是生成的不同的隨機(jī)數(shù)
        // 如果使用同一組數(shù)，這樣利用硬件特性道盏，耗費(fèi)的時(shí)間會(huì)更少
        // 可以試試
        ThreadLocalRandom random = ThreadLocalRandom.current();
        for (int t = 0; t < 100; t++) {
            int nums[] = new int[99999999];
            for (int i = 0; i < 99999999; i++) {
                int r = random.nextInt(999999999);
                nums[i] = r;
            }
            System.out.println("quick sort init finish ......");
            //qs.insertion(nums,0,nums.length-1);
            long start = System.nanoTime();
            qs.sort(nums, 0, nums.length - 1);
            long finish = System.nanoTime();
            System.out.println("quick sort finish ......cust nano time=" + (finish - start));
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] > nums[i + 1]) {
                    throw new IllegalStateException();
                }
            }
            System.out.println("...... check finish ,time=" + t + ",  ......");
        }
    }

}

喜歡java并發(fā)編程的請(qǐng)加群：736156823

<--結(jié)束
有問(wèn)題歡迎指正而柑，這是新鮮出爐的
本文為原創(chuàng)文章，轉(zhuǎn)載請(qǐng)注明出處荷逞，謝謝你……