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

冒泡排序(bubble1插入排序(insertion1歸并排序(mergeO(nlog桶排序(bucket基數(shù)排序(RadixO(dn)（d是常數(shù)二叉樹(shù)排序(BinarytreeO(nlog選擇排序(selection1排序(sO(nlog1堆排序O(nlog1快速排序平均是O(nlogn)，是O(log（一）的速度要求。而一般我們所謂的算法的性能主要是指算法的復(fù)雜度，一般用OO若存在一個(gè)常量Kn0，使當(dāng)n>=n0時(shí)，有f(n)<=K×g(nf(n)O(g(n)R：掃到原的氣，使向“浮。此復(fù)行直最任兩氣都輕（2）S排序(排序首先需要一個(gè)遞減的步長(zhǎng)gap1。工作原理是首先對(duì)相隔較遠(yuǎn)的元素的所有內(nèi)容O(n)的空間。(1)若n≤423nO(×Lg(N)排序的平均時(shí)間最短；快速排序不適合用于“幾乎已排好序”或“幾乎正好倒序”的數(shù)據(jù)。在此情況O(N2)。堆排序所需的輔助空間少于快速排序，并且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的S排序的時(shí)間復(fù)雜度在數(shù)學(xué)上沒(méi)有解決，大致可以認(rèn)為是O(n(1￡)),其中￡是介于0和1之間的（二）O(N)；O(Log2(N))。R[low..high]是當(dāng)前的查找區(qū)間)：KR[mid].key找R[mid].key>KR[mid..n].keysK，因此若表中存在關(guān)鍵字等于KmidR[1..mid-1R[1..mid-R[mid].key<KKmidR[mid+1..n]中，即新的查找區(qū)間是右R[mid+1..n]。下一次查找是針對(duì)新的查找區(qū)間進(jìn)行的。因此，從初始的查找區(qū)間R[1..n]開(kāi)始，每經(jīng)過(guò)一次與當(dāng)前查找區(qū)間的中點(diǎn)位置上的結(jié)點(diǎn)關(guān)鍵字的比較，就可確定查找是否成功，不成功則當(dāng)前的查找區(qū)間就縮小一半。這一過(guò)程重復(fù)直至找到關(guān)鍵字為K分塊查找(BlockingSearch)又稱(chēng)索引順序查找。它是一種性能介于順序查找和二分查找之間的查找R[1..nbb-1s=n/bbs；每一塊中的關(guān)塊的最大關(guān)鍵字及該塊在表RR(1)nn≤40(2n雜度為O(Log2(N))的二分查找方法。(3)若文件初始狀態(tài)分塊有序，且n數(shù)放面，大數(shù)放在后面。即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將小主要有直接插入排序和排序。如果該元素（已排序）3，時(shí)，把含有nn12到長(zhǎng)度為n2435、將另一序列剩下的所有元素直接到合并序列尾桶排序的基本思想就是把區(qū)間[0，1)n稱(chēng)桶，然后將n[0，1)在桶排序算法的代碼中，假設(shè)輸入是個(gè)含n個(gè)元素的數(shù)組A，且每個(gè)元素0≤A[i]<1。另外還需要一個(gè)輔助數(shù)組B[O..n-1]來(lái)存放鏈表實(shí)現(xiàn)的桶，并假設(shè)可以用某種機(jī)制來(lái)這些表。我的理解是：桶排序相當(dāng)于一個(gè)N路的歸并排序，首先將輸入按均勻分布分到N個(gè)桶中，每一個(gè)桶都用一個(gè)鏈表來(lái) 就是每一路）進(jìn)行排序，最后將NC0<=Kj<=Crd-1(0<=j<=rd),可rdrd=10,C0=0,C9=9,d基數(shù)排序的基本思想是：從低位到依次對(duì)待排序的關(guān)鍵碼進(jìn)行分配和收集，經(jīng)過(guò)d基數(shù)排序從低位到進(jìn)行，使得最后一次計(jì)數(shù)排序完成后，數(shù)組有序，最后按年排序，僅需排序三次。但是如果先排序就沒(méi)這么簡(jiǎn)單了?；业睦斫馐牵夯鶖?shù)排序算法中，數(shù)據(jù)可分解為d二叉排序樹(shù)（BinarySortTree）又稱(chēng)二叉查找樹(shù)。它或者是一棵空1、首先執(zhí)行查找算法，找出結(jié)點(diǎn)的父親結(jié)點(diǎn)2、判斷結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將結(jié)點(diǎn)作為葉子結(jié)點(diǎn)3將結(jié)點(diǎn)z1、如果結(jié)點(diǎn)z沒(méi)有，則修改其父結(jié)點(diǎn)p[z]，使NIL為其2、如果結(jié)點(diǎn)z只有一個(gè)，則可以通過(guò)在其子結(jié)點(diǎn)與父結(jié)點(diǎn)間建立一條鏈來(lái)刪除z；3、如果結(jié)點(diǎn)z只有兩個(gè)，先刪除z的后繼y(它沒(méi)有左)，再用yzPS：xkey[x]中的關(guān)鍵字中最小者的那個(gè)與第1個(gè)記錄交換，然后在其余的記錄內(nèi)選出排序碼最小的記錄，與第2個(gè)記 八、排(S)排序的基本思想是：先取一個(gè)小于n的整數(shù)d1作為d1=n/2，di+1=di/21，di堆的定義：nKl，K2，…，Kn(Heap)，當(dāng)且僅當(dāng)該(1)ki≤K2i且或(2)Ki≥K2i且ki≥K2i+1(1≤i≤1R[1..n]2R[1](R[n]交R[1..n-1]R[n]，R[1..n-3、由于交換后新的根R[1]可能堆性質(zhì)，故應(yīng)將當(dāng)前無(wú)序區(qū)R[1..n-1]R[1..n-1]R[1]和該區(qū)間的最后一R[n-1]R[1..n-2]R[n-1..n]，且R[1..n-2].keys≤R[n-1..n].keys，R[1..n-2]調(diào)整為第一步，在待排序的n 算法演view voidInsertSort(SqList&L)//對(duì)順序表Lintfor(i=2;i<=L.length;if(LT(L.r[i].key,L.r[i-1].key)) 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)//對(duì)順序表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] 入}}// 算法演 返 情況— 穩(wěn)定性：不穩(wěn)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 算法演 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[0exchange=TRUE;}if(!exchange)}//endfor(} 算法演 輔助空間 穩(wěn)定性：viewviewintPartition(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í)，在它之前（后）的記錄均不大（小KeyTypeL.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)//對(duì)順序表LL.r[low..highintif pivotloc=Partition(L,low, QSort(L,low,pivotloc-1);pivotlocQSort(L,pivotloc+1, }}//voidQuickSort(SqList&L) //對(duì)順序表LQSort(L,1, 算法演 view}//}//voidSelectSort(SqList&L)//對(duì)順序表Lintfor(i=1;i<L.length;++i){//選擇第ij=SelectMinKey(L, L.r[i..L.length]if(i!=j) 與第iRedType}}}// 算法演 輔助空間 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; rc插入在位置sH.r[s]= s=}H.r[s]= }//voidHeapSort(HeapType&H)//對(duì)順序表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]}}// 算法演 輔助空間 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..tintRedTypeif(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]} 算法演情況— 輔助空間 穩(wěn)定性view}//voidMergeSort(SqList&L)//對(duì)順序表LMSort(L.r,L.r,1,}//voidDistribute(SLList&L,inti,ArrType&f,ArrType&e)//靜態(tài)鏈表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 p=L.r[p].next)j=L.r[p].keys[i]- //將記錄中第i[0..RADIX-if(!f[j])f[j]=elseL.r[e[j]].next=e[j]= //將p插入第j}}//voidCollect(SLList&L,inti,ArrTypef,ArrTypee)keys[i]f[0..RADIX-1]所指各子表依次鏈//一個(gè)鏈表，e[0..RADIX-1]intfor(j=0;!f[j];j++); ，succ數(shù):++L.r[0].next=f[j]; L.r[0].nextt=while(j<RADIX)for(j=j+1;j<RADIX&&!f[j];j++); if(j