冒泡排序-计算机级机试必考内容.ppt

先看一道计算机三级原题 例、已知数据文件IN.DAT中存有200个四位数，并已调用读函数readDat()把这些数存入数组a中，请考生编制一函数jsVal()，其功能是：把千位数字和十位数字重新组成一个新的十位数ab（新十位数的十位数字是原四位数的千位数字，新十位数的个位数字是原四位数的十位数字），以及把个位数字和百位数字组成另一个新的十位数cd（新十位数的十位数字是原四位数的个位数字，新十位数的个位数字是原四位数的百位数字），如果新组成的两个十位数ab-cd=10且ab-cd=20且两个数均是偶数，同时两个新数的十位数字均不为零，则将满足此条件的四位数按从大到小的顺序存入数组b中，并要计算满足上述条件的四位数的个数cnt。 最后main()函数调用写函数writeDat( )把结果cnt以及数组b中符合条件的四位数输出到OUT.DAT文件中。 可以看到上题中红色部分就是要运用今天所学的冒泡排序方法进行排序 下面我们就来认识和学习——冒泡排序 排序 冒泡排序：起泡排序算法是交换排序算法中的一种。交换排序算法的基本思想是：按照某种原则，不断对数列中的一对对逆序（不符合排序要求）的数据进行比较交换，直到数列中不存在任何一对逆序的数据为止。例如要按照升序排列数据，则要通过交换，使任何一个数据前面没有比它大的数据。 三级原题的答案 void jsVal() { int i,j,t,ab,cd; for(i=0;iMAX;i++) { ab=a[i]/1000*10+a[i]/10%10; cd=a[i]%10*10+a[i]/100%10; if(ab - cd = 10 ab - cd = 20 ab%2==0 cd % 2==0 a[i]/10!=0 a[i]/10!=0) b[cnt++]=a[i]; } 希望大家有所收获 谢谢！ ——计算机三级考试机试必考内容 冒泡排序 排序过程: （从小到大） 比较第一个数与第二个数，若为逆序a[0]a[1]，则交换；然后比较第二个数与第三个数；依次类推，直至第n-1个数和第n个数比较为止——第一趟冒泡排序，结果最大的数被安置在最后一个元素位置上； 对前n-1个数进行第二趟冒泡排序，结果使次大的数被安置在第n-1个元素位置； 重复上述过程，共经过n-1趟冒泡排序后，排序结束 38 49 65 76 13 27 30 97 第一趟 38 49 65 13 27 30 76 第二趟 38 49 13 27 30 65 第三趟 38 13 27 30 49 第四趟 13 27 30 38 第五趟 13 27 30 第六趟 13 27 第七趟 49 38 65 97 76 13 27 30 初始关键字 n = 8 38 49 76 97 97 97 97 13 27 30 13 76 76 76 27 30 13 65 65 65 27 30 13 49 49 49 27 30 13 38 38 38 27 30 冒泡排序图示效果 for j = 0 to NUM – i – 1 输入NUM 个数给a[0] 到 a[NUM-1] for i = 1 to NUM – 1 a[j] a[j+1] 真 假 a[j] ? a[j+1] 输出a[0] 到 a[NUM – 1] /*samp7-4a.c*/ #include stdio.h #define NUM 10 void main ( ) { int a[NUM], i, j, t; printf (input %d numbers: \n, NUM); for (i = 0; i NUM; i++) /*输入NUM个整数*/ scanf (%d, a[i]); for (i = 1; i NUM; i++) /*趟数，共NUM-1趟*/ for (j = 0; j NUM - i; j++)/*实现一次冒泡操作*/ if (a[j] a[j+1]) /*交换a[j]和a[j+1]*/ {