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

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