簡介
快速排序（Quicksort）是對冒泡排序的一種改進。
創(chuàng)始人：C. A. R. Hoare
出現(xiàn)的時間：1960年
快速排序算法的原理
基本思想
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序
簡單說明
- 通過設(shè)置分界值將原序列分為兩部分，（現(xiàn)在討論升序的情況，降序則相反）左邊部分的所有值都小于或等于分界值，右邊部分的所有值都大于或等于分界值。然后進行步驟2。
- 對步驟1中產(chǎn)生的兩部分分別再次按步驟1執(zhí)行一次。（這里其實已經(jīng)產(chǎn)生了遞歸）
具體步驟
首先設(shè)定一個分界值，通過該分界值將數(shù)組分成左右兩部分。
將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時，左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值。
然后，左邊和右邊的數(shù)據(jù)可以獨立排序。對于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個分界值，將該部分數(shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理。
重復(fù)上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當左、右兩個部分各數(shù)據(jù)排序完成后，整個數(shù)組的排序也就完成了。
對具體步驟的解釋
對上面具體步驟的抽象解釋如下：
- 對與一個數(shù)組設(shè)置一個分界值，然后用分界值與數(shù)組中的每一個元素（除分界值自己外）比較，所有滿足條件的（比如升序，被對比元素的元素應(yīng)該小于分界值）元素應(yīng)該從數(shù)組頭部開始依次往尾部方插入；相反，所有-不滿足條件的元素應(yīng)該從數(shù)組的尾部開始依次往頭部方向插入。
- 分界值自己除了作為對比值，還充當了空位置的角色，用于安置（實際上就是交換）滿足或不滿足條件的元素。
例
有了上面的介紹，相信你已經(jīng)對快速算法有了一個基本的認識，下面來看一個例子：
對數(shù)組[3,1,4,2,5]使用快速排序算法（升序），主要說明一趟排序（相當于遞歸調(diào)用的第一層）過程：
- 設(shè)置臨界值為
3 - 3和5比較，滿足升序，不交換
- 3和2比較，不滿足升序，交換，數(shù)組變?yōu)椋?code>[2,1,4,3,5]
- 3和1比較，滿足升序，不交換
- 3和4比較，不滿足升序，交換，數(shù)組變?yōu)椋?code>[2,1,3,4,5]
- 一趟排序完成
（說白了就是臨界值一直充當被交換的角色，不斷的把在前的不滿足條件的元素往后挪，在后的滿足條件的元素往前挪，所以它自己也要不斷的前后移動，直到找到真正屬于它的位置）
快速排序算法的Java實現(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);
}
//快速排序方法需要三個關(guān)鍵參數(shù)，設(shè)置排序區(qū)間的頭、尾數(shù)組下標和排序方式標志
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);
}
}
