004-的数组.ppt

* 7.6 编程实例——冒泡排序 43 7 -3 23 0 1 43 23 7 -3 1 0 43 23 7 1 -3 0 43 23 7 1 0 -3 43 23 7 1 0 -3 i=0 a[5] a[4] a[3] a[2] a[1] a[0] i=1 i=2 i=3 i=4 冒泡排序程序：当 n=6 时，进行程序抽象 4 i 控制外层循环: for (i=0;i ;i++) n-1 j 控制内层循环: for (j= ;j ;j++) n-1 n-1-i 0 n-i-1 * #define N 6 int main ( ) { int i, j, t, a[N]; for (i=0; iN; i++) /* 输入N个整数 */ { printf(Enter No.%2d:, i+1); scanf (%d, a[i]); } for (i=0; iN-1; i++) /* 进行N-1趟比较 */ for (j=0; jN-i-1; j++)/*比较数组中相邻两个元素*/ if ( a[j] a[j+1] ) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } /* 交换 */ for (i=0; iN; i++) /* 输出排序结果 */ printf(%d , a[i]); } * 7.6 编程实例——冒泡排序 冒泡排序的缺陷：在比较交换的过程中大的数不能一次到位，效率低。 7 -3 43 0 1 23 a[5] a[4] a[3] a[2] a[1] a[0] 7 -3 43 0 23 1 7 -3 43 23 0 1 7 -3 43 23 0 1 7 43 -3 23 0 1 43 7 -3 23 0 1 选择排序法的基本思想： 以冒泡排序法为基础，在两两比较后并不马上进行交换，而是在找到最小的数之后，记住最小数的位置(在数组中的下标)，待一轮比较完毕后，再将最小的数一次交换到位。 * 7.6 编程实例——选择排序 问题：将 23、1、0、43、-3 和 7 从小到大排列。 选择排序法 若有N个数，则需要进行N-1轮排序处理。 第1轮排序从1～N个数中找出最小的数，然后将它与第1个数交换。第1个数则是最小的数。 第2轮排序从2～N个数中找出最小的数，然后将它与第2个数交换。第2个数则是次小的数。 经过 N-1 轮处理，完成全部N个数排序。 编程时使用二重循环。外面的大循环控制进行N-1轮排序，小循环找出第 i 轮的最小值。 * 7.6 编程实例——选择排序 23 1 0 43 -3 7 1 2 3 4 5 j=0 -3 1 0 43 23 7 i=0 0 初始 p = 1 p=j 则 p= a[p] a[j] j=1 2 p=j 则 p= a[p] a[j] j=2 a[p] ≯ a[j] j=3 4 p=j 则 p= a[p] a[j] j=4 a[p] ≯ a[j] j=5 p!=i 进行交换：t=a[i]; a[i]=a[p]; a[p]=t; p：记录当前排序过程中最小值的下标 找第 1个小数 * 7.6 编程实例——选择排序 -3 1 0 43 23 7 1 2 3 4 5 j=0 -3 0 1 43 23 7 i=1 1 初始 p = 2 p=j 则 p= a[p] a[j] j=2 a[p] ≯ a[j] j=3 a[p] ≯ a[j] j=4 a[p] ≯ a[j] j=5 p!=i 进行交换：t=a[i]; a[i]=a[p]; a[p]=t; p：记录当前排序过程中最小值的下标 找第 2个小数 * #define N 6 int main ( ) { int i,j,t,p, a[N]; for (i=0; iN; i++) { printf(Enter No.%2d: