c語(yǔ)言排序與查找

1、排序與查找1. 選擇排序算法：N元數(shù)組a0aN-1由小到大排序：第0步:找到a0aN-1中的最小值元素與a0交換;第1步:找到a1aN-1中的最小值元素與a1交換；第2步:找到a2aN-1中的最小值元素與a2交換；.第i步:找到aiaN-1中的最小值元素與ai交換；.第N-2步:找到aN-2aN-1中的最小值元素與 aN-2交換。算法停止。思考：由大到小排序算法如何改動(dòng)？#include "stdio.h"#define N 10void SelSort(int aN) /* 選擇排序函數(shù) */int i,j,minj,t;for (i = 0;i < N-1;i+)

2、 for (j = i + 1;j < N;j+)if(aj < ai) t = ai;ai = aminj;aminj = t;這樣中間有些交換是沒有必要的，設(shè)定一個(gè)minj變量記錄當(dāng)前一趟最小值的下標(biāo)?？梢詼p少變量交換的次數(shù)。改進(jìn)如下：void SelSort(int aN) /* 改進(jìn)選擇排序函數(shù) */int i,j,minj,t;for (i = 0;i < N-1;i+) minj = i;for (j = i + 1;j < N;j+)if(aj < aminj)minj = j;if(minj != i) t = ai;ai = aminj;amin

3、j = t;void main()int aN,i;for(i = 0;i < N;i+)scanf("%d”,a + i);SelSort(a);for (i = 0;i < N;i+)printf("%6d”,ai);2. 插入排序引例：寫一個(gè)函數(shù)，將一個(gè)整型數(shù) x插入到由小到大排列的整型數(shù)組a0aN-1中，使得插入元素后的數(shù)組a0aN保持升序。void insert(int aN+1,int x) int i = N - 1;while (i >= 0 && ai > x) (ai+1 = ai;i-;ai+1 = x;算法要點(diǎn)

4、：將升序數(shù)組中大于x的所有元素向后挪動(dòng)一個(gè)下標(biāo)位置；循環(huán)退出時(shí)，下標(biāo) i + 1位置為一空位置，正好是正確插入元素x的位置.插入排序算法：N元數(shù)組a0aN-1由小到大排序：第1步:將a1插入a0a1中，使得a0a1升序；第2步:將a2插入a0a2中，使得a0a2升序；第3步:將a3插入a0a3中，使得a0a3升序；.第i步:將ai插入a0ai中，使得a0ai升序；.第 N-1 步:將 aN-1插入 a0aN-1中，使得 a0aN-1升序；算法停止。思考：由大到小排序算法如何改動(dòng)？#include "stdio.h"#define N 10void InsSort(int a

5、N) /*N元數(shù)組插入排序 */int i,j,x;for(i = 1;i < N;i+)x = ai;j = i - 1;while(j >= 0 && aj > x) aj+1 = aj;j-;aj+1 = x;void main() (int aN,i;for (i = 0;i < N;i+)scanf("%d”,&ai);InsSort(a);for (i = 0;i < N;i+)printf("%6d”,ai);3. 冒泡排序相鄰元素比較大小發(fā)生交換使最大值(最小值)”浮出”到數(shù)組盡頭:若a0>a1,則

6、a0?a1;使a1為a0,a1的大者)(2)若 a1>a2,則 a1?a2;使 a2 為 a1,a2 的大者)(i)若 ai-1>ai,則 ai-1?ai 交換(使 ai 為 ai-1,ai 的大者)按照這種方法運(yùn)算下去，數(shù)組中的最大元一定可以移動(dòng)到最后一個(gè)下標(biāo)位置 冒泡排序算法：N元數(shù)組a0aN-1由小到大排序：第1步:找到a0aN-1中的最大元浮動(dòng)到 aN-1;第2步:找到a0aN-2中的最大元浮動(dòng)到 aN-2;第3步:找到a0aN-3中的最大元浮動(dòng)到 aN-3;.第i步:找到a0aN-i中的最大元浮動(dòng)到 aN-i;.第N-1步:找到a0a1中的最大元浮動(dòng)到 a1。算法停止.思

7、考：由大到小排序算法如何改動(dòng)？#include "stdio.h"#define N 10void main() (int aN,i,j,t;printf("Input %d int numbers:n",N);for (i = 0;i < N;i+)scanf("%d",a+i);for (i = 1;i < N;i+)for (j = 0;j < N-i;j+)if (aj > aj+1) (t = aj;aj = aj+1;aj+1 = t;printf("Reslut:");for(

8、i = 0;i < N;i+)printf("%6d”,ai);printf("n");冒泡排序的改進(jìn)：顯然，當(dāng)數(shù)組已經(jīng)排好序時(shí)，不會(huì)發(fā)生元素的浮動(dòng)(即元素的交換值)，因此，可設(shè)一個(gè)標(biāo)變量，當(dāng)內(nèi)循環(huán)未發(fā)生前后兩元素交換值時(shí)，就跳出外循環(huán)。void BubSort(int aN) (int i,j,t;int sorted;for (i = 1;i < N;i+) (sorted = 1;for(j = 0;j < N-i;j+)if (aj > aj+1) (t = aj;aj = aj+1;aj+1 = t;sorted = 0;if(s

9、orted) break;4. 索引排序目的：待排序數(shù)組保持不變，而元素的順序通過下標(biāo)數(shù)組中的下標(biāo)順序來體現(xiàn)。貓組下標(biāo)D 1 2 3 45 6 7待排序數(shù)組ft的元素9 7 -1 12 15 S-32 -7下標(biāo)數(shù)組元素初值G I 2 3 4$ 6 7排序后的下標(biāo)海元素值6 7 % 1 3 0 罵耳！ a6<A7<a2'- al#include "stdio.h"#define N 10void InxBubSort(int aN,int pN) (/*pN為下標(biāo)數(shù)組，也稱為索引數(shù)組*/ int i,j,k;for (i = 0;i < N;i+)p

10、i = i;for (i = 1;i < N;i+)for (j = 0;j < N-i;j+)if (apj > apj+1) (k = pj;pj = pj+1;pj+1 = k;)void main() (int aN,pN,i;printf("Input %d int number:n",N);for (i = 0;i < N;i+)scanf("%d”,&ai);InxBubSort(a,p);printf("Result:n");for(i = 0;i < N;i+)printf("%

11、6d”,api);printf("n");)對(duì)分查找(也稱為折半查找或拆半查找)算法：設(shè)a0aN-1已升序，待查找元素為x令起點(diǎn)下標(biāo) h=0;終點(diǎn)下標(biāo)r=N-1;中點(diǎn)下標(biāo)m=(h+r)/2;當(dāng)h<=r時(shí)執(zhí)行以下步驟：若x=am則表明查找成功，am為所找元素；x<am,顯然 x 在 aham-1之間，則h 不變;r=m-1;m=(h+r)/2;轉(zhuǎn)x>am,顯然 x 在 am+1ar之間，則r 不變;h=m+1;m=(h+r)/2;轉(zhuǎn) 若h>r,則表明查找失敗.該算法僅適用于在已排序的數(shù)組中快速查找所需要的元素，具有效率高的突出優(yōu)點(diǎn)?？梢宰C明，當(dāng)數(shù)組長(zhǎng)度為n個(gè)元素時(shí)，該算法的平均比較次數(shù)不會(huì)超過log2n+1。/*升序數(shù)組aN中查找x,找到返回有效下標(biāo) 0N-1,查找失敗返回-1*/int Locate(int aN,int x) (int h,r,m;h = 0;r = N-1;m = (h + r) / 2;while (h <= r && x != am)if (x &l