快速排序算法思想：
（1）輸入的數(shù)據(jù)信息：輸入一個(gè)待排序的數(shù)組a[n]酿雪，利用QuickSort算法實(shí)現(xiàn)此數(shù)組的排序任務(wù)。
（2）快速排序的思想：找待排序數(shù)組a[n]中a[0]或者a[n-1]作為參考flag略就，例如找flag=a[n-1]近刘，然后兩個(gè)指針一個(gè)從left=0開始向右索引，一個(gè)指針從right=n-2開始向左索引干旁，left指針尋找大于flag的元素魁袜，right指針尋找小于flag的元素桩撮，如果都找不到，則left++或right--峰弹，繼續(xù)索引距境，當(dāng)left>=right時(shí)，終止此循環(huán)垮卓，然后把flag與此時(shí)left指針?biāo)饕脑亟粨Q垫桂，最后輸出left，實(shí)現(xiàn)數(shù)據(jù)分割粟按，即left指針左邊的數(shù)據(jù)元素小于flag诬滩，left指針右邊的數(shù)據(jù)元素大于flag霹粥。
（3）遞歸實(shí)現(xiàn)算法：輸入待排序的數(shù)組a[n]和需要對(duì)此數(shù)組排序的索引范圍（left，right）疼鸟，因?yàn)槲覀儾豢赡塥?dú)立把數(shù)組分成兩部分后控，所以實(shí)現(xiàn)的方式就是在原數(shù)組上進(jìn)行處理，利用交換實(shí)現(xiàn)空間復(fù)雜度不變空镜。
快速排序Java編程：
public class QuickSortTest {
public static void QuickSort(int[] arr, int left, int right){
if(left < right){
int medium = Partition(arr, left, right);
QuickSort(arr, left, medium-1);
QuickSort(arr, medium+1, right);
}
}
public static int Partition(int[] arr, int left, int right){
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot)
right--;
if (left < right)
arr[left++] = arr[right];
while (left < right && arr[left] <= pivot)
left++;
if (left < right)
arr[right--] = arr[left];
}
arr[left] = pivot;
return left;
}
public static void main(String[] args) {
int[] arr = {6,9,8,6,4,3,9,10,52,82,12,36,14};
int left = 0;
int right = arr.length - 1;
QuickSort(arr,left,right);
for(int i : arr){
System.out.print(i);
System.out.print(' ');
}
}
}
輸出結(jié)果：3 4 6 6 8 9 9 10 12 14 36 52 82
快速排序的遞歸算法本質(zhì)上就是一個(gè)二叉樹的先序遍歷過程浩淘，先處理當(dāng)前根節(jié)點(diǎn)，然后依次處理左右部分（左子樹和右子樹）吴攒。
將快速排序遞歸算法轉(zhuǎn)換為非遞歸相當(dāng)于將二叉樹先序遍歷遞歸算法轉(zhuǎn)為非遞歸算法张抄。
時(shí)間復(fù)雜度和空間復(fù)雜度計(jì)算
1.時(shí)間復(fù)雜度：
①問題描述
快速排序?qū)⒁?guī)模為n的問題分解為2個(gè)子問題，每個(gè)子問題的規(guī)模為n/2洼怔，每個(gè)子問題繼續(xù)遞歸實(shí)現(xiàn)重復(fù)操作署惯。
②公式定義：
T(n) = 2T(n/2) + f(n) = 2T(n/2) + O(n)
公式說明：T(n)表示總的時(shí)間復(fù)雜度，T(n/2)為分一次得到的子問題的時(shí)間復(fù)雜度镣隶，f(n)表示執(zhí)行一次分裂需要做多少次操作极谊，快速排序左右索引依次向中間走，總共需要遍歷n次安岂，所以f(n) = O(n)轻猖。
③求解T(n)的方法：
首先理解一個(gè)數(shù)組通過二分法對(duì)半分，一直到每一個(gè)數(shù)據(jù)都被分開隔離需要多少次域那？
答案：2^k = n咙边，所以 k = lgn （以2為底的對(duì)數(shù)）
④生成函數(shù)法求解T(n)
T(n)=2T(n/2)+n
=2[2T(n/4)+n/2]+n = 4T(n/4) + 2n
=4[2T(n/8)+n/4]+2n = 8T(n/8) + 3n
=16T(n/16)+4n
=……
=(2^k) * T(n/(2^k)) + kn
=(2^lgn) * T(n/(2^lgn)) + nlgn
=nT(1)+nlgn
2.空間復(fù)雜度
①問題描述
a. 借用的輔助空間的大小
b. 遞歸時(shí)壓入棧的數(shù)據(jù)所占用的空間。
②最壞情況：完全逆序
待續(xù)
