【精品數(shù)據結構】排序算法.ppt

《【精品數(shù)據結構】排序算法.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、第10章排序算法1§10.1概述排序的主要目的是便于以后在已排序的集合中查找檢索某一成員若干概念關鍵字排序排序的穩(wěn)定性內排序外排序多鍵排序2§10.1概述排序方法進行分類插入排序交換排序選擇排序歸并排序分配排序3§10.1概述算法的時間復雜性通常只考慮鍵值的比較次數(shù)和記錄的移動次數(shù)評價排序的另一個主要標準是執(zhí)行算法所需的附加空間4§10.2插入排序插入排序的基本方法是：每步將一個待排序的記錄按其關鍵字的大小插到前面已經排序的序列中的適當位置，直到全部記錄插入完畢為止。5§10.2.1直接插入排序初始鍵值序列[46]58154590181062i=2[4

2、658]154590181062i=3[154658]4590181062i=4[15454658]90181062i=5[1545465890]181062i=6[151845465890]1062i=7[10151845465890]62i=8[1015184546586290]圖10?1直接插入排序過程示例6§10.2.1直接插入排序可以將插入排序粗略地描述為：SortInsertion(inta[],longn){for(i=1;i

3、tion(inta[],longn){intx,i,,j;for(i=1;i=0&&x

4、記錄集的一端移動，鍵值較小的記錄向另一端移動。10§10.3.1冒泡排序設初始記錄集為2030104533225550則第一趟冒泡的過程為：2030104533225550//20與30比較，未交換2010304533225550//30與10比較，交換2010304533225550//30與45比較，未交換2010303345225550//45與33比較，交換2010303322455550//45與22比較，交換10303322455550//45與55比較，未交換2010303322455055//55與50比較，交換11§10.3.1冒泡排

5、序每趟的結果1020302233455055//第2趟1020223033455055//第3趟1020223033455055//第4趟1020223033455055//第5趟1020223033455055//第6趟1020223033455055//第7趟1020223033455055//第8趟12§10.3.3快速排序(一)基本思想基本思想是：在待排序的n個記錄中任取一個記錄（例如就取第一個記錄），以該記錄的鍵值為標準，將所有記錄分為兩組（一般都是無序的），使得第一組中各記錄的鍵值均小于或等于該鍵值，第二組中各記錄的鍵值均大于該鍵值。然后把

6、該記錄就排在這兩組的中間（這也是該記錄最終的位置）。此稱為一趟分割，對所分成的兩組再分別重復上述方法，直到所有記錄都排在適當位置為止。13§10.3.3快速排序(二)分割算法一趟快速排序的具體做法是：設兩個指針i和j，它們的初值分別為0、n-1，且把a[0]送入工作單元x中保存（選第一個記錄為標準），然后比較a[j]和x，若a[j]>x，則j減1后繼續(xù)與x比較，直至r[j]＜=x，然后，將a[j]移至a[i]的位置，令i加1，接著進行a[i]和x的比較，若a[i]

7、，令j減1，之后，重復上述過程，直至i==j。此時i便是記錄x所應在的位置。14§10.3.3快速排序(二)分割算法longSortPartition(ina[],longp1,longp2);{//對a[p1]—a[p2]進行分割，返回分割點longi,j;intx;i=p1;j=p2;x=a[i];15§10.3.3快速排序(二)分割算法while(ix&&i

8、x;returni;}16§10.3.3快速排序(二)分割算法初始關鍵字70736923931