快速排序的基本思想：
分治法，即，分解，求解，組合 .

分解：
在 無(wú)序區(qū)R[low..high]中任選一個(gè)記錄作為基準(zhǔn)(通常選第一個(gè)記錄，并記為Pivot,其下標(biāo)為pivotpos),以此為基準(zhǔn)劃分成兩個(gè)較小的 子區(qū)間R[low,pivotpos - 1]和R[pivotpos + 1 , high],并使左邊子區(qū)間的所有記錄均小于等于基準(zhǔn)記錄,右邊子區(qū)間的所有記錄均大于等于基準(zhǔn)記錄,基準(zhǔn)記錄無(wú)需參加后續(xù)的排序。而劃分的關(guān)鍵是要求出 基準(zhǔn)記錄所在的位置pivotpos.

求解：
通過(guò)遞歸調(diào)用快速排序?qū)ψ蟆⒂易訁^(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序

組合：
當(dāng)"求解"步驟中的兩個(gè)遞歸調(diào)用結(jié)束時(shí)，其左、右兩個(gè)子區(qū)間已有序。對(duì)快速排序而言，"組合"步驟無(wú)須做什么，可看作是空操作。

具體過(guò)程：
設(shè)序列為R[low,high]，從其中選第一個(gè)為基準(zhǔn)，設(shè)為pivot,然后設(shè)兩個(gè)指針i和j,分別指向序列R[low,high]的起始和結(jié)束位置上：
      1），將i逐漸增大，直到找到大于pivot的關(guān)鍵字為止；
      2），將j逐漸減少，直到找到小于等于pivot的關(guān)鍵字為止；
      3），如果i<j，即R[i,j]的元素?cái)?shù)大于1，則交換R[i]和R[j]；
      4），將基準(zhǔn)記錄pivot放到合適的位置上，即i和j同時(shí)指向的位置,則此位置為新的pivotpos。

備注：
快速排序是不穩(wěn)定排序,即相同的關(guān)鍵字排序后，相對(duì)位置是不確定的。

示例代碼：

    public class DataStructure_QuickSort
    {
        //劃分子區(qū)間,計(jì)算基準(zhǔn)位置
        int Partition(int[] arr , int nLower ,int nUpper)
        {
            int pivot = arr[nLower] ;//取第一個(gè)記錄為基準(zhǔn)記錄
            int nLeft = nLower + 1;  //加1，pivot無(wú)需和自身做比較
            int nRight = nUpper ;

            int temp ;
            do{
                while (nLeft <= nRight && arr[nLeft] <= pivot) //將nLeft逐漸增大，直到找到大于pivot的下標(biāo)為止
                    nLeft++ ;

                while (nLeft <= nRight && arr[nRight] > pivot) //從nRight逐漸減少，直到找到小于等于pivot的下標(biāo)為止
                    nRight-- ;

                //R[nLeft,nRight]區(qū)間的長(zhǎng)度(元素?cái)?shù))大于1時(shí)，交換R[nLeft]和R[nRight]
                if (nLeft < nRight)
                {
                    temp = arr[nLeft] ;
                    arr[nLeft] = arr[nRight] ;
                    arr[nRight] = temp ;

                    nLeft++;
                    nRight--;
                }
            } while (nLeft < nRight); //當(dāng)nLeft == nRight的時(shí)候停止循環(huán)

            //把基準(zhǔn)記錄pivot放到正確位置，即nLeft和nRight同時(shí)指向的位置
            temp = arr[nLower];
            arr[nLower] = arr[nRight];
            arr[nRight] = temp ;

            return nRight ;
        }

        public void QuickSort(int[] arr, int nLower, int nUpper)
        {
            int pivotpos; //基準(zhǔn)下標(biāo)
            if (nLower < nUpper) //僅當(dāng)區(qū)間范圍長(zhǎng)度大于1時(shí)才須排序
            {
                pivotpos = Partition(arr, nLower, nUpper);//劃分子區(qū)間,知道基準(zhǔn)下標(biāo)(QuickSort的關(guān)鍵)
                QuickSort(arr, nLower, pivotpos - 1);     //對(duì)左區(qū)間遞歸排序 
                QuickSort(arr, pivotpos + 1, nUpper);     //對(duì)右區(qū)間遞歸排序
            }
        }
    }