版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。博客源地址為zhixiang.org.cn https://blog.csdn.net/myFirstCN/article/details/80851021

學(xué)習(xí)更多算法系列請(qǐng)參考文章：死磕算法之匯總篇

快速排序是一個(gè)運(yùn)用了分治法和遞歸算法的排序方式。

假如我們現(xiàn)在要排序的數(shù)組為[3,1,0,2,8,4,2]。那么在進(jìn)行快速排序的時(shí)候我們先要進(jìn)行一些準(zhǔn)備：

• n作為一個(gè)數(shù)組中的標(biāo)桿，一趟排序過后我們要把數(shù)組中所有大于n的數(shù)放在它的右邊，所有小于n的放在它的左邊。一般情況下我們會(huì)取數(shù)組第一個(gè)元素作為n，在此數(shù)組中就是n=3
• i我們使用i來(lái)找數(shù)組中大于標(biāo)桿的值，i初始指向數(shù)組第一個(gè)位置
• j我們使用j來(lái)找數(shù)組中小于標(biāo)桿的值，j初始指向數(shù)組最后一個(gè)位置

下面開始排序：

先從數(shù)組右邊開始，我們發(fā)現(xiàn)j指向的元素2比標(biāo)桿n小，那么我們將j指向的元素賦值給i指向的元素，停止操作。此時(shí)數(shù)組為[2,1,0,2,8,4,2]，i指向第一個(gè)位置，j仍指向最后一個(gè)。

從數(shù)組左邊開始，i指向的元素2比標(biāo)桿小，所以不做操作，使i++，i指向的元素1比標(biāo)桿小，所以不做操作，使i++，一直到i指向8的時(shí)候比標(biāo)桿大（注意此處如果等于的話也要操作），那么就把i指向的元素賦值給j指向的元素，此時(shí)數(shù)組為[2,1,0,2,8,4,8]，i指向第五個(gè)位置。也就是元素8，j仍然指向最后一個(gè)位置。

繼續(xù)從右邊操作，j指向的8不比n小，所以不做操作，j--，4不比3小，不做操作，j--。現(xiàn)在i和j的位置重合了，把n放到這個(gè)位置上。我們此輪的操作也就結(jié)束了，接下來(lái)我們把3所在的位置左邊分為一個(gè)數(shù)組，右邊位置分為一個(gè)數(shù)組再次進(jìn)行剛才的操作。（此處就是一個(gè)遞歸調(diào)用了）

接下來(lái)就來(lái)看一個(gè)圖片描述的過程

接下來(lái)上代碼

public static void quickSort(int[] a, int l, int r) {if (l < r) {int i,j,n; i = l;j = r;n = a[i];while (i < j) {while(i < j ){if(a[j] < n){a[i] = a[j]; break; }j--; }while(i < j ){if(a[i] >= n){a[j] = a[i];break; }i++;}}a[i] = n;quickSort(a, l, i-1); /* 遞歸調(diào)用 */quickSort(a, i+1, r); /* 遞歸調(diào)用 */} }

快速排序講完了。在這里溫馨提示大家，學(xué)習(xí)算法時(shí)，我們沒必要拘泥于代碼的實(shí)現(xiàn)，那沒有意義。我的建議就是深入理解步驟，當(dāng)你理解步驟以后代碼是隨你怎么玩都可以的。

總結(jié)

以上是生活随笔為你收集整理的死磕算法之快速排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。