NOI排序算法課程膠片

排序冒泡排序快速排序直接插入排序希爾排序選擇排序小結(jié)冒泡排序算法描述設(shè)待排序記錄序列中的記錄個數(shù)為n一般地，第i趟起泡排序從1到n-i+1依次比較相鄰兩個記錄的關(guān)鍵字，如果發(fā)生逆序，則交換之其結(jié)果是這n-i+1個記錄中，關(guān)鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟。算法示例1212525*16080123452125*49251649chang=10825*chang=10816chang=125*2521492125160849i=0i=1i=2i=3算法示例225*012345i=44916chang=108252125*i=54916chang=0082521總體演示210825492516214925251608214925251608214925251608214925251608214925251608初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序算法實(shí)現(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]#include<stdio.h>main(){inta[11],i,j,t;printf("Input10numbers:\n");for(i=1;i<11;i++){scanf("%d",&a[i]);}printf("\n");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:\n");for(i=1;i<11;i++){ printf("%d",a[i]);}}冒泡排序快速排序直接插入排序希爾排序選擇排序小結(jié)快速排序快速排序是通過比較關(guān)鍵碼、交換記錄，以某個記錄為界(該記錄稱為支點(diǎn))，將待排序列分成兩部分一部分所有記錄的關(guān)鍵碼大于等于支點(diǎn)記錄的關(guān)鍵碼另一部分所有記錄的關(guān)鍵碼小于支點(diǎn)記錄的關(guān)鍵碼算法描述任取待排序記錄序列中的某個記錄(例如取第一個記錄)作為基準(zhǔn)(樞),按照該記錄的關(guān)鍵字大小,將整個記錄序列劃分為左右兩個子序列左側(cè)子序列中所有記錄的關(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指向序列最后一個記錄位置算法示例12108254925*16始關(guān)鍵字08254925*162108254925*1608254925*1608254925*1608254925*1621pivotkey一次交換二次交換三次交換high-1完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh算法示例212254925*162108254925*162108完成一趟排序分別進(jìn)行快速排序有序序列08254925*1621算法分析快速排序是一個遞歸過程;利用序列第一個記錄作為基準(zhǔn)，將整個序列劃分為左右兩個子序列。只要是關(guān)鍵字小于基準(zhǔn)記錄關(guān)鍵字的記錄都移到序列左側(cè)；快速排序的趟數(shù)取決于遞歸樹的高度。如果每次劃分對一個記錄定位后,該記錄的左側(cè)子序列與右側(cè)子序列的長度相同,則下一步將是對兩個長度減半的子序列進(jìn)行排序,這是最理想的情況13冒泡排序快速排序直接插入排序希爾排序選擇排序小結(jié)直接插入排序算法描述：記錄存放在數(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ū)

直接插入排序操作細(xì)節(jié)：當(dāng)插入第i(i≥1)個對象時,前面的r[0],r[1],…,r[i-1]已經(jīng)排好序。用r[i]的關(guān)鍵字與r[i-1],r[i-2],…的關(guān)鍵字順序進(jìn)行比較(和順序查找類似)，如果小于，則將r[x]向后移動(插入位置后的記錄向后順移)找到插入位置即將r[i]插入直接插入排序?qū)嵱美樱阂阎虻囊唤M記錄的初始排列為：21,25,49,25*,16,0821254925*1608012345算法示例012345temp21254925*160825i=1012345temp21254925*160849i=221254925*1608012345i=325*算法示例012345temp21254925*1608i=416012345temp21254925*1608i=50821254925*1608012345完成算法實(shí)現(xiàn)voidInsertSort(intr[],intn){//假設(shè)關(guān)鍵字為整型，放在向量r[]中

inti,j,temp; for(i=1;i<n;i++){temp=r[i];for(j=i;j>0;j--){//從后向前順序比較，并依次后移if(temp<r[j-1]) r[j]=r[j-1]; else break;}r[j]=temp;}}算法分析關(guān)鍵字比較次數(shù)和記錄移動次數(shù)與記錄關(guān)鍵字的初始排列有關(guān)。最好情況下,排序前記錄已按關(guān)鍵字從小到大有序,每趟只需與前面有序記錄序列的最后一個記錄比較1次,移動2次記錄,總的關(guān)鍵字比較次數(shù)為n-1,記錄移動次數(shù)為2(n-1)在平均情況下的關(guān)鍵字比較次數(shù)和記錄移動次數(shù)約為n2/4。直接插入排序是一種穩(wěn)定的排序方法直接插入排序最大的優(yōu)點(diǎn)是簡單，在記錄數(shù)較少時，是比較好的辦法

冒泡排序快速排序直接插入排序希爾排序選擇排序小結(jié)希爾排序希爾排序又稱縮小增量排序是1959年由D.L.Shell提出來的

算法描述首先取一個整數(shù)gap<n(待排序記錄數(shù))作為間隔,將全部記錄分為gap個子序列,所有距離為gap的記錄放在同一個子序列中在每一個子序列中分別施行直接插入排序。然后縮小間隔gap,例如取gap=gap/2重復(fù)上述的子序列劃分和排序工作，直到最后取gap=1,將所有記錄放在同一個序列中排序?yàn)橹?。算法示例已知待排序的一組記錄的初始排列為：21,25,49,25*,16,080123452108254925*16算法示例t30123452108254925*160123452108254925*16t22108254925*162108254925*16t12108254925*162108254925*16算法分析開始時gap的值較大,子序列中的記錄較少,排序速度較快隨著排序進(jìn)展,gap值逐漸變小,子序列中記錄個數(shù)逐漸變多,由于前面大多數(shù)記錄已基本有序,所以排序速度仍然很快Gap的取法有多種。shell提出取gap=n/2，gap=gap/2，直到gap=1。冒泡排序快速排序直接插入排序希爾排序選擇排序小結(jié)排序過程首先通過n-1次比較，從n個數(shù)中找出最小的，將它與第一個數(shù)交換—第一趟選擇排序，結(jié)果最小的數(shù)被安置在第一個元素位置上再通過n-2次比較，從剩余的n-1個數(shù)中找出關(guān)鍵字次小的記錄，將它與第二個數(shù)交換—第二趟選擇排序重復(fù)上述過程，共經(jīng)過n-1趟排序后，排序結(jié)束排序示例初始：[49386597761327]kji=11349一趟：13[386597764927]i=22738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]kkkkjjjjjjjjjj算法示例212525*16080123452125*i=1492516251608490825*4921i=2i=3081625*2521初始49算法示例25*01234525*2516084925*492108162521最小者

25*無交換最小者

25無交換25211608各趟排序后的結(jié)果算法示例01234549160825*49210825*2521i=2時選擇排序的過程ikj49250825*1621ikj492525*25162516<25ikj算法示例49250825*1621012345ikj2116k

指示當(dāng)前序列中最小者算法實(shí)現(xiàn)輸入n個數(shù)給a[1]到a[n]fori=1ton-1forj=i+1tona[j]<a[k]真假k=j輸出a[1]到a[n]k=ia[i]a[k]i!=k真假#include<stdio.h>main(){

inta[11],i,j,k,x;printf("Input10numbers:\n");

for(i=1;i<11;i++){scanf("%d",&a[i]);}printf("\n");

for(i=1;i<10;i++)

{

k=i;

for(j=i+1;j<=10;j++){

if(a[j]<a[k])k=j;}

if(i!=k)

{

x=a[i];a[i]=a[k];a[k]=x;

}

}printf("Thesortednumbers:\n");

for(i=1;i<11;i++){ printf("%d",a[i]);}}冒泡排序快速排序直接插入排序希爾排序選擇排序小結(jié)36基本概念排序（Sorting）：簡單地說，排序就是把一組記錄按照某個（或某幾個）字段的值以遞增（由小到大）或遞減（由大到?。┑拇涡蛑匦屡帕械倪^程。（如按年齡從小到大排序）學(xué)號姓名年齡性別2004001張佳18男2004002王鵬19男2004003劉寧17女2004004李娟18女2004005陳濤19男2004006李小燕