一、定義
同冒泡排序一樣，快速排序也屬于交換排序，通過(guò)元素之間的比較和交換位置來(lái)達(dá)到排序的目的。
不同的是，冒泡排序在每一輪中只把1個(gè)元素冒泡到數(shù)列的一端，而快速排序則在每一輪挑選一個(gè)基準(zhǔn)元素，并讓其他比它大的元素移動(dòng)到數(shù)列一邊，比它小的元素移動(dòng)到數(shù)列的另一邊，從而把數(shù)列拆解成兩個(gè)部分。
這種思路就叫作分治法。
二、思路
1、基準(zhǔn)元素的選擇
基準(zhǔn)元素，英文是pivot，在分治過(guò)程中，以基準(zhǔn)元素為中心，把其他元素移動(dòng)到它的左右兩邊 我們可以隨機(jī)選擇一個(gè)元素作為基準(zhǔn)元素，并且讓基準(zhǔn)元素和數(shù)列首元素交換位置。
2、元素的比較
選定了基準(zhǔn)元素以后，我們要做的就是把其他元素中小于基準(zhǔn)元素的都交換到基準(zhǔn)元素一邊，大于基準(zhǔn)元素的都交換到基準(zhǔn)元素另一邊。
（1）雙邊循環(huán)法
首先，選定基準(zhǔn)元素pivot，并且設(shè)置兩個(gè)指針left和right，指向數(shù)列的最左和最右兩個(gè)元素
接下來(lái)進(jìn)行第1次循環(huán)：
從right指針開(kāi)始，讓指針?biāo)赶虻脑睾突鶞?zhǔn)元素做比較。
如果大于或等于pivot，則指針向左移動(dòng)；
如果小于pivot，則right指針停止移動(dòng)，切換到left指針；
輪到left指針行動(dòng)，讓指針?biāo)赶虻脑睾突鶞?zhǔn)元素做比較。
如果小于或等于pivot，則指針向右移動(dòng)；
如果大于pivot，則left指針停止移動(dòng) 左右指針指向的元素交換位置。
由于left開(kāi)始指向的是基準(zhǔn)元素，判斷肯定相等，所以left右移1位。
由于7>4，left指針在元素7的位置停下。這時(shí)，讓left和right指針?biāo)赶虻脑剡M(jìn)行交換。
接下來(lái)，進(jìn)入第2次循環(huán)，重新切換到right指針，向左移動(dòng)。right指針先移動(dòng)到8，8>4，繼續(xù)左移。由于2<4，停止在2的位置。
（2）單邊循環(huán)法
單邊循環(huán)法只從數(shù)組的一邊對(duì)元素進(jìn)行遍歷和交換。
開(kāi)始和雙邊循環(huán)法相似，首先選定基準(zhǔn)元素pivot。
同時(shí)，設(shè)置一個(gè)mark指針指向數(shù)列起始位置， 這個(gè)mark指針代表小于基準(zhǔn)元素的區(qū)域邊界。
接下來(lái)，從基準(zhǔn)元素的下一個(gè)位置開(kāi)始遍歷數(shù)組。
如果遍歷到的元素大于基準(zhǔn)元素，就繼續(xù)往后遍歷 如果遍歷到的元素小于基準(zhǔn)元素，
則需要做兩件事：
第一，把mark指針右移1位，因?yàn)樾∮趐ivot的區(qū)域邊界增大了1；
第二，讓最新遍歷到的元素和mark指針?biāo)谖恢玫脑亟粨Q位置，
因?yàn)樽钚卤闅v的元素歸屬于小 于pivot的區(qū)域 首先遍歷到元素7，7>4，所以繼續(xù)遍歷。
接下來(lái)遍歷到的元素是3，3<4，所以mark指針右移1位
隨后，讓元素3和mark指針?biāo)谖恢玫脑亟粨Q，因?yàn)樵?歸屬于小于pivot的區(qū)域。
按照這個(gè)思路，繼續(xù)遍歷，后續(xù)步驟如圖所示
三、代碼實(shí)現(xiàn)
1、雙邊循環(huán)法
import JAVA.util.Arrays;
/**
* 快速排序：雙邊循環(huán)法
*/
public class QuickSort {
public static void quickSort(int[] arr, int startIndex,
int endIndex) {
// 遞歸結(jié)束條件：startIndex大于或等于endIndex時(shí)
if (startIndex >= endIndex) {
return;
}
// 得到基準(zhǔn)元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根據(jù)基準(zhǔn)元素，分成兩部分進(jìn)行遞歸排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
/**
* 分治（雙邊循環(huán)法）
*
* @param arr 待交換的數(shù)組
* @param startIndex 起始下標(biāo)
* @param endIndex 結(jié)束下標(biāo)
* @return
*/
private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第1個(gè)位置（也可以選擇隨機(jī)位置）的元素作為基準(zhǔn)元素
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
while (left != right) {
//控制right 指針比較并左移
while (left < right && arr[right] > pivot) {
right--;
}
//控制left指針比較并右移
while (left < right && arr[left] <= pivot) {
left++;
}
//交換left和right 指針?biāo)赶虻脑? if (left < right) {
int p = arr[left];
arr[left] = arr[right];
arr[right] = p;
}
}
//pivot 和指針重合點(diǎn)交換
arr[startIndex] = arr[left];
arr[left] = pivot;
return left;
}
public static void main(String[] args) {
int[] arr = new int[]{4, 7, 3, 5, 6, 2, 8, 1};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
2、單邊循環(huán)法
import java.util.Arrays;
/**
* 快速排序：?jiǎn)芜呇h(huán)法
*/
public class QuickSort {
public static void quickSort(int[] arr, int startIndex,
int endIndex) {
// 遞歸結(jié)束條件：startIndex大于或等于endIndex時(shí)
if (startIndex >= endIndex) {
return;
}
// 得到基準(zhǔn)元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根據(jù)基準(zhǔn)元素，分成兩部分進(jìn)行遞歸排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
/**
* 分治（單邊循環(huán)法）
*
* @param arr 待交換的數(shù)組
* @param startIndex 起始下標(biāo)
* @param endIndex 結(jié)束下標(biāo)
* @return
*/
private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第1個(gè)位置（也可以選擇隨機(jī)位置）的元素作為基準(zhǔn)元素
int pivot = arr[startIndex];
int mark = startIndex;
for (int i = startIndex + 1; i <= endIndex; i++) {
if (arr[i] < pivot) {
mark++;
int p = arr[mark];
arr[mark] = arr[i];
arr[i] = p;
}
}
arr[startIndex] = arr[mark];
arr[mark] = pivot;
return mark;
}
public static void main(String[] args) {
int[] arr = new int[]{4, 7, 3, 5, 6, 2, 8, 1};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
