快速排序是效率比較高的排序方式糟描,采用分治法思想,將規(guī)模較大的問(wèn)題分解成規(guī)模較小的子問(wèn)題书妻,它的時(shí)間復(fù)雜度O(nlog2n)船响。
描述:
1、選定第一個(gè)值為基準(zhǔn)值躲履,在數(shù)組兩端設(shè)置一個(gè)低指針和一個(gè)高指針见间,從兩端往中間遍歷。
2工猜、高指針從右往左走米诉,遇到比基準(zhǔn)值小的就賦值給低指針,切換方向從低指針往右走篷帅;低指針遇到比基準(zhǔn)值大的就賦值給高指針史侣,切換方向;
3魏身、最終高指針和低指針重合抵窒,本次遍歷結(jié)束,此時(shí)基準(zhǔn)值左側(cè)元素都比它小叠骑,右側(cè)都比他大。
4削茁、數(shù)組從基準(zhǔn)值處一分為二宙枷,各自重復(fù)以上過(guò)程直到分成N個(gè)長(zhǎng)度為1的數(shù)組,數(shù)組完成排序(類(lèi)似二叉樹(shù)前序遍歷)茧跋。
動(dòng)畫(huà):
代碼:
private void quickSort(int[] array, int start, int end) {
if (array.length <= 1 || start >= end) {
//數(shù)組最后會(huì)分解成長(zhǎng)度為1的小數(shù)組慰丛,而且start值等于end,到此遞歸結(jié)束
return;
}
//取第一個(gè)值為基準(zhǔn)值
int temp = array[start];
int low = start;
int high = end;
//false 從高指針往低指針走
//true 從低指針往高指針走
boolean direction = false;
while (low < high) {
if (!direction) {
if (temp <= array[high]) {
//高指針對(duì)應(yīng)的值比基準(zhǔn)值大
//高指針左移
high--;
} else {
//高指針對(duì)應(yīng)的值比基準(zhǔn)值小
//把這個(gè)值放在低指針位置
//低指針右移
//切換移動(dòng)方向
array[low++] = array[high];
direction = !direction;
}
} else {
if (temp >= array[low]) {
low++;
} else {
array[high--] = array[low];
direction = !direction;
}
}
}
//指針移動(dòng)結(jié)束把基準(zhǔn)值放在高低指針重合處
array[low] = temp;
//這時(shí)候基準(zhǔn)值左側(cè)元素都是比它小的瘾杭,右側(cè)都是比他大的
//數(shù)組從基準(zhǔn)值處一分為二诅病,各自重復(fù)以上過(guò)程
quickSort(array, start, low - 1);
quickSort(array, low + 1, end);
}