原文地址：https://xeblog.cn/articles/17
快速排序基本思想
快速排序使用的是
分治思想润脸，通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分间螟，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小隅居，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行卵渴，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列李命。
image
實(shí)現(xiàn)思路
- 設(shè)置一個(gè)基準(zhǔn)值
k，一般取數(shù)組第一個(gè)元素蕉汪，以此值分割數(shù)組旺垒； - 設(shè)置兩個(gè)掃描員，分別為
i和j肤无，i指向數(shù)組的最低位，j指向數(shù)組的最高位骇钦； - 首先由
j開始從數(shù)組最高位往數(shù)組最低位(j--)掃描比k小的值宛渐，掃描到后停止掃描，并將該值填入i所處的位置眯搭，然后再由i開始從數(shù)組最低位往數(shù)組最高位(i++)掃描比k大的值窥翩，掃描到后停止掃描，并將該值填入j所處的位置鳞仙，j和i依次掃描寇蚊，直至j與i的位置相互重合后，將k的值填入重合處棍好，此時(shí)仗岸，數(shù)組左側(cè)的值均小于k允耿，右側(cè)值均大于k，完成此次排序扒怖； - 分別對(duì)數(shù)組左右兩邊的值做如上操作后即可完成快速排序较锡。
演示圖
快速排序演示圖.gif
代碼實(shí)現(xiàn)
/**
* 快速排序
* @param array 待排序數(shù)組
* @param begin 起點(diǎn)索引
* @param end 終點(diǎn)索引
*/
private static void fastSort(int[] array, int begin, int end) {
// 遞歸終止條件，起點(diǎn)索引大于等于終點(diǎn)索引
if (begin >= end) {
return;
}
// 起點(diǎn)索引
int i = begin;
// 終點(diǎn)索引
int j = end;
// 基準(zhǔn)值
int k = array[begin];
// 循環(huán)條件：起點(diǎn)索引小于終點(diǎn)索引
while (i < j) {
/*
這個(gè)循環(huán)是要掃描小于基準(zhǔn)值的值盗痒，掃描到后退出循環(huán),
循環(huán)條件：當(dāng)前索引位的值大于等于基準(zhǔn)值k(加等于號(hào)是防止相同數(shù)字交換而陷入死循環(huán)中),
且起點(diǎn)索引小于終點(diǎn)索引(防止數(shù)組下標(biāo)出界)
*/
while (array[j] >= k && i < j) {
// 終點(diǎn)索引位從右至左逐個(gè)遞減
j--;
}
if (i < j) {
// 將小于基準(zhǔn)值的數(shù)移至左側(cè)
array[i] = array[j];
}
/*
這個(gè)循環(huán)是要掃描大于基準(zhǔn)值的值蚂蕴，掃描到后退出循環(huán),
循環(huán)條件：當(dāng)前索引位的值小于等于基準(zhǔn)值k(加等于號(hào)是防止相同數(shù)字交換而陷入死循環(huán)中),
且起點(diǎn)索引小于終點(diǎn)索引(防止數(shù)組下標(biāo)出界)
*/
while (array[i] <= k && i < j) {
// 起點(diǎn)索引位從左至右逐個(gè)遞增
i++;
}
if (i < j) {
// 將大于基準(zhǔn)值的數(shù)移至右側(cè)
array[j] = array[i];
}
}
if (array[j] != k) {
// 基準(zhǔn)值歸位（數(shù)組的中間某個(gè)位置），歸位后俯邓，基準(zhǔn)值左側(cè)都是小于基準(zhǔn)值的數(shù)骡楼，右側(cè)都是大于基準(zhǔn)值的數(shù)
array[j] = k;
}
// 遞歸將基準(zhǔn)值左側(cè)的數(shù)排序
fastSort(array, begin, j - 1);
// 遞歸將基準(zhǔn)值右側(cè)的數(shù)排序
fastSort(array, j + 1, end);
}
測(cè)試排序
int[] array = {5, 6, 6, 4, 3, 5, 5};
System.out.println("排序前：" + Arrays.toString(array));
fastSort(array, 0, array.length - 1);
System.out.println("排序后：" + Arrays.toString(array));
輸出結(jié)果
排序前：[5, 6, 6, 4, 3, 5, 5]
排序后：[3, 4, 5, 5, 5, 6, 6]
快速排序的時(shí)間復(fù)雜度
平均時(shí)間復(fù)雜度： O(nlogn) 。
最壞時(shí)間復(fù)雜度： O(n^2) 稽鞭，這種情況發(fā)生在排序數(shù)組為正序或逆序的時(shí)候鸟整。
穩(wěn)定性： 不穩(wěn)定。
