一維數(shù)組相關(guān)算法

1、一維數(shù)組相關(guān)算法查找計算最大值/位置/和/平均值倒置排序（2種）插入刪除例：編程將一個數(shù)組的元素值按逆序重新存放。例如，原順序為1，5，8， 4，9，逆序后為9，4，8，5，1#include#define MAX 100void main() int aMAX,n,i,t; printf(please input n ); scanf(%d,&n); /輸入數(shù)組a printf(please input 數(shù)組a ); for(i=0;in;i+) scanf(%d,&ai); printf(“n”); /交換數(shù)組 for(i=0;in/2;i+) t=ai; ai=an-1-i; an-1-

2、i=t; /輸出交換后的數(shù)組 for(i=0;in;i+) printf(%4d,ai);/交換數(shù)組for(i=0,j=n-1;ij;i+,j-) t=ai; ai=aj; aj=t；應(yīng)用舉例50個同學(xué)參加C程序設(shè)計考試，請讀取和存儲每個同學(xué)的成績值，并計算平均考試成績，并將所有成績按照從低到高的順序排列。1）求平均數(shù)2）排序#include #define STU_NUM 50void main() float markSTU_NUM, ave; int i; for(i=0; iSTU_NUM;i+) printf(Input %d student mark: “, i); scanf(%

3、f, &marki ); ave=0; for(i = 0; i a1，則交換；然后比較第二個數(shù)與第三個數(shù)；依次類推，直至第n-1個數(shù)和第n個數(shù)比較為止第一趟冒泡排序，結(jié)果最大的數(shù)被放置在最后一個元素位置上對前n-1個數(shù)進行第二趟冒泡排序，次大的數(shù)被放置在第n-1個元素位置重復(fù)上述過程，共經(jīng)過n-1趟冒泡排序后，排序結(jié)束冒泡排序 實現(xiàn)n個元素，n-1 趟冒泡for( i=0；i n-1; i+ ) 第 i 趟冒泡，進行 ？次比較第 0 趟，n-1 次比較第 1 趟，n-2 次比較第 i 趟， n-i-1 次比較for( j=0; j aj+1 ) change; Bubble - Source

4、Code int aSIZE, i, j, t; for( i=0; in-1; i+) for( j = 0; jaj+1 ) t = aj; aj = aj+1; aj+1 = t; #include #define SIZE 100void main() int aSIZE,i,j,t,n; printf(請輸入數(shù)據(jù)個數(shù)：); scanf(%d,&n); printf(Input n numbers:n); for(i=0;in;i+) scanf(%d,&ai); printf(n); for(i=0;in-1;i+) for(j=0;jaj+1) t=aj; aj=aj+1; aj+

5、1=t; printf(The sorted numbers:n); for(i=0;in;i+)printf(%d ,ai);初始： 49 38 65 97 76 13 27 kji=01349一趟： 13 38 65 97 76 49 27 i=12738二趟： 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簡單選擇排序簡單選擇排序 算法描述1）首先通過n-1次比較，從

6、n個數(shù)中找出最小的， 將它與第一個數(shù)交換第一趟選擇排序，結(jié)果最小的數(shù)被安置在第一個元素位置上2）再通過n-2次比較，從剩余的n-1個數(shù)中找出關(guān)鍵字次小的記錄，將它與第二個數(shù)交換第二趟選擇排序3）重復(fù)上述過程，共經(jīng)過n-1趟排序后，排序結(jié)束 int aSIZE, i, j, k, t; for(i=0; in-1; i+) k=i; for( j = i+1; jn; j+) if( aj ak ) k = j; if( i! = k ) t = ai; ai = ak; ak = t; 簡單選擇排序 算法實現(xiàn)#include#define SIZE 100main() int i,j,l,n,

7、t,aSIZE; printf(Input n: ); scanf(%d,&n); for(i=0;i=n-1;i+) printf(Input data: ); scanf(%d,&ai); for(i=0; in-1; i+) l=i; for( j=i+1; j n; j+) if(ajal)l=j; if( i!=l ) t=ai; ai=al; al=t; for(i=0;i=n-1;i+) printf(%d,ai); printf(n);冒泡排序（bubble sort） O(n2) 選擇排序 （selection sort） O(n2) 雞尾酒排序 (Cocktail sort

8、) O(n2) 插入排序 （insertion sort） O(n2) 桶排序 （bucket sort） O(n); 計數(shù)排序 (counting sort) O(n+k); 歸并排序 （merge sort） O(n log n); 原地歸并排序 O(n2) 二叉樹排序 （Binary tree sort） O(n log n); 鴿巢排序 (Pigeonhole sort) O(n+k); 基數(shù)排序 （radix sort） O(nk); Gnome sort O(n2) Library sort O(n log n) 希爾排序 （shell sort） O(n log n) Comb

9、sort O(n log n) 堆排序 （heapsort） O(n log n) Smoothsort O(n log n) 快速排序 （quicksort） O(n log n) Introsort O(n log n) Patience sorting O(n log n + k)二維數(shù)組相關(guān)算法轉(zhuǎn)置計算最大值各行各列的最大值/求和楊輝三角形上三角元素之和例：求1010二維數(shù)組中的最大值。#include #define MAX 10void main() int aMAXMAX,n,i,j,l,k; printf(Input a%1d%1d:n, MAX, MAX); for( i=0

10、; iMAX; i+) for( j=0; jMAX; j+) scanf(%d, &aij); l=0; k=0; for( i=0; iMAX; i+) for( j=0; j alk ) l=i; k=j; printf(“%d,%d,%dn, l, k, alk);int a34,row3,column4;int i, j, k;k=0; for (i=0; i3; i+) k = 0; for(j=1; j4; j+) if (aik aij ) k = j; rowi = aik; for (j=0; i4; i+) k = 0; for(i=1; i3; i+) if (akj

11、aij ) k = i; columnj = akj;例：各行各列最大值存放每行最大值存放每列最大值例：矩陣轉(zhuǎn)置#includevoid main() int a33, b33, i, j; for ( i=0; i3; i+) for( j=0; j3; j+) printf(input data ); scanf(%d,&aij); for (i=0;i3;i+) for(j=0;j3;j+) bij=aji; for (i=0;i3;i+) for(j=0;j3;j+) printf(%3d,bij); printf(n); 1 2 34 5 67 8 91 4 72 5 83 6 9#

12、includemain() int a1111,i,j; for(i=1; i=10; i+) ai1=1; aii=1; for(j=2; ji; j+) aij= ai-1j-1+ai-1j; for(i=1; i=10; i+) for(j=1;j=i;j+) printf(“%4d”,aij); printf(n); 例：打印楊輝三角/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htmhttp:/OcwWeb/web/home/home/index.htmVideo lectures Audio lectures Subtitles/Transcript Selected lecture notes Assignments and solutions Exams and Solutio