數(shù)據(jù)結(jié)構(gòu)排序算法總結(jié)

穩(wěn)定的排序算法如下表所示冒泡排序(bubble1插入排序(insertion1歸并排序(mergeO(nlog桶排序(bucket基數(shù)排序(RadixO(dn)（d是常數(shù)二叉樹排序(BinarytreeO(nlog不穩(wěn)定的排序算法如下表所示選擇排序(selection1排序(sO(nlog1堆排序O(nlog1快速排序平均是O(nlogn)，是O(log（一）的速度要求。而一般我們所謂的算法的性能主要是指算法的復(fù)雜度，一般用OO若存在一個(gè)常量Kn0n>=n0時(shí)，有f(n)<=K×g(n),f(n)=O(g(n))O(N2第二部分是高級(jí)排序算法，復(fù)雜度為O(N×Log2(N))或小于O(N2)。這里我們只介紹3種算法。另外還1R：凡掃描到本原則的輕氣泡，就使其向上“飄浮”。如此反復(fù)進(jìn)行，直到最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。2（2）S排序(排序（3）O(n)的空間。(1)nn≤40)，可采用插入排序或選擇排序。當(dāng)記錄規(guī)模較小時(shí)，插入排序較好；反之，因?yàn)檫x擇移動(dòng)的記錄數(shù)少于插人，應(yīng)選選擇排序?yàn)橐恕?2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用插人、冒泡或隨機(jī)的快速排序?yàn)橐耍?3)nO(N×Log2(N))速排序、堆排序或歸并排序。排序的平均時(shí)間最短；快速排序不適合用于“幾乎已排好序”或“幾乎正好倒序”的數(shù)據(jù)。在此情況O(N2)。堆排序所需的輔助空間少于快速排序，并且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的S排序的時(shí)間復(fù)雜度在數(shù)學(xué)上沒有解決，大致可以認(rèn)為是O(n(1￡)),其中￡是介于0和1之間的（二）O(N)；R[low..high]是當(dāng)前的查找區(qū)間)：首先確定該區(qū)間的中點(diǎn)位置R[mid].key>K，R[mid..n].keysK，因此若表中存在關(guān)鍵字等于KmidR[1..mid-1]R[1..mid-R[mid].key<K，KmidR[mid+1..n]中，即新的查找區(qū)間是右R[mid+1..n]。下一次查找是針對(duì)新的查找區(qū)間進(jìn)行的。R[1..n]開始，每經(jīng)過一次與當(dāng)前查找區(qū)間的中點(diǎn)位置上的結(jié)點(diǎn)關(guān)鍵字的比K結(jié)點(diǎn)，或者直至當(dāng)前的查找區(qū)間為空(即查找失敗)時(shí)為止。分塊查找(BlockingSearch)又稱索引順序查找。它是一種性能介于順序查找和二分查找之間的查找分塊查找表的結(jié)構(gòu)由“分塊有序”的線性表和索引表組成R[1..n]bb-1s=n/b，bs；每一塊中的關(guān)ID[l..b]，即：ID[i](1≤i≤b)塊的最大關(guān)鍵字及該塊在表RR(1)nn≤40)，(2)nO(Log2(N))的二分查找方法。(3)若文件初始狀態(tài)分塊有序，且n一、冒泡排數(shù)放面，大數(shù)放在后面。即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，2個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前，二、插入排主要有直接插入排序和排序。如果該元素（已排序）3，三、歸并排nn12n2435、將另一序列剩下的所有元素直接到合并序列尾四、桶排n[0，1)在桶排序算法的代碼中，假設(shè)輸入是個(gè)含n個(gè)元素的數(shù)組A，且每個(gè)元素滿足0≤A[i]<1。另外還需要一個(gè)輔助數(shù)組B[O..n-1]來存放鏈表實(shí)現(xiàn)的桶，并假設(shè)可以用某種機(jī)制來這些表。布分到N個(gè)桶中，每一個(gè)桶都用一個(gè)鏈表來 五、基數(shù)排C0<=Kj<=Crd-1(0<=j<=rd),可rdrd=10,C0=0,C9=9,d基數(shù)排序的基本思想是：從低位到依次對(duì)待排序的關(guān)鍵碼進(jìn)行分配和d基數(shù)排序從低位到進(jìn)行，使得最后一次計(jì)數(shù)排序完成后，數(shù)組有序，最后按年排序，僅需排序三次。但是如果先排序就沒這么簡(jiǎn)單了。基六、二叉樹排二叉排序樹（BinarySortTree）又稱二叉查找樹。它或者是一棵空1、首先執(zhí)行查找算法，找出結(jié)點(diǎn)的父親結(jié)點(diǎn)2、判斷結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插3z1、如果結(jié)點(diǎn)z沒有，則修改其父結(jié)點(diǎn)p[z]，使NIL為其2、如果結(jié)點(diǎn)z只有一個(gè)，則可以通過在其子結(jié)點(diǎn)與父結(jié)點(diǎn)間建立z；3、如果結(jié)點(diǎn)z只有兩個(gè)，先刪除z的后繼y(它沒有左)，再yz七、選擇排與第1個(gè)記錄交換，然后在其余的記錄內(nèi)選出排序碼最小的記錄，與第2個(gè)記 八、排(S)排序的基本思想是：先取一個(gè)小于n的整數(shù)d1作為d1d1d2<d1di=1，插入排序?yàn)橹?。該方法?shí)質(zhì)上是一種分組插入方法。d1=n/2，di+1=di/21，di九、堆排(1)ki≤K2i且或(2)Ki≥K2i且ki≥K2i+1(1≤i≤若將此序列所的向量R[1..n]看作是一棵完全二叉樹的結(jié)構(gòu)則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字。1R[1..n]R[1..n-1]R[n]，R[1..n-3、由于交換后新的根R[1]可能堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]R[1..n-1]R[1]和該區(qū)間的最后一R[n-1]R[1..n-2]R[n-1..n]，且十、快速排第一步，在待排序的n個(gè)記錄中任取一個(gè)記錄，以該記錄的排序碼為準(zhǔn)，將所有記錄分成兩組，第1組各記錄的排序碼都小于等于該排序碼，第2一、插入排一、插入排 排二、交換排 一、插入排1）直接插入排 算法演時(shí)間復(fù)雜度：平均情況—view情況— 輔助空間 穩(wěn)定性：穩(wěn)voidInsertSort(SqList&L)Lintfor(i=2;i<=L.length;if(LT(L.r[i].key,L.r[i-1].key))22）折半插入排時(shí)間復(fù)雜度：平均情況— viewL.r[i]L.r[0]= for(j=i- LT(L.r[0].key, --L.r[j+1]= L.r[j+1]= }}//voidBInsertSort(SqList&L)Lintfor(i=2;i<=L.length;++i)L.r[0]= L.r[i]low= high=i-07while(low<=high){ r[low..high]中折半查找有序08m=if(LT(L.r[0].key,L.r[m].key))high=m- elselow }for(j=i-1;j>=high+1;--j)L.r[j+1]= 移L.r[high+1] 入}}//3）排 算法演 返時(shí)間復(fù)雜度：理想情況— viewvoidSInsert(SqList&L,intdk)//對(duì)順序表L作一趟插入排序。本算法對(duì)算法10.1作了以下修 1.dk， 2.r[0]j<=0intfor(i=dk+1;i<=L.length;if(LT(L.r[i].key,L.r[i-dk].key))L.r[i]插入有L.r[0] for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-L.r[j+dk]= L.r[j+dk]= }}//SvoidSSort(SqList&L,intdlta[],intt)//按增量序列dlta[0..t-1]對(duì)順序表L作排序for(int二、二、交換排1）冒泡排 算法演時(shí)間復(fù)雜度：平均情況—情況— 輔助空間 viewSInsert(L, dlta[k]}//voidBubbleSort(SeqListR)intBooleanexchange;for(i=1;i<n;i++){exchange="FALSE;"j="n-1;j">=i;jR[i..n]自下向上掃描if(R[j+1].key<R[j].key){//R[0]=R[j+1];//R[0]exchange=TRUE;}if(!exchange)}//endfor(}22）快速排 算法演時(shí)間復(fù)雜度：平均情況— intintPartition(SqList&L,intlow,inthigh)LL.r[low..high]//并返回其所在位置，此時(shí)，在它之前（后）的記錄均不大（小KeyTypeRedTypepivotkey=L.r[low].key; while(low<high){ while(low<high&&L.r[high].key>=pivotkey)-- 的記錄交換到while <high&&L.r[low].key< }return }//intPartition(SqList&L,intlow,inthigh)LL.r[low..high]//并返回其所在位置，此時(shí)，在它之前（后）的記錄均不大（小KeyTypeviewviewL.r[0]=L.r[low]; pivotkey= while(low<high){ while(low<high&&L.r[high].key>=pivotkey)--L.r[low]= while <high&& <L.r[high]= }L.r[low]= return }//voidQSort(SqList&L,intlow,inthigh)LL.r[low..high]intif pivotloc=Partition(L,low, QSort(L,low,pivotloc-1);，pivotlocQSort(L,pivotloc+1,high); }}//voidQuickSort(SqList&L) LQSort(L,1,三三、選擇排1）簡(jiǎn)單選擇排 算法演時(shí)間復(fù)雜度：平均情況— 輔助空間 view}//}//voidSelectSort(SqList&L)Lintfor(i=1;i<L.length;++i)ij=SelectMinKey(L, L.r[i..L.length]if(i!=j) iRedType}}}//2）堆排 算法演 返時(shí)間復(fù)雜度：平均情況— 情況— viewvoidHeapAdjust(HeapType&H,ints,intm)H.r[s..m]H.r[s].keyH.r[s]H.r[s..m]//（對(duì)其中記錄的關(guān)鍵字而言intRedTyperc=for(j=2*s;j<=m;j*=2) key選if(jm&&H.r[j].keyH.r[j+1].key)++j;jkeyif(rc.key>=H.r[j].key)break; rcsH.r[s]= s=}H.r[s]= }//voidHeapSort(HeapType&H)HintRedTypefor(i=H.length/2;i>0;-- H.r[1..H.length]HeapAdjust(H,i,H.lengthfor(i=H.length;i>1;--i) //將堆頂記錄和當(dāng)前排序子Hr[1..i]HeapAdjust(H,1,i- H.r[1..i-1]}}//四四、歸并排 算法演時(shí)間復(fù)雜度：平均情況—情況— viewvoidMerge(RedTypeSR[],RedTypeTR[],inti,intm,intn)SR[i..m]SR[m+1..n]intfor(j=m+1, i<=m&&j< ++k)SRifLQ(SR[i].key,SR[j].key)TR[k]=elseTR[k]=}if(i<=m) //TR[k..n]=SR[i..m]; TRwhile(k<=n&&i<=m)if(j< //將剩余的SR[j..n]到while(k<=n <=n)}//voidMSort(RedTypeSR[],RedTypeTR1[],ints,intt)SR[s..t]TR1[s..t]intRedTypeif(s==t)TR1[t]=else SR[s..t]平分為SR[s..m]SR[m+1..t] SR[s..m]歸并為有TR2[s..m] SR[m+1..t]Merge(TR2,TR1,s,m,t);TR2[s..m]TR2[m+1..t]歸TR1[s..t]}五五、基數(shù)排 算法演時(shí)間復(fù)雜度：平均情況—情況— 輔助空間 view}//voidMergeSort(SqList&L)LMSort(L.r,L.r,1,}//voidDistribute(SLList&L,inti,ArrType&f,ArrType&e)Lr(keys[0],...,keys[i-1])ikeys[i]RADIXkeys[i]相同。f[0..RADIX-1]intj,for(j=0;j<RADIX;++j)f[j]=0; for