數(shù)據(jù)結(jié)構(gòu)0406快速排序

快速排序數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第1頁。快速排序的基本思想快速排序是由冒泡排序改進而來的。它的基本思想是在待排序的n個記錄中任取一個記錄（通常取第一個記錄）作為樞軸（或支點），設(shè)其關(guān)鍵字為pivotkey。經(jīng)過一趟排序后，把所有關(guān)鍵字大于pivotkey的記錄交換到后面，結(jié)果將待排序記錄分成兩個子表，最后將樞軸放置在分界處的位置。然后，分別對左右子表重復上述過程，甚至每一個子表只有一個記錄時，排序完成。數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第2頁。例題4938659776132749*ijj初始關(guān)鍵字27386597761349*ij進行1次交換后i設(shè)待排序記錄關(guān)鍵字序列為（4938659776132749*）數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第3頁。例題27386597761349*j進行2次交換后ij27386597761349*進行3次交換后iji數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第4頁。例題27381376976549*ijj進行4次交換后27381376976549*完成一趟排序49數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第5頁。例題4927381376976549*數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第6頁。例題對左右子表繼續(xù)進行劃分下去的話，其對應(yīng)的遞歸樹為：492776133849*9765數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第7頁。快速排序的算法intPartition(SqList&L,intlow,inthigh){//交換順序表L中子序列L.r[low..high]的記錄，使樞軸記錄到位，//并返回其所在位置，此時，在它之前（后）的記錄均不大（?。┯谒麷eyTypepivotkey;L.r[0]=L.r[low];//用子表的第一個記錄作樞軸記錄pivotkey=L.r[low].key;//樞軸記錄關(guān)鍵字while(low<high){//從表的兩端交替地向中間掃描while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];//將比樞軸記錄小的記錄移到低端while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];//將比樞軸記錄大的記錄移到高端}L.r[low]=L.r[0];//樞軸記錄到位returnlow;//返回樞軸位置}//Partition數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第8頁?？焖倥判虻乃惴╲oidQSort(SqList&L,intlow,inthigh){//對順序表L中的子序列L.r[low..high]進行快速排序intpivotloc;if(low<high){//長度大于1pivotloc=Partition(L,low,high);//將L.r[low..high]一分為二QSort(L,low,pivotloc-1);//對低子表遞歸排序，pivotloc是樞軸位置QSort(L,pivotloc+1,high);//對高子表遞歸排序}}//QSort數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第9頁。快速排序的算法voidQuickSort(SqList&L){//對順序表L進行快速排序QSort(L,1,L.length);}//QuickSort其中Partition函數(shù)是進行劃分的過程，QSort函數(shù)對Partition函數(shù)進行調(diào)用，QSort是個遞歸函數(shù)。數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第10頁?？焖倥判蛩惴ǖ男蕰r間復雜度方面，最好情況下，每一趟劃分后，樞軸都能將記錄序列分成兩個長度大致相等的子表。這個時候，快速排序?qū)?yīng)的遞歸樹的深度和log2n是線性的關(guān)系，這一點類似于完全二叉樹。由于每一層對樞軸進行定位所需時間為O(n)，所以總的時間復雜度是O(nlog2n)。數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第11頁?？焖倥判蛩惴ǖ男实窃谧顗那闆r下，在待排序序列已經(jīng)排好序的情況下，其遞歸樹成為單支樹。比如待排序記錄關(guān)鍵字序列為(1,2,3,4,5)，并總是使用第一個關(guān)鍵字作為樞軸的話。遞歸樹就變成了12345數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第12頁?？焖倥判蛩惴ǖ男蔬@樣的話，樹的深度和樹的結(jié)點樹是一樣的，所以時間復雜度為O(n2)。這種情況下，快速排序完全蛻化到簡單排序的水平。樞軸記錄的合理選擇可以避免這種情況的出現(xiàn)，比如利用“三者取中”的方法：比較當前表中的第一個記錄、最后一個記錄、中間一個記錄的關(guān)鍵字，取關(guān)鍵字居中的記錄作為樞軸記錄，并將該記錄調(diào)換到第一個記錄的位置。數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第13頁?？焖倥判蛩惴ǖ男士臻g復雜度方面，由于快速排序是遞歸算法，執(zhí)行時需要一個棧來存在相應(yīng)的數(shù)據(jù)。棧的深度與遞歸樹的深度是一致的，所以最好情況下是O(log2n)，最壞情況下是O(n)。數(shù)據(jù)結(jié)構(gòu)0406快速排序全文共15頁，當前為第14頁?？?/p>