概述
快速排序算法借鑒的是二叉樹(shù)前序遍歷的思想，最終對(duì)數(shù)組進(jìn)行排序梁呈。
優(yōu)點(diǎn)：
對(duì)于數(shù)據(jù)量比較大的數(shù)組排序婚度，由于采用的具有二叉樹(shù)二分的思想，故排序速度比較快
局限
只適用于順序存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)排序（數(shù)組 官卡，ArrayList等）蝗茁，不適用于鏈?zhǔn)降臄?shù)據(jù)結(jié)構(gòu)
算法實(shí)現(xiàn)思路
一.將目標(biāo)數(shù)組轉(zhuǎn)化為這樣一個(gè)數(shù)組醋虏。數(shù)組中的某個(gè)位置左邊的所有數(shù)據(jù)都比該位置的數(shù)據(jù)小，該位置右邊的數(shù)據(jù)都比該位置數(shù)據(jù)大哮翘。
實(shí)現(xiàn)思路：
1.取出數(shù)組第0個(gè)數(shù)據(jù)
圖片發(fā)自簡(jiǎn)書(shū)App
圖片發(fā)自簡(jiǎn)書(shū)App
3.改變遍歷方向阻课，從左邊開(kāi)始開(kāi)始遍歷，如果發(fā)現(xiàn)左邊的數(shù)據(jù)比第0個(gè)位置的數(shù)據(jù)大艰匙，將該位置的數(shù)據(jù)賦值給2步驟停留下來(lái)的位置柑肴，并變換方向。
圖片發(fā)自簡(jiǎn)書(shū)App
4.循環(huán)2旬薯、3步驟直到左右遍歷到的下標(biāo)重合
5.將取出的第0個(gè)位置的值賦值給循環(huán)結(jié)束后左右指針停留下的位置
二.借鑒前序遍歷的思路晰骑，遞歸，最終完成排序绊序。
代碼實(shí)現(xiàn)
private void quickSort(int[] array, int start, int end) {
if (start >= end) {
return;
}
int key = array[start];
int left = start;
int right = end;
boolean direction = true;
L1:
while (left < right) {
if (direction) {
for (int i = right; i > left; i--) {
if (array[i] < key) {
array[left++] = array[i];
right = i;
direction = !direction;
continue L1;
}
}
right = left;
} else {
for (int i = left; i < right; i++) {
if (array[i] > key) {
array[right--] = array[i];
left = i;
direction = !direction;
continue L1;
}
}
left = right;
}
}
array[left] = key;
quickSort(array, start, left - 1);
quickSort(array, left + 1, end);
}
結(jié)果測(cè)試
@Test
public void testQuickSort() {
int[] array = new int[]{1, 3, 4, 10, 2, 5, 6, 9, 7, 8};
quickSort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
結(jié)果打印
1
2
3
4
5
6
7
8
9
10
