一、定義
同冒泡排序一樣，快速排序也屬于交換排序，通過元素之間的比較和交換位置來達到排序的目的。
不同的是，冒泡排序在每一輪中只把1個元素冒泡到數列的一端，而快速排序則在每一輪挑選一個基準元素，并讓其他比它大的元素移動到數列一邊，比它小的元素移動到數列的另一邊，從而把數列拆解成兩個部分。
這種思路就叫作分治法。
二、思路
1、基準元素的選擇
基準元素，英文是pivot，在分治過程中，以基準元素為中心，把其他元素移動到它的左右兩邊 我們可以隨機選擇一個元素作為基準元素，并且讓基準元素和數列首元素交換位置。
2、元素的比較
選定了基準元素以后，我們要做的就是把其他元素中小于基準元素的都交換到基準元素一邊，大于基準元素的都交換到基準元素另一邊。
（1）雙邊循環法
首先，選定基準元素pivot，并且設置兩個指針left和right，指向數列的最左和最右兩個元素
接下來進行第1次循環：
從right指針開始，讓指針所指向的元素和基準元素做比較。
如果大于或等于pivot，則指針向左移動；
如果小于pivot，則right指針停止移動，切換到left指針；
輪到left指針行動，讓指針所指向的元素和基準元素做比較。
如果小于或等于pivot，則指針向右移動；
如果大于pivot，則left指針停止移動 左右指針指向的元素交換位置。
由于left開始指向的是基準元素，判斷肯定相等，所以left右移1位。
由于7>4，left指針在元素7的位置停下。這時，讓left和right指針所指向的元素進行交換。
接下來，進入第2次循環，重新切換到right指針，向左移動。right指針先移動到8，8>4，繼續左移。由于2<4，停止在2的位置。
（2）單邊循環法
單邊循環法只從數組的一邊對元素進行遍歷和交換。
開始和雙邊循環法相似，首先選定基準元素pivot。
同時，設置一個mark指針指向數列起始位置， 這個mark指針代表小于基準元素的區域邊界。
接下來，從基準元素的下一個位置開始遍歷數組。
如果遍歷到的元素大于基準元素，就繼續往后遍歷 如果遍歷到的元素小于基準元素，
則需要做兩件事：
第一，把mark指針右移1位，因為小于pivot的區域邊界增大了1；
第二，讓最新遍歷到的元素和mark指針所在位置的元素交換位置，
因為最新遍歷的元素歸屬于小 于pivot的區域 首先遍歷到元素7，7>4，所以繼續遍歷。
接下來遍歷到的元素是3，3<4，所以mark指針右移1位
隨后，讓元素3和mark指針所在位置的元素交換，因為元素3歸屬于小于pivot的區域。
按照這個思路，繼續遍歷，后續步驟如圖所示
三、代碼實現
1、雙邊循環法
import JAVA.util.Arrays;
/**
* 快速排序：雙邊循環法
*/
public class QuickSort {
public static void quickSort(int[] arr, int startIndex,
int endIndex) {
// 遞歸結束條件：startIndex大于或等于endIndex時
if (startIndex >= endIndex) {
return;
}
// 得到基準元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根據基準元素，分成兩部分進行遞歸排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
/**
* 分治（雙邊循環法）
*
* @param arr 待交換的數組
* @param startIndex 起始下標
* @param endIndex 結束下標
* @return
*/
private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第1個位置（也可以選擇隨機位置）的元素作為基準元素
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 指針所指向的元素
if (left < right) {
int p = arr[left];
arr[left] = arr[right];
arr[right] = p;
}
}
//pivot 和指針重合點交換
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、單邊循環法
import java.util.Arrays;
/**
* 快速排序：單邊循環法
*/
public class QuickSort {
public static void quickSort(int[] arr, int startIndex,
int endIndex) {
// 遞歸結束條件：startIndex大于或等于endIndex時
if (startIndex >= endIndex) {
return;
}
// 得到基準元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根據基準元素，分成兩部分進行遞歸排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
/**
* 分治（單邊循環法）
*
* @param arr 待交換的數組
* @param startIndex 起始下標
* @param endIndex 結束下標
* @return
*/
private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第1個位置（也可以選擇隨機位置）的元素作為基準元素
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));
}
}
