C語言課件(查找和排序)

1、查找與排序查找與排序查找與排序查找與排序查找查找順序查找順序查找折半查找折半查找排序排序直接插入排序直接插入排序簡單選擇排序簡單選擇排序冒泡排序冒泡排序查找與排序查找與排序查找查找查找查找根據(jù)指定的關(guān)鍵字查找數(shù)組中的特定元素。根據(jù)指定的關(guān)鍵字查找數(shù)組中的特定元素。常用方法常用方法順序查找順序查找折半查找折半查找查找與排序查找與排序順序查找順序查找順序查找順序查找適用于小型和適用于小型和（或）（或）沒有排序的數(shù)組。沒有排序的數(shù)組。用關(guān)鍵字與數(shù)組的元素依次進行比較。用關(guān)鍵字與數(shù)組的元素依次進行比較。平均而言，要與數(shù)組的一半元素進行比較平均而言，要與數(shù)組的一半元素進行比較65728379978779

2、57917887查找表查找表關(guān)鍵字關(guān)鍵字查找與排序查找與排序#define N 10void main() int listN+1=0,65,72,83,79,97,87,75,57,91,78; int key,i; printf(Input search key:); scanf(%d,&key); for (i=1;(listi!=key)&(iN) printf(Not found!); else printf(Success! The position is %d.,i);順序查找順序查找順序查找舉例順序查找舉例（cw1009.c）65728379978779579178查找與排序查

3、找與排序折半查找折半查找折半查找折半查找適用于已經(jīng)排好序的數(shù)組。適用于已經(jīng)排好序的數(shù)組。用關(guān)鍵字與數(shù)組的中間元素比較用關(guān)鍵字與數(shù)組的中間元素比較如果相等，則查找結(jié)束如果相等，則查找結(jié)束找到找到如果如果keymiddle，則繼續(xù)在后半部分查找，則繼續(xù)在后半部分查找如果沒有可查找的部分，則查找結(jié)束如果沒有可查找的部分，則查找結(jié)束沒有找到?jīng)]有找到5765727578798387919783lowmidhigh查找與排序查找與排序折半查找折半查找折半查找舉例折半查找舉例（cw1010.c）#include #define N 10void main() int i, low, mid, high, k

4、ey, found; int listN+1=0,57,65,72,75,78,79,83,87,91,97; printf(Sorted list:n); for (i=1;i=N;i+) printf(%-4d, listi); printf(n); printf(Input search key:); scanf(%d, &key);查找與排序查找與排序折半查找折半查找折半查找舉例折半查找舉例 low=1; high=N; found=0; while (lowlistmid) low=mid+1; else if (key=listmid) found=1; else high=mid

5、-1; if (found) printf(Success! The position is %d., mid); else printf(Not found!);考慮不要考慮不要found變量變量查找與排序查找與排序排序排序排序排序按特定的順序來安排數(shù)據(jù)。按特定的順序來安排數(shù)據(jù)。常用方法常用方法直接插入排序直接插入排序簡單選擇排序簡單選擇排序冒泡排序冒泡排序查找與排序查找與排序數(shù)據(jù)插入數(shù)據(jù)插入問題問題把一個數(shù)據(jù)插入到已排好序的有序表中，從而得到一個新把一個數(shù)據(jù)插入到已排好序的有序表中，從而得到一個新的、長度增的、長度增1的有序表。的有序表。57657275787987919783576572

6、757879838791975765727578798791971.找到插入點找到插入點2.騰出位置騰出位置3.插入數(shù)據(jù)插入數(shù)據(jù)查找與排序查找與排序數(shù)據(jù)插入數(shù)據(jù)插入數(shù)據(jù)插入數(shù)據(jù)插入（cw1011.c）把一個數(shù)據(jù)插入到一個有序表中。把一個數(shù)據(jù)插入到一個有序表中。#include #define N 20void main() int i, j, x, len=9; int listN=57,65,72,75,78,79,87,91,97; printf(Sorted list:n); for (i=0;ilisti)&(ii;j-) listj=listj-1; listi=x; len+; p

7、rintf(The new list:n); for (i=0;ilen;i+) printf(%-4d, listi); printf(n);找到插入點找到插入點“騰出位子騰出位子”插入數(shù)據(jù)插入數(shù)據(jù)查找與排序查找與排序直接插入排序直接插入排序直接插入排序直接插入排序(78) 45 25 31 13 66 92 8初始狀態(tài)初始狀態(tài)(45 78) 25 31 13 66 92 8插入第插入第2個數(shù)個數(shù)(25 45 78) 31 13 66 92 8插入第插入第3個數(shù)個數(shù)(8 13 25 31 45 66 78 92)插入最后一個數(shù)插入最后一個數(shù)查找與排序查找與排序直接插入排序直接插入排序直接插入

8、排序直接插入排序（cw1012.c）輸入任意個數(shù)，按從小到大的順序?qū)λ鼈冞M行排序。輸入任意個數(shù)，按從小到大的順序?qū)λ鼈冞M行排序。#include #define N 10void main() int i, j, k, len; int listN, x; printf(Input several integers to construct a listn); printf(“How many?(%d)”, N); scanf(%d, &len); printf(“Please input them:”); for (i=0;ilen;i+) scanf(%d,&listi); printf(

9、OK! The list has been constructed:n); for (i=0;ilen;i+) printf(%-4d,listi);任意個數(shù)：任意個數(shù)：程序運行時確定程序運行時確定查找與排序查找與排序直接插入排序直接插入排序直接插入排序直接插入排序續(xù)續(xù) printf(nTo sort.n); for (i=1;ilistj)&(jj;k-) listk=listk-1; listj=x; printf(Finished! The list has been sorted:n); for (i=0;ilen;i+) printf(%-4d,listi);記住記住listi把把l

10、isti插入有序插入有序數(shù)列：數(shù)列：list0.listi-1（1 1）查找插入點）查找插入點（2 2）移動數(shù)據(jù)）移動數(shù)據(jù)（3 3）插入）插入784525311366928查找與排序查找與排序簡單選擇排序簡單選擇排序簡單選擇排序簡單選擇排序78 45 25 31 13 66 92 8初始狀態(tài)初始狀態(tài)(8) 78 45 31 25 66 92 13找到最小數(shù)找到最小數(shù)(8 13) 78 45 31 66 92 25找到第二小的數(shù)找到第二小的數(shù)(8 13 25 31 45 66 78 92)最大數(shù)被找到最大數(shù)被找到一趟簡單選擇排序的操作：通過一趟簡單選擇排序的操作：通過n-i次數(shù)次數(shù)據(jù)間的比較，從

11、據(jù)間的比較，從n-i+1個記錄中選出最小個記錄中選出最小的數(shù)，并和第的數(shù)，并和第i個數(shù)交換。個數(shù)交換。查找與排序查找與排序簡單選擇排序簡單選擇排序簡單選擇排序簡單選擇排序（cw1013.c）輸入任意個數(shù)，按從小到大的順序?qū)λ鼈冞M行排序。輸入任意個數(shù)，按從小到大的順序?qū)λ鼈冞M行排序。#include #define N 10void main() int i, j, len, min; int listN, tmp; printf(Input several integers to construct a list.n); printf(“How many?(%d)”, N); scanf(%d

12、, &len); printf(“Please input them:”); for (i=0;ilen;i+) scanf(%d,&listi); printf(OK! The list has been constructed:n); for (i=0;ilen;i+) printf(%-4d,listi);查找與排序查找與排序簡單選擇排序簡單選擇排序簡單選擇排序簡單選擇排序續(xù)續(xù) printf(nTo sort.n); for (i=0;ilen-1;i+) min=i; for (j=i+1;jlistj) min=j; tmp=listi; listi=listmin; listmin

13、=tmp; printf(Finished! The list has been sorted:n); for (i=0;ilen;i+) printf(%-4d,listi);查找與排序查找與排序冒泡排序冒泡排序冒泡排序冒泡排序?qū)⑾噜弮蓚€數(shù)比較，把小的調(diào)到前面，大數(shù)放到后面。將相鄰兩個數(shù)比較，把小的調(diào)到前面，大數(shù)放到后面。78453210298092861554578321029809286155453278102980928615545321078298092861554532102978809286155453210297880928615545321029788092861554532

14、10297880892615545321029788086192554532102978808615592321029457886155809210293245861557880928102932455561788092小數(shù)小數(shù)大數(shù)大數(shù)N-1 趟趟查找與排序查找與排序冒泡排序冒泡排序冒泡排序冒泡排序（cw1014.c）輸入任意個數(shù)，按從小到大的順序?qū)λ鼈冞M行排序。輸入任意個數(shù)，按從小到大的順序?qū)λ鼈冞M行排序。#include #define N 10void main() int i, j, len; int listN, tmp; printf(Input several integers

15、to construct a list.n); printf(“How many?(%d)”, N); scanf(%d, &len); printf(“Please input them:”); for (i=0;ilen;i+) scanf(%d,&listi); printf(OK! The list has been constructed:n); for (i=0;ilen;i+) printf(%-4d,listi);查找與排序查找與排序冒泡排序冒泡排序冒泡排序冒泡排序續(xù)續(xù) printf(nTo sort.n); for (i=0;ilen-1;i+) for (j=0;jlistj+1) tmp=listj; listj=listj+1; listj+1=tmp; printf(Finished! The list has been sorted:n); for (i=0;ilen;i+)