文档介绍：三种基本排序算法
主要的排序方法:
1、选择排序
2、冒泡排序
3、插入排序
例1、选择排序
从键盘上输入10个整数,用选择法将其按由小到大的顺序排列并输出
基本思想:
(1)第1个位置的数和从第2个位置的数到第10个位置的数比较,小在前,大在后,否则,交换。
(2)第2个位置的数和从第3个位置的数到第10个位置的数比较,小在前,大在后,否则,交换。
…
(8)第8个位置的数和从第9个位置的数到第10个位置的数比较,小在前,大在后,否则,交换。
(9) 第9个位置的数和第10个位置的数比较,小在前,大在后,否则,交换。
输入数据:
5 13 3 9 32 22 8 1 23 21
排序过程如下:
5 13 3 9 32 22 8 1 23 21
① 1 13 5(3) 9 32 22 8 3(1) 23 21
② 1 3 13 9 32 22 8 5 23 21
③ 1 3 5 9 32 22 8 13 23 21
④ 1 3 5 8 32 22 9 13 23 21
⑤ 1 3 5 8 9 22 32 13 23 21
⑥ 1 3 5 8 9 13 32 22 23 21
⑦ 1 3 5 8 9 13 21 22 23 32
⑧ 1 3 5 8 9 13 21 22 23 32
⑨ 1 3 5 8 9 13 21 22 23 32
#include <>
main()
{int I,j,t,a[10];
for(I=0;I<10;I++) scanf(“%d”,&a[I]);/*输入数据到数组*/
for(I=0;I<9;I++)
for(j=I+1;j<10;j++)
if(a[I]>a[j])
{t=a[I];a[I]=a[j];a[j]=t;
}
printf(“\n”);
for(I=0;I<10;I++)printf(“%6d”,a[I]);/*输出排序后的数据*/
}
分析:
从程序可知:
。
。若数组有N个元素,则共进行N-1趟排序。第一趟,I=0;第二趟,I=1,···
[I,9]的区间内选择最小数。比较次数随趟数增大而减少。
,当后面元素较小时,马上进行交换。而这种交换是不必要的。事实上,只要记住较小元素的位置,即下标,在内循结束后做一次交换即可,这样可大大节省程序运行时间。
改进排序过程如下:
5 13 3 9 32 22 8 1 23 21
① 1 13 3 9 32 22 8 5 23 21
② 1 3 13 9 32 22 8 5 23 21
③ 1 3 5 9 32 22 8 13 23 21
④ 1 3 5 8 32 22 9 13 23 21
⑤ 1 3 5 8 9 22 32 13 23 21
⑥ 1 3 5 8 9 13 32 22 23 21
⑦ 1 3 5 8 9 13 21 22 23 32
⑧ 1 3 5 8 9 13 21 22 23 32
⑨ 1 3 5 8 9 13 21 22 23 32
改进后的程序见下页,注意与前一程序比较
#include <>