2009-7-29
1
3
7
5
6
8
0
5
76
7
0
8
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
j=2
3
5
6
7
0
8
0
7
j=3
3
5
6
0
7
8
0
6
j=4j=1
3
5
0
6
7
8
0
5
j=5
3
0
5
6
7
8
0
3
【 例 6.4】 冒泡法排序（从小到大）。
如果 a[ i ] > a[ i+1 ]
a[ i ] 与 a[ i+1 ]交换
(单击继续 … )
以 6个数,3,7,5,6,8,0为例。
2009-7-29
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=4j=1
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
2009-7-29
3冒泡法排序 （续）
从上述过程可以看到,n个数要比较 n-1趟，而在第 j趟比较中，要进行 n-j次两两比较。
冒泡法排序
for (i=0; i<N; i++)
输入 a[i]
for (j=1;j<N; j++)
for (i=0; i<N-j; i++)
a[i]>a[i+1]
T F
a[i]与 a[i+1]交换输出 a[0]~a[N-1]
2009-7-29
4
#define N 6
main( )
{ int a[N];
int i,j,t;
for (i=0; i<N; i++)
scanf("%d",&a[i]);
for (j=1; j<=N-1; j++) /*控制比较的趟数 */
for (i=0; i<N-j; i++) /*两两比较的次数 */
if (a[i]>a[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
2009-7-29
5
以 6个数,3,7,5,6,8,0为例。
思路：
第一趟：将 第一个数 依次和后面的数比较，如果后面的某数小于 第一个数,则两个数交换，比较结束后,第一个数 则是 最小 的数。
第二趟,将 第二个数 依次和后面的数比较，如果后面的某数小于 第二个数,则两个数交换，比较结束后,第二个数 则是 次小 的数； …… 。
【 例 6.5】 选择法序排序（从小到大）。
2009-7-29
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
3 7 5 6 8 00 3
不交换不交换不交换不交换
a[1] a[2] a[3] a[4] a[5]a[0]
第一趟
j=0
交换
【 例 6.5】 选择法序排序（续）。
2009-7-29
7
0 7 5 6 8 3
0 3 7 6 8 5j=1
0 3 5 7 8 6j=2
0 3 5 6 8 7j=3
0 3 5 6 7 8j=4
j=0
a[1] a[2] a[3] a[4] a[5]a[0]
【 例 6.5】 选择法序排序（续）。
2009-7-29
8#define N 5
main( )
{ int a[N];
int i,j,t;
for (i=0; i<N; i++)
scanf("%d",&a[i]);
printf("\n");
for (j=0; j<N-1; j++) /*确定基准位置 */
for(i=j+1; i<N; i++)
if (a[j]>a[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