冒泡法和選擇法ppt課件

1、由以上可推知：由以上可推知：6 個(gè)數(shù)要比較個(gè)數(shù)要比較5趟趟 第一趟中要進(jìn)展兩兩比較第一趟中要進(jìn)展兩兩比較5次次 第二趟中比較第二趟中比較 4次次 假設(shè)有假設(shè)有n個(gè)數(shù)，那么要進(jìn)展個(gè)數(shù)，那么要進(jìn)展n-1趟比較趟比較 第第j趟比較中要進(jìn)展趟比較中要進(jìn)展n-j次兩兩比較。次兩兩比較。例例2 用冒泡法對(duì)用冒泡法對(duì)10個(gè)數(shù)排序由小到大個(gè)數(shù)排序由小到大方法：將兩個(gè)相鄰數(shù)比較，小的調(diào)到前頭。方法：將兩個(gè)相鄰數(shù)比較，小的調(diào)到前頭。9 8 8 8 8 88 9 5 5 5 5 8 5 5 5 55 5 9 4 4 4 5 8 4 4 44 4 4 9 2 2 4 4 8 2 22 2 2 2 9 0 2 2 2

2、8 00 0 0 0 0 9 0 0 0 0 8排序過(guò)程：排序過(guò)程：1 1比較第一個(gè)數(shù)與第二個(gè)數(shù)，假設(shè)為逆序，比較第一個(gè)數(shù)與第二個(gè)數(shù)，假設(shè)為逆序，a1a2a1a2，那么交換；然后比較第二個(gè)數(shù)與第三個(gè)數(shù)；依次類推，那么交換；然后比較第二個(gè)數(shù)與第三個(gè)數(shù)；依次類推，直至第直至第n-1n-1個(gè)數(shù)和第個(gè)數(shù)和第n n個(gè)數(shù)比較為止個(gè)數(shù)比較為止第一趟冒泡排序，第一趟冒泡排序，結(jié)果最大的數(shù)被安頓在最后一個(gè)元素位置上結(jié)果最大的數(shù)被安頓在最后一個(gè)元素位置上2 2對(duì)前對(duì)前n-1n-1個(gè)數(shù)進(jìn)展第二趟冒泡排序，結(jié)果使次大的數(shù)個(gè)數(shù)進(jìn)展第二趟冒泡排序，結(jié)果使次大的數(shù)被安頓在第被安頓在第n-1n-1個(gè)元素位置個(gè)元素位置3 3反

3、復(fù)上述過(guò)程，共經(jīng)過(guò)反復(fù)上述過(guò)程，共經(jīng)過(guò)n-1n-1趟冒泡排序后，排序終了趟冒泡排序后，排序終了輸入輸入n 個(gè)數(shù)給個(gè)數(shù)給a1 到到 anfor j=1 to n-1for i=1 to n-jaiai+1真真假假aiai+1輸出輸出a1 到到 an文件包含文件包含變量定義變量定義主函數(shù)主函數(shù)輸入數(shù)據(jù)輸入數(shù)據(jù)排序排序輸出數(shù)據(jù)輸出數(shù)據(jù)#include int a10,i,j,t;printf(Input 10 numbers:n);for(i=0;i10;i+) scanf(%d,&ai);for( ) for( ) if( ) printf(n);printf(The sorted num

4、bers:n);for(i=0;i10;i+) printf(%d ,ai);main() j=0; j9 ; j+i=0 ; iai+1例例 用簡(jiǎn)單項(xiàng)選擇擇法對(duì)用簡(jiǎn)單項(xiàng)選擇擇法對(duì)1010個(gè)數(shù)排序個(gè)數(shù)排序排序過(guò)程：排序過(guò)程：1 1首先經(jīng)過(guò)首先經(jīng)過(guò)n-1n-1次比較，從次比較，從n n個(gè)數(shù)中找出最小的，個(gè)數(shù)中找出最小的， 將它將它與第一個(gè)數(shù)交換與第一個(gè)數(shù)交換第一趟選擇排序，結(jié)果最小的數(shù)被安頓第一趟選擇排序，結(jié)果最小的數(shù)被安頓在第一個(gè)元素位置上在第一個(gè)元素位置上2 2再經(jīng)過(guò)再經(jīng)過(guò)n-2n-2次比較，從剩余的次比較，從剩余的n-1n-1個(gè)數(shù)中找出關(guān)鍵字個(gè)數(shù)中找出關(guān)鍵字次小的記錄，將它與第二個(gè)數(shù)交換次

5、小的記錄，將它與第二個(gè)數(shù)交換第二趟選擇排序第二趟選擇排序3 3反復(fù)上述過(guò)程，共經(jīng)過(guò)反復(fù)上述過(guò)程，共經(jīng)過(guò)n-1n-1趟排序后，排序終了趟排序后，排序終了例例初始：初始： 49 38 65 97 76 13 27 ji=11349一趟：一趟： 13 38 65 97 76 49 27 i=22738二趟：二趟： 13 27 65 97 76 49 38 三趟：三趟： 13 27 38 97 76 49 65 四趟：四趟： 13 27 38 49 76 97 65 五趟：五趟： 13 27 38 49 65 97 76 六趟：六趟： 13 27 38 49 65 76 97 kkkkjjjjjjjjjj一共比較一共比較n-1趟趟k輸入輸入n 個(gè)數(shù)給個(gè)數(shù)給a1 到到 anfor i=1 to n-1for j=i+1 to najak假假真真k=j輸出輸出a1 到到 ank=ii != kaiak真真假假文件包含文件包含變量定義變量定義輸入數(shù)據(jù)輸入數(shù)據(jù)輸出數(shù)據(jù)輸出數(shù)據(jù)#include int a10,i,j,k,t;printf(Input 10 numbers:n);for(i=0;i10;i+) scanf(%d,&ai);printf(n);printf(The sorted numbers:n);for(i=0;i10;i+) printf(%d ,ai);m