一维数组相关算法

1、一维数组相关算法查找计算最大值/位置/和/平均值倒置排序（2种）插入删除例：编程将一个数组的元素值按逆序重新存放。例如，原顺序为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); /输入数组a printf(please input 数组a ); for(i=0;in;i+) scanf(%d,&ai); printf(“n”); /交换数组 for(i=0;in/2;i+) t=ai; ai=an-1-i; an-1-

2、i=t; /输出交换后的数组 for(i=0;in;i+) printf(%4d,ai);/交换数组for(i=0,j=n-1;ij;i+,j-) t=ai; ai=aj; aj=t；应用举例50个同学参加C程序设计考试，请读取和存储每个同学的成绩值，并计算平均考试成绩，并将所有成绩按照从低到高的顺序排列。1）求平均数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，则交换；然后比较第二个数与第三个数；依次类推，直至第n-1个数和第n个数比较为止第一趟冒泡排序，结果最大的数被放置在最后一个元素位置上对前n-1个数进行第二趟冒泡排序，次大的数被放置在第n-1个元素位置重复上述过程，共经过n-1趟冒泡排序后，排序结束冒泡排序 实现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(请输入数据个数：); 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个数中找出最小的， 将它与第一个数交换第一趟选择排序，结果最小的数被安置在第一个元素位置上2）再通过n-2次比较，从剩余的n-1个数中找出关键字次小的记录，将它与第二个数交换第二趟选择排序3）重复上述过程，共经过n-1趟排序后，排序结束 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; 简单选择排序 算法实现#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); 计数排序 (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); 基数排序 （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)二维数组相关算法转置计算最大值各行各列的最大值/求和杨辉三角形上三角元素之和例：求1010二维数组中的最大值。#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;例：各行各列最大值存放每行最大值存放每列最大值例：矩阵转置#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