北京邮电大学电信工程学院计算机技术中心：《C++大学基础教程》冒泡和选择排序

例64冒泡法排序(从小到大)。 以6个数:3、7、5、6、8、0为例。 j=2 j=3 j=4 j=5 a|0 a 如果a[]>a[|1] a2]6 a[i]与a[+1]交换 单击继续) a3 as 2021/2/24

2021/2/24 1 3 7 5 6 8 0 3 7 5 6 8 0 3 5 7 6 8 0 3 5 6 7 8 0 3 5 6 7 8 0 3 5 6 7 0 8 a[0] a[1] a[2] a[3] a[4] a[5] j=2 3 5 6 7 0 8 3 5 6 7 0 8 3 5 6 7 0 8 3 5 6 7 0 8 3 5 6 0 7 8 j=3 3 5 6 0 7 8 3 5 6 0 7 8 3 5 6 0 7 8 3 5 0 6 7 8 j=1 j=4 3 5 0 6 7 8 3 5 0 6 7 8 3 0 5 6 7 8 j=5 3 0 5 6 7 8 0 3 5 6 7 8 【例6.4】冒泡法排序（从小到大）。 如果 a[ i ] > a[ i+1 ] a[ i ] 与 a[ i+1 ]交换 (单击继续…) 以6个数：3、7、5、6、8、0为例

冒泡法排序(续) j=2 j=3 j=4 j=5 a|0 控制比较的趟数(外层循环) a for(=1;j<N;j++) a2] a3]控制两两比较的次数(内层循环) for (i0; i< N-i; i++) as 2021/2/24

2021/2/24 2 冒泡法排序 （续） 3 5 6 7 0 8 a[0] a[1] a[2] a[3] a[4] a[5] j=2 3 5 6 0 7 8 j=3 3 5 0 6 7 8 j=1 j=4 3 0 5 6 7 8 j=5 0 3 5 6 7 8 j 控制比较的趟数(外层循环): for(j=1;j< ;j++) i 控制两两比较的次数(内层循环): for (i=0; i< ; i++) N N-j

冒泡法排序(续) 从上述过程可以看到:n个数要比较n-1趟,而 在第j趟比较中,要进行n-j次两两比较。 for(i=0; iai+1 F a与a[计1交换 输出a[0-aN-1l 冒泡法排序 2021/2/24

2021/2/24 3 冒泡法排序 （续） 从上述过程可以看到：n个数要比较n-1趟，而 在第j趟比较中，要进行n-j次两两比较。 冒泡法排序 for (i=0; ia[i+1] T F a[i]与a[i+1]交换 输出a[0]~a[N-1]

#definen 6 maino f int a ni 程序运行情况如下: int i,j,t; 3756804 for (i=0; i i+lD itaiiall=ai+l;ai+1=t;3 printf("The sorted numbers: n);

2021/2/24 4 #define N 6 main( ) { int a[N]; int i,j,t; for (i=0; ia[i+1]) { t=a[i];a[i]=a[i+1];a[i+1]=t; } printf("The sorted numbers: \n"); 。。。 } 程序运行情况如下： 3 7 5 6 8 0 0 3 5 6 7 8

例65选择法序排序(从小到大)。6 以6个数:3、7、5、6、8、0为例。 思蹄: 第一趟:将第一个数依次和后面的数比较,如 果后面的某数小于第一个数,则两个数交换,比较 结束后,第一个数则是最小的数。 第二趟:将第二个数依次和后面的数比较,如 果后面的某数小于第二个数,则两个数交换,比较 结束后,第二个数则是次小的数; 2021/2/24

2021/2/24 5 以6个数：3、7、5、6、8、0为例。 思路： 第一趟：将第一个数依次和后面的数比较，如 果后面的某数小于第一个数，则两个数交换，比较 结束后，第一个数则是最小的数。 第二趟：将第二个数依次和后面的数比较，如 果后面的某数小于第二个数，则两个数交换，比较 结束后，第二个数则是次小的数；…… 。 【例6.5】选择法序排序（从小到大）

例65】选择法序排序(续) ajo a[ a[21 a[31 a(41 a[51 第一趟3 6 8 0 0 不交 6 8 0 不交换 7 8 0 不交换 7 6 0 不交换 0 7 5 6 8 交换 20212/24

2021/2/24 6 3 7 5 6 8 0 3 7 5 6 8 0 3 7 5 6 8 0 3 7 5 6 8 0 30 7 5 6 8 03 不交换 不交换 不交换 不交换 a[0] a[1] a[2] a[3] a[4] a[5] 第一趟 j=0 交换 【例6.5】选择法序排序（续）

(例65】选择法序排序(续)。 a 0l a[l a[2 a3 a[4 a[51 0 5 6 3 0 6 8 5 2 0 3 5 8 6 3 0 3 5 8 7 0 3 5 2021/2/24

2021/2/24 7 0 7 5 6 8 3 0 3 7 6 8 5 j=1 0 3 5 7 8 6 j=2 0 3 5 6 8 7 j=3 j=4 0 3 5 6 7 8 j=0 a[0] a[1] a[2] a[3] a[4] a[5] 【例6.5】选择法序排序（续）

#definen 5 8 main( fint an; int 程序运行情况如下 for(i=0; K<N; i++) 96786586404 The sorted numbers scanf(%d", &a i; 4065788696 printf("in"); for(j=0;jN-;j++)/确定基准位置* for(i=j+1; i<N; i++) if (aiai Stall;alj=ai;ai=t;) printf(The sorted numbers: n); 2021/2/24

2021/2/24 8 #define N 5 main( ) { int a[N]; int i,j,t; for (i=0; ia[i]) { t=a[j];a[j]=a[i];a[i]=t; } printf("The sorted numbers: \n"); … } 程序运行情况如下： 96 78 65 86 40 The sorted numbers: 40 65 78 86 96