資源描述：
《各種排序算法大全》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、6.1常見的排序算法冒泡排序快速排序直接插入排序希爾排序選擇排序堆排序歸并排序6.1.1冒泡排序算法描述設待排序記錄序列中的記錄個數為n一般地，第i趟起泡排序從1到n-i+1依次比較相鄰兩個記錄的關鍵字，如果發(fā)生逆序，則交換之其結果是這n-i+1個記錄中，關鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟。6.1.1冒泡排序算法實例212525*16080123452125*49251649chang=10825*chang=10816chang=125*25214921251608496.1.1冒泡排序算法實例25*012345i=4
2、4916chang=108252125*i=54916chang=00825216.1.1冒泡排序算法實例210825492516214925251608214925251608214925251608214925251608214925251608初始關鍵字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序6.1.1冒泡排序算法實現輸入n個數給a[1]到a[n]forj=1ton-1fori=1ton-ja[i]>a[i+1]真假a[i]?a[i+1]輸出a[1]到a[n]#includemain(){inta[11],i,j
3、,t;printf("Input10numbers:");for(i=1;i<11;i++)scanf("%d",&a[i]);printf("");for(j=1;j<=9;j++)for(i=1;i<=10-j;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}printf("Thesortednumbers:");for(i=1;i<11;i++)printf("%d",a[i]);}6.1.2快速排序算法特點：快速排序是通過比較關鍵碼、交換記錄，以某個記錄為界(該記錄稱為支點)，
4、將待排序列分成兩部分一部分所有記錄的關鍵碼大于等于支點記錄的關鍵碼另一部分所有記錄的關鍵碼小于支點記錄的關鍵碼6.1.2快速排序算法描述：任取待排序記錄序列中的某個記錄(例如取第一個記錄)作為基準(樞),按照該記錄的關鍵字大小,將整個記錄序列劃分為左右兩個子序列左側子序列中所有記錄的關鍵字都小于或等于基準記錄的關鍵字右側子序列中所有記錄的關鍵字都大于基準記錄的關鍵字基準記錄則排在這兩個子序列中間(這也是該記錄最終應安放的位置)。然后分別對這兩個子序列重復施行上述方法，直到所有的記錄都排在相應位置上為止?；鶞视涗浺卜Q為樞軸（或支點）記錄。取序列第一
5、個記錄為樞軸記錄，其關鍵字為Pivotkey指針low指向序列第一個記錄位置指針high指向序列最后一個記錄位置6.1.2快速排序算法實例：2108254925*16始關鍵字08254925*162108254925*1608254925*1608254925*1608254925*1621pivotkey一次交換二次交換三次交換high-1完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh6.1.2快速排序算法實例：10254925*162108254925*162108完成一趟排序分別進行快速排序
6、有序序列08254925*16216.1.2快速排序算法分析：快速排序是一個遞歸過程;利用序列第一個記錄作為基準，將整個序列劃分為左右兩個子序列。只要是關鍵字小于基準記錄關鍵字的記錄都移到序列左側；快速排序的趟數取決于遞歸樹的高度。如果每次劃分對一個記錄定位后,該記錄的左側子序列與右側子序列的長度相同,則下一步將是對兩個長度減半的子序列進行排序,這是最理想的情況116.1.3直接插入排序算法描述：記錄存放在數組R[0….n-1]中，排序過程的某一中間時刻，R被劃分成兩個子區(qū)間R[0…i-1]和R[i….n-1]，其中：前一個子區(qū)間是已排好序的有序
7、區(qū)；后一個子區(qū)間則是當前未排序的部分?；静僮鲗斍盁o序區(qū)的第1個記錄R[i]插入到有序區(qū)R[0….i-1]中適當的位置，使R[0…i]變?yōu)樾碌挠行騾^(qū)6.1.3直接插入排序操作細節(jié)：當插入第i(i≥1)個對象時,前面的r[0],r[1],…,r[i-1]已經排好序。用r[i]的關鍵字與r[i-1],r[i-2],…的關鍵字順序進行比較(和順序查找類似)，如果小于，則將r[x]向后移動(插入位置后的記錄向后順移)找到插入位置即將r[i]插入6.1.3直接插入排序實用例子：已知待序的一組記錄的初始排列為：21,25,49,25*,16,0821254
8、925*16080123456.1.3直接插入排序實用例子：012345temp21254925*160825i=1012345temp
