穩定的排序算法如下表所示冒泡排序(bubble1插入排序(insertion1歸并排序(mergeO(nlog桶排序(bucket基數排序(RadixO(dn)（d是常數二叉樹排序(BinarytreeO(nlog不穩定的排序算法如下表所示選擇排序(selection1排序(sO(nlog1堆排序O(nlog1快速排序平均是O(nlogn)，是O(log（一）的速度要求。而一般我們所謂的算法的性能主要是指算法的復雜度，一般用OO若存在一個常量Kn0n>=n0時，有f(n)<=K×g(n),f(n)=O(g(n))O(N2第二部分是高級排序算法，復雜度為O(N×Log2(N))或小于O(N2)。這里我們只介紹3種算法。另外還1R：凡掃描到本原則的輕氣泡，就使其向上“飄浮”。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。2（2）S排序(排序（3）O(n)的空間。(1)nn≤40)，可采用插入排序或選擇排序。當記錄規模較小時，插入排序較好；反之，因為選擇移動的記錄數少于插人，應選選擇排序為宜。(2)若文件初始狀態基本有序(指正序)，則應選用插人、冒泡或隨機的快速排序為宜；(3)nO(N×Log2(N))速排序、堆排序或歸并排序。排序的平均時間最短；快速排序不適合用于“幾乎已排好序”或“幾乎正好倒序”的數據。在此情況O(N2)。堆排序所需的輔助空間少于快速排序，并且不會出現快速排序可能出現的S排序的時間復雜度在數學上沒有解決，大致可以認為是O(n(1￡)),其中￡是介于0和1之間的（二）O(N)；R[low..high]是當前的查找區間)：首先確定該區間的中點位置R[mid].key>K，R[mid..n].keysK，因此若表中存在關鍵字等于KmidR[1..mid-1]R[1..mid-R[mid].key<K，KmidR[mid+1..n]中，即新的查找區間是右R[mid+1..n]。下一次查找是針對新的查找區間進行的。R[1..n]開始，每經過一次與當前查找區間的中點位置上的結點關鍵字的比K結點，或者直至當前的查找區間為空(即查找失敗)時為止。分塊查找(BlockingSearch)又稱索引順序查找。它是一種性能介于順序查找和二分查找之間的查找分塊查找表的結構由“分塊有序”的線性表和索引表組成R[1..n]bb-1s=n/b，bs；每一塊中的關ID[l..b]，即：ID[i](1≤i≤b)塊的最大關鍵字及該塊在表RR(1)nn≤40)，(2)nO(Log2(N))的二分查找方法。(3)若文件初始狀態分塊有序，且n一、冒泡排數放面，大數放在后面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放后。然后比較第2個數和第3個數，將小數放前，大數放后，2個數和第3個數的交換，使得第1個數不再小于第2個數），將小數放前，二、插入排主要有直接插入排序和排序。如果該元素（已排序）3，三、歸并排nn12n2435、將另一序列剩下的所有元素直接到合并序列尾四、桶排n[0，1)在桶排序算法的代碼中，假設輸入是個含n個元素的數組A，且每個元素滿足0≤A[i]<1。另外還需要一個輔助數組B[O..n-1]來存放鏈表實現的桶，并假設可以用某種機制來這些表。布分到N個桶中，每一個桶都用一個鏈表來 五、基數排C0<=Kj<=Crd-1(0<=j<=rd),可rdrd=10,C0=0,C9=9,d基數排序的基本思想是：從低位到依次對待排序的關鍵碼進行分配和d基數排序從低位到進行，使得最后一次計數排序完成后，數組有序，最后按年排序，僅需排序三次。但是如果先排序就沒這么簡單了?；?、二叉樹排二叉排序樹（BinarySortTree）又稱二叉查找樹。它或者是一棵空1、首先執行查找算法，找出結點的父親結點2、判斷結點是其父親結點的左、右兒子。將結點作為葉子結點插3z1、如果結點z沒有，則修改其父結點p[z]，使NIL為其2、如果結點z只有一個，則可以通過在其子結點與父結點間建立z；3、如果結點z只有兩個，先刪除z的后繼y(它沒有左)，再yz七、選擇排與第1個記錄交換，然后在其余的記錄內選出排序碼最小的記錄，與第2個記 八、排(S)排序的基本思想是：先取一個小于n的整數d1作為d1d1d2<d1di=1，插入排序為止。該方法實質上是一種分組插入方法。d1=n/2，di+1=di/21，di九、堆排(1)ki≤K2i且或(2)Ki≥K2i且ki≥K2i+1(1≤i≤若將此序列所的向量R[1..n]看作是一棵完全二叉樹的結構則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子(若存在)結點的關鍵字。1R[1..n]R[1..n-1]R[n]，R[1..n-3、由于交換后新的根R[1]可能堆性質，故應將當前無序區R[1..n-1]R[1..n-1]R[1]和該區間的最后一R[n-1]R[1..n-2]R[n-1..n]，且十、快速排第一步，在待排序的n個記錄中任取一個記錄，以該記錄的排序碼為準，將所有記錄分成兩組，第1組各記錄的排序碼都小于等于該排序碼，第2一、插入排一、插入排 排二、交換排 一、插入排1）直接插入排 算法演時間復雜度：平均情況—view情況— 輔助空間 穩定性：穩voidInsertSort(SqList&L)Lintfor(i=2;i<=L.length;if(LT(L.r[i].key,L.r[i-1].key))22）折半插入排時間復雜度：平均情況— 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）排 算法演 返時間復雜度：理想情況— viewvoidSInsert(SqList&L,intdk)//對順序表L作一趟插入排序。本算法對算法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]對順序表L作排序for(int二、二、交換排1）冒泡排 算法演時間復雜度：平均情況—情況— 輔助空間 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）快速排 算法演時間復雜度：平均情況— intintPartition(SqList&L,intlow,inthigh)LL.r[low..high]//并返回其所在位置，此時，在它之前（后）的記錄均不大（小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]//并返回其所在位置，此時，在它之前（后）的記錄均不大（小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）簡單選擇排 算法演時間復雜度：平均情況— 輔助空間 view}//}//voidSelectSort(SqList&L)Lintfor(i=1;i<L.length;++i)ij=SelectMinKey(L, L.r[i..L.length]if(i!=j) iRedType}}}//2）堆排 算法演 返時間復雜度：平均情況— 情況— viewvoidHeapAdjust(HeapType&H,ints,intm)H.r[s..m]H.r[s].keyH.r[s]H.r[s..m]//（對其中記錄的關鍵字而言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) //將堆頂記錄和當前排序子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..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]}五五、基數排 算法演時間復雜度：平均情況—情況— 輔助空間 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