簡(jiǎn)介

快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)烈涮。
創(chuàng)始人：C. A. R. Hoare
出現(xiàn)的時(shí)間：1960年

快速排序算法的原理

基本思想

通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小吁系，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序药版，整個(gè)排序過(guò)程可以遞歸進(jìn)行辑舷，以此達(dá)到整個(gè)數(shù)據(jù)變成有序

簡(jiǎn)單說(shuō)明

1. 通過(guò)設(shè)置分界值將原序列分為兩部分，（現(xiàn)在討論升序的情況槽片，降序則相反）左邊部分的所有值都小于或等于分界值何缓，右邊部分的所有值都大于或等于分界值。然后進(jìn)行步驟2还栓。
2. 對(duì)步驟1中產(chǎn)生的兩部分分別再次按步驟1執(zhí)行一次歌殃。（這里其實(shí)已經(jīng)產(chǎn)生了遞歸）

具體步驟

1. 首先設(shè)定一個(gè)分界值，通過(guò)該分界值將數(shù)組分成左右兩部分蝙云。

2. 將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊氓皱，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時(shí)，左邊部分中各元素都小于或等于分界值波材，而右邊部分中各元素都大于或等于分界值股淡。

3. 然后，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序廷区。對(duì)于左側(cè)的數(shù)組數(shù)據(jù)唯灵，又可以取一個(gè)分界值，將該部分?jǐn)?shù)據(jù)分成左右兩部分隙轻，同樣在左邊放置較小值埠帕，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理玖绿。

4. 重復(fù)上述過(guò)程敛瓷，可以看出，這是一個(gè)遞歸定義斑匪。通過(guò)遞歸將左側(cè)部分排好序后呐籽，再遞歸排好右側(cè)部分的順序。當(dāng)左蚀瘸、右兩個(gè)部分各數(shù)據(jù)排序完成后狡蝶，整個(gè)數(shù)組的排序也就完成了。

對(duì)具體步驟的解釋

對(duì)上面具體步驟的抽象解釋如下：

• 對(duì)與一個(gè)數(shù)組設(shè)置一個(gè)分界值贮勃，然后用分界值與數(shù)組中的每一個(gè)元素（除分界值自己外）比較贪惹，所有滿足條件的（比如升序，被對(duì)比元素的元素應(yīng)該小于分界值）元素應(yīng)該從數(shù)組頭部開(kāi)始依次往尾部方插入寂嘉；相反馍乙，所有-不滿足條件的元素應(yīng)該從數(shù)組的尾部開(kāi)始依次往頭部方向插入。
• 分界值自己除了作為對(duì)比值垫释，還充當(dāng)了空位置的角色丝格，用于安置（實(shí)際上就是交換）滿足或不滿足條件的元素。

例

有了上面的介紹棵譬，相信你已經(jīng)對(duì)快速算法有了一個(gè)基本的認(rèn)識(shí)显蝌，下面來(lái)看一個(gè)例子：
對(duì)數(shù)組[3,1,4,2,5]使用快速排序算法（升序），主要說(shuō)明一趟排序（相當(dāng)于遞歸調(diào)用的第一層）過(guò)程：

1. 設(shè)置臨界值為3
2. 3和5比較订咸，滿足升序曼尊，不交換
3. 3和2比較，不滿足升序脏嚷，交換骆撇，數(shù)組變?yōu)椋?code>[2,1,4,3,5]
4. 3和1比較，滿足升序父叙，不交換
5. 3和4比較神郊，不滿足升序肴裙，交換，數(shù)組變?yōu)椋?code>[2,1,3,4,5]
6. 一趟排序完成
   （說(shuō)白了就是臨界值一直充當(dāng)被交換的角色涌乳，不斷的把在前的不滿足條件的元素往后挪蜻懦，在后的滿足條件的元素往前挪，所以它自己也要不斷的前后移動(dòng)夕晓，直到找到真正屬于它的位置）

快速排序算法的Java實(shí)現(xiàn)

核心代碼

public void sort(boolean isAscending) {
        int[] data = super.getData();
        if (data == null || data.length < 2) {
            return;
        }
        //一趟排序
        this.quickSort(0, data.length - 1, isAscending);
    }

    //快速排序方法需要三個(gè)關(guān)鍵參數(shù)宛乃，設(shè)置排序區(qū)間的頭、尾數(shù)組下標(biāo)和排序方式標(biāo)志
    private void quickSort(int headIndex, int tailIndex, final boolean isAscending) {
        if (tailIndex - headIndex < 0) return;
        int[] data = super.getData();
        int key = data[headIndex];
        int i = headIndex, j = tailIndex;
        boolean isTail = true;
        while (i != j) {
            if (isTail) {
                boolean c1 = isAscending && data[j] < key;
                boolean c2 = !isAscending && data[j] > key;
                if (c1 || c2) {
                    swap(data, i, j);
                    i++;
                    isTail = false;
                    continue;
                }
                j--;
            } else {
                boolean c1 = isAscending && data[i] > key;
                boolean c2 = !isAscending && data[i] < key;
                if (c1 || c2) {
                    swap(data, i, j);
                    j--;
                    isTail = true;
                    continue;
                }
                i++;
            }
        }
         //遞歸排序
        this.quickSort(headIndex, i - 1, isAscending);
        this.quickSort(i + 1, tailIndex, isAscending);
    }

全部代碼（包導(dǎo)入信息自己設(shè)置）
AbstractSort.java

public abstract class AbstractSort {
    private int[] data;

    public AbstractSort(int[] data) {
        this.data = data;
    }

    public abstract void sort(boolean isAscending);

    public void sort() {
        this.sort(true);
    }

    public int[] getData() {
        return data;
    }

    public void print() {
        for (int i : this.data) {
            System.out.println(i);
        }
    }

    protected void swap(int[] data, int indexA, int indexB) {
        int temp = data[indexA];
        data[indexA] = data[indexB];
        data[indexB] = temp;
    }
}

QuickSort.java

public class QuickSort extends AbstractSort {
    public QuickSort(int[] data) {
        super(data);
    }

    @Override
    public void sort(boolean isAscending) {
        int[] data = super.getData();
        if (data == null || data.length < 2) {
            return;
        }
        this.quickSort(0, data.length - 1, isAscending);
    }

    private void quickSort(int headIndex, int tailIndex, final boolean isAscending) {
        if (tailIndex - headIndex < 0) return;
        int[] data = super.getData();
        int key = data[headIndex];
        int i = headIndex, j = tailIndex;
        boolean isTail = true;
        while (i != j) {
            if (isTail) {
                boolean c1 = isAscending && data[j] < key;
                boolean c2 = !isAscending && data[j] > key;
                if (c1 || c2) {
                    swap(data, i, j);
                    i++;
                    isTail = false;
                    continue;
                }
                j--;
            } else {
                boolean c1 = isAscending && data[i] > key;
                boolean c2 = !isAscending && data[i] < key;
                if (c1 || c2) {
                    swap(data, i, j);
                    j--;
                    isTail = true;
                    continue;
                }
                i++;
            }
        }
        this.quickSort(headIndex, i - 1, isAscending);
        this.quickSort(i + 1, tailIndex, isAscending);
    }
}