冒泡排序法
冒泡排序的基本思想是:依次比较相邻的两个数,将大数放在前面,小数放在后面。即首先比较第1个和第2个数,将大数放前,小数放后。然后比较第2个数和第3个数,将大数放前,小数放后,如此继续,直至比较最后两个数,将大数放前,小数放后,此时第一趟结束,在最后的数必是所有数中的最小数。重复以上过程,仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再大于第2个数),将大数放前,小数放后,一直比较到最小数前的一对相邻数,将大数放前,小数放后,第二趟结束,在倒数第二个数中得到一个新的最小数。如此下去,直至最终完成排序。
由于在排序过程中总是大数往前放,小数往后放,相当于气泡往上升,所以中冒泡排序。
用二重循环实现,外循环变量设为i,内循环变量设为j。外循环重复9次,内循环依次重复9,8,...,1次。每次进行比较的两个元素都是与内循环j有关的,它们可以分别用a[j]和a[j+1]标识,i的值依次为1,2,...,9,对于每一个i, j的值依次为1,2,...10-i。
算法:
1、输入10个数到数组a中
2、从大到小排序数组a
for i:=1 to 9 do
for j:=1 to 10-i do
if a[j]<a[j+1]
then 交换a[j]与a[j+1]
3、输出排序后的数组a。
程序:
program sort21(input,output);
var
a:array[1..10] of real;
temp:real;
i,j:integer;
begin
for i:=1 to 10 do
begin
read(a);
write(a<i>);
if i mod 5=0 then writeln;
end;
for i:=1 to 9 do
for j:=1 to 10-i do
if a[j]<a[j+1] then
begin
temp:=a[j];
a[j]:=a[j+1];
a[j+1]:=temp;
end;
for i:=1 to 10 do
begin
write(a<i>);
if i mod 5 =0 then writeln;
end;
end.
- 冒泡排序法的改进 **
比如用冒泡排序将4、5、7、1、2、3这6个数排序。在该列中,第二趟排序结束后,数组已排好序,但计算机此时并不知道已经反排好序,计算机还需要进行一趟比较,如果这一趟比较,未发生任何数据交换,则知道已排序好,可以不再进行比较了。因而第三趟比较还需要进行,但第四、五趟比较则是不必要的。为此,我们可以考虑程序的优化。
为了标志在比较中是否进行了,设一个布尔量flag。在进行每趟比较前将flag置成true。如果在比较中发生了数据交换,则将flag置为false,在一趟比较结束后,再判断flag,如果它仍为true(表明在该趟比较中未发生一次数据交换)则结束排序,否则进行下一趟比较。
算法:
1、输入10个数到数组中
2、从大到小排序数组a
i:=1
repeat
flag:=true;
for j:=1 to 10-i do
if a[j]<a[j+1] then
begin
交换a[k]与a[j]
flag:=false;
end;
i:=i+1;
until flag;
3、输出排序后的数组a
程序:
program sort22(input,output);
var
a:array[1..10] of real;
temp:real;
i,j:integer;
flag:boolean;
begin
for i:=1 to 10 do read(a<i>);
i:=1;
repeat
flag:=true;
for j:=1 to 10-i do
if a[j]<a[j+1] then
begin
temp:=a[j];
a[j]:=a[j+1];
a[j+1]:=temp;
flag:=false;
end;
i:=i+1;
until flag;
for i:=1 to 10 do write(a<i>,' ');
end.
void bubblesort(type* arr,long len)/*bubble sort algorithm*/
{
long i=0,j=0;/*iterator value*/
assertf(arr!=null,"in bubble sort,arr is null\n");
for (i=len;i>1;i--)
for(j=0;j<i-1;j++)
if(arr[j]>arr[j+1])swaparrdata(arr,j,j+1);
}
从数组的后面位置开始,如果发现有比前面一个位置处的数更小的元素,则把交换这两个数的位置,形成一个类似轻的气泡在水中上升的排序过程.