資源描述：
《C語言常見排序算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、上章回顧二叉樹的定義樹深度的定義什么樣的二叉樹是滿二叉樹中序遍歷的規(guī)則常見排序算法第六章預(yù)習(xí)檢查課程目標(biāo)本章概述幾種常見排序算法。本章目標(biāo)熟悉常見的查找算法和排序算法難點(diǎn)快速排序算法本章結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法初步常見的排序算法6.1常見的排序算法冒泡排序快速排序直接插入排序希爾排序選擇排序堆排序歸并排序6.1.1冒泡排序算法描述設(shè)待排序記錄序列中的記錄個數(shù)為n一般地，第i趟起泡排序從1到n-i+1依次比較相鄰兩個記錄的關(guān)鍵字，如果發(fā)生逆序，則交換之其結(jié)果是這n-i+1個記錄中，關(guān)鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟
2、。6.1.1冒泡排序算法實例212525*16080123452125*49251649chang=10825*chang=10816chang=125*25214921251608496.1.1冒泡排序算法實例25*012345i=44916chang=108252125*i=54916chang=00825216.1.1冒泡排序算法實例210825492516214925251608214925251608214925251608214925251608214925251608初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序第
3、五趟排序6.1.1冒泡排序算法實現(xiàn)輸入n個數(shù)給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,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]=
4、a[i+1];a[i+1]=t;}printf("Thesortednumbers:");for(i=1;i<11;i++)printf("%d",a[i]);}6.1.2快速排序算法特點(diǎn)：快速排序是通過比較關(guān)鍵碼、交換記錄，以某個記錄為界(該記錄稱為支點(diǎn))，將待排序列分成兩部分一部分所有記錄的關(guān)鍵碼大于等于支點(diǎn)記錄的關(guān)鍵碼另一部分所有記錄的關(guān)鍵碼小于支點(diǎn)記錄的關(guān)鍵碼6.1.2快速排序算法描述：任取待排序記錄序列中的某個記錄(例如取第一個記錄)作為基準(zhǔn)(樞),按照該記錄的關(guān)鍵字大小,將整個記錄序列劃分為左右兩個子序列左側(cè)子序列中
5、所有記錄的關(guān)鍵字都小于或等于基準(zhǔn)記錄的關(guān)鍵字右側(cè)子序列中所有記錄的關(guān)鍵字都大于基準(zhǔn)記錄的關(guān)鍵字基準(zhǔn)記錄則排在這兩個子序列中間(這也是該記錄最終應(yīng)安放的位置)。然后分別對這兩個子序列重復(fù)施行上述方法，直到所有的記錄都排在相應(yīng)位置上為止?；鶞?zhǔn)記錄也稱為樞軸（或支點(diǎn)）記錄。取序列第一個記錄為樞軸記錄，其關(guān)鍵字為Pivotkey指針low指向序列第一個記錄位置指針high指向序列最后一個記錄位置6.1.2快速排序算法實例：2108254925*16始關(guān)鍵字08254925*162108254925*1608254925*1608254925
6、*1608254925*1621pivotkey一次交換二次交換三次交換high-1完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh6.1.2快速排序算法實例：15254925*162108254925*162108完成一趟排序分別進(jìn)行快速排序有序序列08254925*16216.1.2快速排序算法分析：快速排序是一個遞歸過程;利用序列第一個記錄作為基準(zhǔn)，將整個序列劃分為左右兩個子序列。只要是關(guān)鍵字小于基準(zhǔn)記錄關(guān)鍵字的記錄都移到序列左側(cè)；快速排序的趟數(shù)取決于遞歸樹的高度。如果每次劃分對
7、一個記錄定位后,該記錄的左側(cè)子序列與右側(cè)子序列的長度相同,則下一步將是對兩個長度減半的子序列進(jìn)行排序,這是最理想的情況166.1.3直接插入排序算法描述：記錄存放在數(shù)組R[0….n-1]中，排序過程的某一中間時刻，R被劃分成兩個子區(qū)間R[0…i-1]和R[i….n-1]，其中：前一個子區(qū)間是已排好序的有序區(qū)；后一個子區(qū)間則是當(dāng)前未排序的部分?；静僮鲗?dāng)前無序區(qū)的第1個記錄R[i]插入到有序區(qū)R[0….i-1]中適當(dāng)?shù)奈恢?，使R[0…i]變?yōu)樾碌挠行騾^(qū)6.1.3直接插入排序操作細(xì)節(jié)：當(dāng)插入第i(i≥1)個對象時,前面的r[0],r[
8、1],…,r[i-1]已經(jīng)排好序。用r[i]的關(guān)鍵字與r[i-1],r[i-2],…的關(guān)鍵字順序進(jìn)行比較(和順序查找類似)，如果小于，則將r[x]向后移動(插入位置后的記錄向后順移)找到插入位置即將r[i]插入6.1.3直接插入排序?qū)?/p>
