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

1、一維數(shù)組相關(guān)算法查找計(jì)算最大值/位置/和/平均值倒置排序（2種）插入刪除例：編程將一個(gè)數(shù)組的元素值按逆序重新存放。例如，原順序?yàn)?，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個(gè)同學(xué)參加C程序設(shè)計(jì)考試，請(qǐng)讀取和存儲(chǔ)每個(gè)同學(xué)的成績(jī)值，并計(jì)算平均考試成績(jī)，并將所有成績(jī)按照從低到高的順序排列。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，則交換；然后比較第二個(gè)數(shù)與第三個(gè)數(shù)；依次類推，直至第n-1個(gè)數(shù)和第n個(gè)數(shù)比較為止第一趟冒泡排序，結(jié)果最大的數(shù)被放置在最后一個(gè)元素位置上對(duì)前n-1個(gè)數(shù)進(jìn)行第二趟冒泡排序，次大的數(shù)被放置在第n-1個(gè)元素位置重復(fù)上述過(guò)程，共經(jīng)過(guò)n-1趟冒泡排序后，排序結(jié)束冒泡排序 實(shí)現(xiàn)n個(gè)元素，n-1 趟冒泡for( i=0；i n-1; i+ ) 第 i 趟冒泡，進(jìn)行 ？次比較第 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(請(qǐng)輸入數(shù)據(jù)個(gè)數(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簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序 算法描述1）首先通過(guò)n-1次比較，從

6、n個(gè)數(shù)中找出最小的， 將它與第一個(gè)數(shù)交換第一趟選擇排序，結(jié)果最小的數(shù)被安置在第一個(gè)元素位置上2）再通過(guò)n-2次比較，從剩余的n-1個(gè)數(shù)中找出關(guān)鍵字次小的記錄，將它與第二個(gè)數(shù)交換第二趟選擇排序3）重復(fù)上述過(guò)程，共經(jīng)過(guò)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; 簡(jiǎn)單選擇排序 算法實(shí)現(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); 計(jì)數(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)置計(jì)算最大值各行各列的最大值/求和楊輝三角形上三角元素之和例：求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