Java圖解快速排序算法(附源碼)

點(diǎn)擊上面藍(lán)字onlyserver，關(guān)注萬(wàn)人公眾號(hào)

號(hào)內(nèi)福利：

1.架構(gòu)師成神之路-最新視頻資源-65個(gè)課題【免費(fèi)下載】

2.400多人的微信技術(shù)群，干凈，沒(méi)廣告，氣氛活躍

3.技術(shù)文章都是精華文章，助你進(jìn)步，成長(zhǎng)，強(qiáng)大

=長(zhǎng)摁關(guān)注=

=回復(fù)加群進(jìn)微信技術(shù)群=

=回復(fù)1024下載視頻資源=

先說(shuō)一下原理：兩個(gè)指針，分別從數(shù)組的首尾開(kāi)始向中間運(yùn)動(dòng)，左指針先運(yùn)動(dòng)，左指針指到的數(shù)若大于或等于樞紐元?jiǎng)t停下來(lái)，當(dāng)左指針停下來(lái)的時(shí)候，右指針運(yùn)動(dòng)，右指針指到的數(shù)若小于樞紐元?jiǎng)t停下來(lái)，此時(shí)，交換左右指針指向的數(shù)，然后重復(fù)上述運(yùn)動(dòng)。直到左右指針相遇，運(yùn)動(dòng)結(jié)束。

比如數(shù)組：【7 10 2 4 7 1 8 5 19】， 把7當(dāng)做基準(zhǔn)值：

? ? ? ? ?

? ? ? ? ?左指針指到的數(shù)等于7，停下來(lái)；右指針指向的數(shù)大于7，繼續(xù)走。。。

? ? ? ? ? ? ??

? ? ? ? 右指針指向的數(shù)為5，小于7，停下來(lái)；然后交換兩個(gè)指針指向的數(shù)。。。

? ? ? ? ? ? ?

? ? ? ?然后左指針繼續(xù)走，走到10，大于7，停下來(lái)；然后右指針走，指向8，大于7，繼續(xù)走，然后走到1，小于7，停下來(lái)。。。

? ? ? ? ? ? ??

? ? ? ?然后交換左右兩個(gè)指針的指向的值。。。

? ? ? ?

? ? ? 然后左指針繼續(xù)走，走到2，小于7，繼續(xù)走，走到4，繼續(xù)走，走到7，等于7，停；然后右指針走，走到7，和左指針相遇。。。

? ? ? ??

? ? ? ?然后以7位界限，左邊的都是小于7的數(shù)，右邊的都是大于7的數(shù)。然后將左邊的【5,1,2,4】和右邊的【10,8,7,19】看成是兩個(gè)數(shù)組，重復(fù)上述的步驟，就可以排成【1,2,4,5,7,7,8,10,19】這樣的從小到大的有序數(shù)組。

上源碼：

package 快速排序;
/**
 * 7 10 2 4 7 1 8 5 19
 * 1.先找一個(gè)數(shù)，作為基準(zhǔn)，比如7
 * 2.左邊一個(gè)指針，從左向右找，找到大于等于7的就停下來(lái)， 找不到就繼續(xù)走
* 3.右邊一個(gè)指針，從右向左找，找到小于7的就停下來(lái)，找不到就繼續(xù)走
* 4.左右都停下來(lái)以后，交換指針下邊的值
* 5.一直到左邊的指針碰到右邊的指針，算是完成第一遍。
* 6.這樣的目的是為了以7為界，把小于7的數(shù)都放到左邊，把大于7的數(shù)都放到右邊
* 7.遞歸上面的操作，把左右分開(kāi)的兩部分，再按上面的步驟來(lái)一遍。
* des: 有3個(gè)while ,大while里面套著2個(gè)小while, 有遞歸，左右兩部分要遞歸
* 時(shí)間復(fù)雜度：
* 1.最壞的情況（基準(zhǔn)值左邊或者右邊的序列為空）,復(fù)雜度是：On2
 * 2.最好的情況（基準(zhǔn)值每次都恰好左右數(shù)量相等）,復(fù)雜度是：Onlogn
 * 3.平均的情況
* created by miapoeng on 2021/8/10 14:32
 */
public class QuickSort {

private static void quickSort (int[] arr, int low, int high) {
int i;//左邊指針
int j;//右邊指針
int temp;//基準(zhǔn)值
int t;//用于交換的第三者
//左邊指針大于右邊指針的時(shí)候，不再執(zhí)行? >=能行嗎?
if (low > high) {
return;
}

        i = low;//給左邊指針賦值(下標(biāo))
j = high;//給右邊指針賦值(下標(biāo))
temp = arr[low];//基準(zhǔn)值默認(rèn)取第一個(gè)數(shù)
//他倆沒(méi)相遇，就一直執(zhí)行
while (i < j) {

//左邊指針指的這個(gè)數(shù)大于等于7就停下， 下于7就繼續(xù)走
while (arr[i] < temp && i < j) {//&& i < 是必須要加的，否則會(huì)報(bào)錯(cuò)
i++;
}

//右邊指針指的這個(gè)數(shù)小于7就停下， 大于等于7就繼續(xù)走
while (arr[j] >= temp && i < j) {
                j--;
}

//都停下以后，進(jìn)行交換
// if (i < j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
//  }
}

quickSort(arr, low, j-1);
quickSort(arr, j+1, high);
}


public static void main(String[] args) {
int[] arr = {7, 10, 2, 4, 7, 1, 8, 5, 19, 190};
quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
}
//1 2 4 5 7 7 8 10 19 190
}
}