實(shí)驗(yàn)八快速排序

《實(shí)驗(yàn)八快速排序》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、實(shí)驗(yàn)八快速排序一.實(shí)驗(yàn)?zāi)康?、熟悉和掌握快速排序的基本思想。2、了解并掌握快速排序的結(jié)構(gòu)。3、掌握和熟悉內(nèi)部排序中快速排序的實(shí)現(xiàn)方法。二.實(shí)驗(yàn)預(yù)備知識(shí)快速排序是市起泡排序改進(jìn)而得來(lái)的。起泡排序的算法思想是：通過(guò)無(wú)序區(qū)中相鄰紀(jì)錄關(guān)鍵字間的比較和位置的交換，使關(guān)鍵字最小的紀(jì)錄如氣泡一般逐漸往上“漂浮”直至“水面”。整個(gè)算法是從最下面的紀(jì)錄開(kāi)始，對(duì)每?jī)蓚€(gè)相鄰的關(guān)鍵字進(jìn)行比較，且使關(guān)鍵字較小的紀(jì)錄換至關(guān)鍵字較大的紀(jì)錄之上。，使得經(jīng)過(guò)一趟起泡排序后，關(guān)鍵字最小的記錄到達(dá)最上端，接著，再在剩下的紀(jì)錄中找關(guān)鍵字最小的紀(jì)錄，并把它換在第二個(gè)位置上。依次類推，一直到所有記錄

2、都有序?yàn)橹?。快速排序的基本思想是在待排序的n個(gè)記錄中任選一個(gè)記錄，將該紀(jì)錄放入最終位置后，數(shù)據(jù)序列被分割成兩部分。所有關(guān)鍵字比較該紀(jì)錄關(guān)鍵字小的放置在前一部分，所有比他大的放置在后一部分，并將該紀(jì)錄排在這兩部分的中間，這個(gè)過(guò)程稱作一趟快速排序。之后對(duì)分割成的兩部分分別重復(fù)上述過(guò)程，直到每個(gè)部分內(nèi)只有一個(gè)記錄為止?？焖倥判蚴遣环€(wěn)定的。從平均時(shí)間性能而言，快速排序最佳，其時(shí)間復(fù)雜性為O(nlog2n)。但在最壞情況下，即對(duì)幾乎是排序好的輸入序列，該算法的效率很低，近似于0(『)。對(duì)于較小的n值,該算法效果不明顯；反之，對(duì)較大的n值，效果較好。初始關(guān)鍵字[707

3、3692393181168]第一趟排序后[6811692318]70[9373]第二趟排序后[181123]68[69]70[9373]第三趟排序后111823686970[93731第四趟排序后1118236869707393一.實(shí)驗(yàn)內(nèi)容從時(shí)間上看，快速排序的平均性能優(yōu)于英它各種排序方法，從空間上看，快速排序只需一個(gè)?？臻g來(lái)實(shí)現(xiàn)遞歸。最壞的情況下，一個(gè)長(zhǎng)度為n的序列，其快速排序所需棧的最大深度為no最小深度為O(logn)o實(shí)驗(yàn)基本思想：設(shè)有n個(gè)記錄的序列，運(yùn)用快速排序法將其按升序排列，并輸出排列結(jié)果。實(shí)驗(yàn)源程序算法如下：quicksort(intr[]

4、,ints,intt)/*把r[s]至r[t]的元素進(jìn)行快速排序*/{inti=s;intj=t;if(s=r[01)j-;r[i]=r[j]；i++；while(i

5、寫(xiě)出每趟排序的結(jié)果和實(shí)驗(yàn)報(bào)告。#include#includevoidquicksort(intr[],ints,intt)排序*/{intm;/*m為監(jiān)視哨*/inti=s;intj=t;/*把r[s]至r[t]的元素進(jìn)行快速m=r[s];do{while(i=m)j—;{r[i]=r[j]；i++；}while(i

6、rt(rj+l,t);intmain(void)inta[12]={67,l,3,4,12,8,9,O,5,43,55,15},i;quicksort(a,0,l1);foT(i二0;ivl2;i++)printf(n%d”,a[i]);return0;}五、強(qiáng)化與提高1、已知序歹!J{503,55,78,99,10,953,487,41,13,776,314},采用快速排序?qū)υ撔蛄凶鹘敌蚺判驎r(shí)的每一趟結(jié)果。2、對(duì)于快速排序的非遞歸算法，可用隊(duì)列實(shí)現(xiàn)嗎？說(shuō)明理由。3、寫(xiě)出快速排序的非遞歸算法。