這可能是我見過最詳細的快速排序！

關于快速排序，網上，和維基都有完成的解釋，他們都是。。。。。。，俺覺得都是，太過于總結話語在概述一些東西；

而我卻從最本質的東西，一步一步的深入；在深入的學習過程中，我得到如下非代碼層面上的感悟；

A.一個完整的模式（代碼或者其他東西）都是通過沒有=>part0=>part1=>part2>version0=>viersion1.......versionN=>perfect? 最后達到一個完成的形式；

如果你只是去學習和體會最后的那一個完成的版本，而沒有經歷整個探索的過程，你的體會也不會太多；

B.有時候要學會抽象化和跳躍化的去思考問題，而不是step by step（這有點不具體，下次我結合具體的實例來解釋）

C.幫助別人解決問題；并不是直接給出問題的答案或者結果；而是給別人一些引導和資源，讓他自己去解決；（這點來自使用stackoverflow提問的感受）

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

E.還有當研究出了算法之后，要學會如何去驗證自己的一般性規律，在我們的code，就是要學會寫測試用例，進行驗證；

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

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

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

3.找出value 在有序數組中的位置；

4.找出value 在無序數組中的位置；這個位置應該滿足，它在有序數組中應該具有的位置；greater than left data and less than right data;

5.在不開辟內存的情況下（使用新的數組來存儲值）完成問題2；

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

7.三種方式來實現我們的額快速排序；（本質的區別只有兩種）

8.通過Unit Test 來驗證我們的代碼；

關于前面的 5個問題，我就直接上代碼；你細細品味（建議在沒有看代碼前，完成上面的問題）

 /// <summary>/// 最基本的；將數組分成兩部分；一部分比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++) //從第二個元素開始查找；
            {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++) //從第二個元素開始查找；
            {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++) //從第二個元素開始查找；
            {if (arr[i] > target){max.Add(arr[i]);}}min.AddRange(max); //that can make sure  min<target<max
        }/// <summary>/// optimze the SplitArray1/// 上面的代碼，還是有問題的，如果有重復的值，那么，將在判斷max的時候丟掉；/// 那么問題來了，如果相等的如何判斷呢;/// </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++) //從第二個元素開始查找；
            {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++) //從第二個元素開始查找；
            {if (arr[i] >= target) //我們把等于符號加上，就解決問了？？？？ 對于本例子，是從arr[0] 開始的；//那如果是從別的位置開始呢；
                {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]; //假設，我們從index=2 開始，這里，我們肯定滿足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 開始了，遍歷整個數組；
            {if (arr[i] < target){min.Add(arr[i]);}}min.Add(target);for (int i = 0; i < len; i++) //這里，我們就要從0 開始了，遍歷整個數組；
            {if (arr[i] >= target && i != randomIndex) //加上這個條件，我們就可以過濾到我們的 randomIndex 避免重復添加的問題； 
                {max.Add(arr[i]);}}//最后，我們的數組，就是符合我們要求的數組；
        }//上面的做法；可以滿足  min<target<=max/// <summary>/// 我們來找出元素所在的位置 index 首先是我們的有序數組中/// 通過值相等來進行判斷的話，可以滿足；/// 不管值有序 還是 無序的值；/// </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>/// 兩種思維方式，/// 兩種思維方式；第二種，更接近普通人的表達方式；/// </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，在數組中的第一個index 值； 不管它是否有序；/// 現在我們要找一個元素，在有序列表中的（應該插入的值,但是我們不插入）/// </summary>static void FindIndex2(int[] arr, int value){int len = arr.Length;int index = -1;for (int i = 0; i < len; i++){//你可以這么想；//如果找到大于大的數就停止；否則就繼續if (arr[i] >= value)  //考慮到取等情況；
                {index = i; //這個時候，我們的數據，就可以插入在改元素的的后面；index = index - 1;  //這樣就返回了可以直接插入的位置；//并且停止我們的循環；break;    //前提是有序的數組列表中
                }}//在插入的時候，就必須把后面的元素往后面挪動；//插入的時候，
        }/// <summary>/// 上面的方法是找到，value，在數組中的第一個index 值； 不管它是否有序；/// 現在我們要找一個元素，在有序列表中的（應該插入的值,但是我們不插入）///  2 和 3 兩種不同的想法，寫出來的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;  還沒考慮，我們取等的情況滴呀；
                }else{//遇到，不滿足的情況，我們就退出//原本的我們的index 是落后于我們的i，出去的時候；再加一次，index++;break;}}//這樣就找到了我們的index；在一個可以插入的位置；
        }/// <summary>/// 先這樣來想，找出小于 value的count，那么value在的位置應該就是在我們的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的數量；那么 我們value所在的位置就是我們count+1
        }/// <summary>/// 關鍵的來了：找到value 應該在的位置；在一個無序的數組中；/// </summary>/// <param name="arr"></param>/// <param name="value"></param>static void FindIndexInUnSortArr(int[] arr, int value){int len = arr.Length;int rightPosition = 0;  //初始化，默認我們的指針在0位置；for (int i = 0; i < len; i++){//通過遍歷來查找；if (arr[i] <= value){rightPosition++;}}}/// <summary>/// 找到index在的位置，并將小于value的數據放在左邊，大于value的數據放在右邊/// </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 能找到一個小于value的值；//middleIndex 始終指向一個大于或等于 value的值；for (int i = 1; i < len; i++){if (arr[i] <= value) //當找到一個小于value的值之后，進行交換，和那個值進行交換呢；（原則：小的值移動到左邊，大的值移動到右邊；）{                    //現在，我們找到了小的值，那么大的值呢；？？？？if (i == middleIndex){//不進行交換； keep move
                    }else{Swap(arr, middleIndex, i);}middleIndex++;}}//最后出來后，我們要將第一個元素和中間的元素進行交換，也就是講value放在middle的位置；Swap(arr, 0, middleIndex - 1);}/// <summary>///  上面的代碼，基本上已經滿足了我們額基本要求；///  完美的代碼，解決了這個問題；/// </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>/// 同樣，我們又第二種方式來實現，/// </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>/// 當然，就有了，我們的第四種方法；/// 你會發現，前面的方法都是，先找到一個小于的index  high 然后找到一個大于的index low/// 然后進行交換；/// 然后有沒有其他的方式呢？ /// 答案是有的；/// 而且，你會發現，我們的額pvoit 是沒有參與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];  //這樣，會覆蓋我們的第一個值，不過，在最后，我們會將第一個值，放在“中間”位置；while (arr[low] <= pviot && low < high){low++;} //這樣做的話，在沒有，進行到最后一步，數組中會有一個重復的值，不過，我們最后將被我們pviotarr[high] = arr[low];}arr[low] = pviot;return high;}//到了這一步，我們的基本核心的單元，算是基本基本完整了；//然后，我們這里，再實現，三個版本的快速排序；方法；/// <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.然后是快速排序的第一種實現方式：（從兩端申明指針然后，開始查找；這個算法是有問題的：to do.....做單元測試來一步一步的發現問題）

        /// <summary>/// 第一種實現方式，從兩邊開始查找；/// 還有一個值得考慮問題就是，等于的數據，如何處理呢；從我們的代碼看出，等于pviot的數據，沒有參與到交換中；/// 第一次交換之后將流在我們的 兩端；參與下一次的交換；/// </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.然后是快速排序的第二種實現方式（本質上和第一種方式一樣的，只不過寫法（想法），略有不同，一旦找到元素就開始覆蓋指定位置的值，這樣每次都會有一個重復的值，不過這個重復的值，最后會被我們的pivot給占據）

        /// <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);}