關(guān)于快速排序，網(wǎng)上，和維基都有完成的解釋，他們都是。。。。。。，俺覺(jué)得都是，太過(guò)于總結(jié)話語(yǔ)在概述一些東西；

而我卻從最本質(zhì)的東西，一步一步的深入；在深入的學(xué)習(xí)過(guò)程中，我得到如下非代碼層面上的感悟；

A.一個(gè)完整的模式（代碼或者其他東西）都是通過(guò)沒(méi)有=>part0=>part1=>part2>version0=>viersion1.......versionN=>perfect? 最后達(dá)到一個(gè)完成的形式；

如果你只是去學(xué)習(xí)和體會(huì)最后的那一個(gè)完成的版本，而沒(méi)有經(jīng)歷整個(gè)探索的過(guò)程，你的體會(huì)也不會(huì)太多；

?

B.有時(shí)候要學(xué)會(huì)抽象化和跳躍化的去思考問(wèn)題，而不是step by step（這有點(diǎn)不具體，下次我結(jié)合具體的實(shí)例來(lái)解釋）

?

C.幫助別人解決問(wèn)題；并不是直接給出問(wèn)題的答案或者結(jié)果；而是給別人一些引導(dǎo)和資源，讓他自己去解決；（這點(diǎn)來(lái)自使用stackoverflow提問(wèn)的感受）

?

D.還有第四點(diǎn)，要學(xué)會(huì)從特殊（具體）到一般（抽象）的探索過(guò)程；比如，我們可以先總結(jié)出滿足大于零的規(guī)律，然后是小于零的規(guī)律，然后是等于零的規(guī)律，這些都是特殊（或者你可以理解成具體）；從這些特殊規(guī)律總結(jié)出一般性（通用性）的規(guī)律；

?

E.還有當(dāng)研究出了算法之后，要學(xué)會(huì)如何去驗(yàn)證自己的一般性規(guī)律，在我們的code，就是要學(xué)會(huì)寫測(cè)試用例，進(jìn)行驗(yàn)證；

?

好了，廢話不多了；直接從代碼開(kāi)始；開(kāi)始之前，想嘗試做下面的practice;

?

1.選擇數(shù)組的第一個(gè)data(target)將數(shù)組分成兩部分；滿足:? ?minArr<target<=maxArr;

?

2.選擇數(shù)組的第一個(gè)data(target)將數(shù)組分成兩部分；滿足:? ?minArr<target<=maxArr; 并將target 放入數(shù)組“中間位置“；滿足：? target greater than left data and less than right data;

?

3.找出value 在有序數(shù)組中的位置；

?

4.找出value 在無(wú)序數(shù)組中的位置；這個(gè)位置應(yīng)該滿足，它在有序數(shù)組中應(yīng)該具有的位置；greater than left data and less than right data;

?

5.在不開(kāi)辟內(nèi)存的情況下（使用新的數(shù)組來(lái)存儲(chǔ)值）完成問(wèn)題2；

?

6.關(guān)于遞歸的學(xué)習(xí)和使用（具體看這篇文章的后半部分：http://www.cnblogs.com/mc67/p/5114008.html）

?

7.三種方式來(lái)實(shí)現(xiàn)我們的額快速排序；（本質(zhì)的區(qū)別只有兩種）

?

8.通過(guò)Unit Test 來(lái)驗(yàn)證我們的代碼；

?

?

關(guān)于前面的 5個(gè)問(wèn)題，我就直接上代碼；你細(xì)細(xì)品味（建議在沒(méi)有看代碼前，完成上面的問(wèn)題）

?

/// <summary>/// 最基本的；將數(shù)組分成兩部分；一部分比target小，一部分比target大；/// </summary>/// <param name="arr"></param>static void SplitArray(int[] arr){int len = arr.Length;int target = arr[0];List<int> min = new List<int>(len); //為了方便，這里我使用ListList<int> max = new List<int>(len); //為了方便，這里我使用Listfor (int i = 1; i < len; i++) //從第二個(gè)元素開(kāi)始查找； {if (arr[i] < target){min.Add(arr[i]);}else{max.Add(arr[i]); // as euqual condition,I put it into max; }}}/// <summary>/// split the arr and put the target in the right position(greater than left ,less than right)/// </summary>/// <param name="arr"></param>static void SplitArray1(int[] arr){int len = arr.Length;int target = arr[0];List<int> min = new List<int>(len); //為了方便，這里我使用ListList<int> max = new List<int>(len); //為了方便，這里我使用Listfor (int i = 1; i < len; i++) //從第二個(gè)元素開(kāi)始查找； {if (arr[i] < target){min.Add(arr[i]);}}//put it in the last of min, that can make sure target greater than min(left) min.Add(target);for (int i = 1; i < len; i++) //從第二個(gè)元素開(kāi)始查找； {if (arr[i] > target){max.Add(arr[i]);}}min.AddRange(max); //that can make sure min<target<max }/// <summary>/// optimze the SplitArray1/// 上面的代碼，還是有問(wèn)題的，如果有重復(fù)的值，那么，將在判斷max的時(shí)候丟掉；/// 那么問(wèn)題來(lái)了，如果相等的如何判斷呢;/// </summary>/// <param name="arr"></param>static void SplitArray2(int[] arr){int len = arr.Length;int target = arr[0];List<int> min = new List<int>(len); //為了方便，這里我使用ListList<int> max = new List<int>(len); //為了方便，這里我使用Listfor (int i = 1; i < len; i++) //從第二個(gè)元素開(kāi)始查找； {if (arr[i] < target){min.Add(arr[i]);}}//put it in the last of min, that can make sure target greater than min(left) min.Add(target);for (int i = 1; i < len; i++) //從第二個(gè)元素開(kāi)始查找； {if (arr[i] >= target) //我們把等于符號(hào)加上，就解決問(wèn)了？？？？ 對(duì)于本例子，是從arr[0] 開(kāi)始的；//那如果是從別的位置開(kāi)始呢； {max.Add(arr[i]);}}}/// <summary>/// start from random index;/// </summary>/// <param name="arr"></param>static void SplitArray3(int[] arr){int len = arr.Length;int randomIndex = 2;int target = arr[randomIndex]; //假設(shè)，我們從index=2 開(kāi)始，這里，我們肯定滿足arr.length>=2; List<int> min = new List<int>(len); //為了方便，這里我使用ListList<int> max = new List<int>(len); //為了方便，這里我使用Listfor (int i = 0; i < len; i++) //這里，我們就要從0 開(kāi)始了，遍歷整個(gè)數(shù)組； {if (arr[i] < target){min.Add(arr[i]);}}min.Add(target);for (int i = 0; i < len; i++) //這里，我們就要從0 開(kāi)始了，遍歷整個(gè)數(shù)組； {if (arr[i] >= target && i != randomIndex) //加上這個(gè)條件，我們就可以過(guò)濾到我們的 randomIndex 避免重復(fù)添加的問(wèn)題； {max.Add(arr[i]);}}//最后，我們的數(shù)組，就是符合我們要求的數(shù)組； }//上面的做法；可以滿足 min<target<=max/// <summary>/// 我們來(lái)找出元素所在的位置 index 首先是我們的有序數(shù)組中/// 通過(guò)值相等來(lái)進(jìn)行判斷的話，可以滿足；/// 不管值有序 還是 無(wú)序的值；/// </summary>static void FindIndex(int[] arr, int value){int len = arr.Length;int index = -1;for (int i = 0; i < len; i++){if (arr[i] == value){index = i;break;}}}/// <summary>/// 兩種思維方式，/// 兩種思維方式；第二種，更接近普通人的表達(dá)方式；/// </summary>/// <param name="arr"></param>/// <param name="value"></param>static void FindIndex1(int[] arr, int value){int len = arr.Length;int index;bool isExist = false;for (int i = 0; i < len; i++){if (arr[i] == value){index = i;isExist = true;break;}}if (isExist == false) { index = 1; }}/// <summary>/// 上面的方法是找到，value，在數(shù)組中的第一個(gè)index 值； 不管它是否有序；/// 現(xiàn)在我們要找一個(gè)元素，在有序列表中的（應(yīng)該插入的值,但是我們不插入）/// </summary>static void FindIndex2(int[] arr, int value){int len = arr.Length;int index = -1;for (int i = 0; i < len; i++){//你可以這么想；//如果找到大于大的數(shù)就停止；否則就繼續(xù)if (arr[i] >= value) //考慮到取等情況； {index = i; //這個(gè)時(shí)候，我們的數(shù)據(jù)，就可以插入在改元素的的后面；index = index - 1; //這樣就返回了可以直接插入的位置；//并且停止我們的循環(huán)；break; //前提是有序的數(shù)組列表中 }}//在插入的時(shí)候，就必須把后面的元素往后面挪動(dòng)；//插入的時(shí)候， }/// <summary>/// 上面的方法是找到，value，在數(shù)組中的第一個(gè)index 值； 不管它是否有序；/// 現(xiàn)在我們要找一個(gè)元素，在有序列表中的（應(yīng)該插入的值,但是我們不插入）/// 2 和 3 兩種不同的想法，寫出來(lái)的code 就不太一樣；/// </summary>static void FindIndex3(int[] arr, int value){int len = arr.Length;int index = -1;for (int i = 0; i < len; i++){//我們可以可以這么想； if (arr[i] <= value){index++; //小于它的值，我們的index 就 keep move forward; 還沒(méi)考慮，我們?nèi)〉鹊那闆r滴呀； }else{//遇到，不滿足的情況，我們就退出//原本的我們的index 是落后于我們的i，出去的時(shí)候；再加一次，index++;break;}}//這樣就找到了我們的index；在一個(gè)可以插入的位置； }/// <summary>/// 先這樣來(lái)想，找出小于 value的count，那么value在的位置應(yīng)該就是在我們的count+1;/// </summary>/// <param name="arr"></param>/// <param name="value"></param>static void FindCountLessThan(int[] arr, int value){int len = arr.Length;int count = 0;for (int i = 0; i < len; i++){if (arr[i] <= value){count++;}}//這樣，我們就能夠找出小于count的數(shù)量；那么 我們value所在的位置就是我們count+1 }/// <summary>/// 關(guān)鍵的來(lái)了：找到value 應(yīng)該在的位置；在一個(gè)無(wú)序的數(shù)組中；/// </summary>/// <param name="arr"></param>/// <param name="value"></param>static void FindIndexInUnSortArr(int[] arr, int value){int len = arr.Length;int rightPosition = 0; //初始化，默認(rèn)我們的指針在0位置；for (int i = 0; i < len; i++){//通過(guò)遍歷來(lái)查找；if (arr[i] <= value){rightPosition++;}}}/// <summary>/// 找到index在的位置，并將小于value的數(shù)據(jù)放在左邊，大于value的數(shù)據(jù)放在右邊/// </summary>/// <param name="arr"></param>/// <param name="value"></param>static void FindeAndSwap(int[] arr){int len = arr.Length;int middleIndex = 1;int value = arr[0];//target;// i 能找到一個(gè)小于value的值；//middleIndex 始終指向一個(gè)大于或等于 value的值；for (int i = 1; i < len; i++){if (arr[i] <= value) //當(dāng)找到一個(gè)小于value的值之后，進(jìn)行交換，和那個(gè)值進(jìn)行交換呢；（原則：小的值移動(dòng)到左邊，大的值移動(dòng)到右邊；）{ //現(xiàn)在，我們找到了小的值，那么大的值呢；？？？？if (i == middleIndex){//不進(jìn)行交換； keep move }else{Swap(arr, middleIndex, i);}middleIndex++;}}//最后出來(lái)后，我們要將第一個(gè)元素和中間的元素進(jìn)行交換，也就是講value放在middle的位置；Swap(arr, 0, middleIndex - 1);}/// <summary>/// 上面的代碼，基本上已經(jīng)滿足了我們額基本要求；/// 完美的代碼，解決了這個(gè)問(wèn)題；/// </summary>/// <param name="arr"></param>static int FindeAndSwap1(int[] arr, int start, int end){int middlePosition = start + 1;int pivot = arr[start];for (int i = start + 1; i <= end; i++){if (arr[i] <= pivot){if (i == middlePosition){//there is need to swap }else{Swap(arr, middlePosition, i);}middlePosition++;}}//put the arr[start] in "middle position"(greater than left,less than right)int position = middlePosition - 1;Swap(arr, arr[start], position);return position;}/// <summary>/// 同樣，我們又第二種方式來(lái)實(shí)現(xiàn)，/// </summary>/// <param name="arr"></param>/// <param name="low"></param>/// <param name="high"></param>static void FindeAndSwap2(int[] arr, int low,int high){int l = low-1; //make sure pointer move firstly (before take value from arr to compare with pviot)int h = high+1; //make sure pointer move firstly (before take value from arr to compare with pviot)int pviot = arr[low]; while (l<h){while (arr[--h]> pviot) //find some value less than pvoit {}while (arr[++l] <= pviot) //find some value greater than pvoit we use <= instead of <;beacause we don't let arr[start] swap {}if (l < h){Swap(arr, h, l); //swap }} Swap(arr, low, h); //put the povit in the "middle" Position }/// <summary>/// 同樣，我們也有第三種寫法；/// </summary>/// <param name="arr"></param>/// <param name="low"></param>/// <param name="high"></param>static int FindeAndSwap3(int[] arr, int low, int high){int l = low;int h = high;int pviot = arr[low];while (l < h){while (arr[h] >= pviot) //chose >= instead of >; beca if the first value arr[h] equal pviot ,this will enter endless loop；(don't enter {} do h--;) {h--;}while (arr[l] <= pviot) //we chose <= instead of < to make sure pviot don't take part in swap, we will swap in the last step with "middle" position {l++;}if (l >= h)break;Swap(arr,l,h);}int middlePosition = h;Swap(arr,low, middlePosition);return middlePosition;}/// <summary>/// 當(dāng)然，就有了，我們的第四種方法；/// 你會(huì)發(fā)現(xiàn)，前面的方法都是，先找到一個(gè)小于的index high 然后找到一個(gè)大于的index low/// 然后進(jìn)行交換；/// 然后有沒(méi)有其他的方式呢？ /// 答案是有的；/// 而且，你會(huì)發(fā)現(xiàn)，我們的額pvoit 是沒(méi)有參與swap的，直到我們的最后一步，然后將起放在 middle position（這一步，是不可避免滴呀）/// </summary>/// <param name="arr"></param>/// <param name="low"></param>/// <param name="high"></param>/// <returns></returns>static int FindeAndSwap4(int[] arr, int low, int high){int pviot = arr[low];while (low < high){while(arr[high]>=pviot && low < high){high--;}//一旦，找到了，我們就替換；arr[low] = arr[high]; //這樣，會(huì)覆蓋我們的第一個(gè)值，不過(guò)，在最后，我們會(huì)將第一個(gè)值，放在“中間”位置；while (arr[low] <= pviot && low < high){low++;} //這樣做的話，在沒(méi)有，進(jìn)行到最后一步，數(shù)組中會(huì)有一個(gè)重復(fù)的值，不過(guò)，我們最后將被我們pviotarr[high] = arr[low];}arr[low] = pviot;return high;}//到了這一步，我們的基本核心的單元，算是基本基本完整了；//然后，我們這里，再實(shí)現(xiàn)，三個(gè)版本的快速排序；方法；/// <summary>/// 交換/// </summary>/// <param name="arr"></param>/// <param name="i"></param>/// <param name="j"></param>static void Swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

?

?1.然后是快速排序的第一種實(shí)現(xiàn)方式：（從兩端申明指針然后，開(kāi)始查找； 這個(gè)算法是有問(wèn)題的：to do.....做單元測(cè)試來(lái)一步一步的發(fā)現(xiàn)問(wèn)題）

/// <summary>/// 第一種實(shí)現(xiàn)方式，從兩邊開(kāi)始查找；/// 還有一個(gè)值得考慮問(wèn)題就是，等于的數(shù)據(jù)，如何處理呢；從我們的代碼看出，等于pviot的數(shù)據(jù)，沒(méi)有參與到交換中；/// 第一次交換之后將流在我們的 兩端；參與下一次的交換；/// </summary>/// <param name="arr"></param>/// <param name="low"></param>/// <param name="high"></param>/// <returns></returns>static int QuickSortUnit(int[] arr, int low, int high){
int pviot=arr[low]; //we chose the first value as pivot;
while (low < high){while (arr[high] >= pviot && low<high) //>= instead of > because: if the arr[high] less than pviot,that will result in endless loop(high index never do high--;) {high--; //start search from high address }while (arr[low] <= pviot && low<high) // <= instead of < becuase:we can make sure arr[first] did't involve the whole swap until the ending {low++; //start search from low address }//we both chose equal,after first loop,the equivalent will remianing the origial positon and take part in next sort; that does't affect the final result;if (low >= high)break;Swap(arr, low, high);}//because we firstly star from high; so the last value that must less than pviot;so high is our "middle" position;int middlePosition = high; //make the code easy to read; Swap(arr,middlePosition,low);return high;}/// <summary>/// recurion to resolve the same problem;/// </summary>/// <param name="arr"></param>/// <param name="low"></param>/// <param name="high"></param>static void QuickSort(int [] arr,int low,int high){if (low >= high) //make sure recusion can stopreturn;int middlePositon=QuickSortUnit(arr,low,high);//star from left;QuickSort(arr,low, middlePositon-1);//star from rightQuickSort(arr, middlePositon+1,high);}

2.然后是快速排序的第二種實(shí)現(xiàn)方式（本質(zhì)上和第一種方式一樣的，只不過(guò)寫法（想法），略有不同，一旦找到元素就開(kāi)始覆蓋指定位置的值，這樣每次都會(huì)有一個(gè)重復(fù)的值，不過(guò)這個(gè)重復(fù)的值，最后會(huì)被我們的pivot給占據(jù)）

/// <summary>/// /// </summary>/// <param name="arr"></param>/// <param name="low"></param>/// <param name="high"></param>static int QuickSortUnit(int[] arr, int low, int high){int pviot = arr[low];while (low < high){while (arr[high] >= pviot && low<high){high--;}arr[low] = arr[high]; //once find the value less than pviot ,put it in low address;while (arr[low] <= pviot && low < high){low++;}arr[high] = arr[low]; //once find the value greater than pviot, put it in high address; }int middlePositon = high;arr[low] = pviot; return middlePositon;}/// <summary>/// use recursion to resovle the same problem;/// </summary>/// <param name="arr"></param>/// <param name="low"></param>/// <param name="high"></param>static void QuickSort(int [] arr,int low,int high){if (low >= high)return;int middlePosition = QuickSortUnit(arr,low,high);QuickSortUnit(arr, low, middlePosition-1);QuickSortUnit(arr, middlePosition+1, high);}

思考：

? ?最后一步交互為哈一定要取low呢；（debug 一下這個(gè)：? ? var arr = new[] { 7, 8, 7 };）

?

?

第三種方式；其實(shí)，本質(zhì)是一樣，不過(guò)，這種方式，不用從兩端申明pointer，去查找（伴隨著兩個(gè)while循環(huán)）；這里我們用一個(gè)循環(huán)，還是兩個(gè)pointer，不過(guò)他們的出發(fā)位置，就有所不同了，都從左邊開(kāi)始；

?提現(xiàn)了不同的思路去解決問(wèn)題；

?

?

?最后一種，我們就直接給鏈接吧；

?https://www.hackerearth.com/zh/practice/algorithms/sorting/quick-sort/tutorial/

非常好的網(wǎng)站；

?

這里，我們?cè)賮?lái)總結(jié)一下，整個(gè)執(zhí)行過(guò)程：

1）設(shè)置兩個(gè)變量i、j，排序開(kāi)始的時(shí)候：i=0，j=N-1； 2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]； 3）從j開(kāi)始向前搜索，即由后開(kāi)始向前搜索(j--)，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]互換； 4）從i開(kāi)始向后搜索，即由前開(kāi)始向后搜索(i++)，找到第一個(gè)大于key的A[i]，將A[i]和A[j]互換； 5）重復(fù)第3、4步，直到i=j； (3,4步中，沒(méi)找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時(shí)候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進(jìn)行交換的時(shí)候i， j指針位置不變。另外，i==j這一過(guò)程一定正好是i+或j-

最后，就是要通過(guò)寫單元測(cè)試，來(lái)assert我們的值；

?

轉(zhuǎn)載于:https://www.cnblogs.com/mc67/p/8259734.html

總結(jié)

以上是生活随笔為你收集整理的这可能是我见过最详细的快速排序！的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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