【六月五号】排序算法之冒泡排序

今天说的仍然是一中简单排序——冒泡排序，时间复杂度O(n^2)。
其基本思想是：
通过相邻元素之间的比较和交换使较小的元素逐渐从后向前移动，就像水底的气泡一样逐渐向上冒。
具体过程如下：
首先比较d[n]和d[n-1]，若d[n]<d[n-1]，则交换，使较小的元素前移，较大的元素后移；接着比较d[n-1]和d[n-2]，以此类推，直到比较d[2]和d[1]并使较小的元素前移，第一趟排序结束,则d[1]为最小的元素。然后在d[2]..d[n]间进行第二趟排序，使第二小元素前移到d[2]位置；n-1趟排序后，整个冒泡排序结束。
假设我们将把2252204119024218542231这8个数排序
排序过程演示
　　初始关键字：[2252204119024218542231]不交换
　　d[8]和d[7]：[2252204119024218542231]交换
　　d[7]和d[6]：[2252204119024242185231]交换
　　d[6]和d[5]：[2252204119042242185231]交换
　　d[5]和d[4]：[2252204142190242185231]不交换
　　d[4]和d[3]：[2252204142190242185231]交换
　　d[3]和d[2]：[2254122042190242185231]交换
　　d[2]和d[1]：[4122522042190242185231]
　　
　　以上是一趟排序的演示，总共需要进行n-1趟排序
　　第一趟排序后：41[22522042190242185231]
　　第二趟排序后：4142[225220185190242231]
　　第三趟排序后：4142185[225220190231242]
　　第四趟排序后：4142185190[225220231242]
　　第五趟排序后：4142185190220[225231242]
　　第六趟排序后：4142185190220225[231242]
　　第七趟排序后：4142185190220225231242


　　Pascal代码：

　　const mx=10000;

　　var

　　 d:array[1..mx]of longint;

　　 n,i,j,k:longint;

　　begin

　　 readln(n);

　　 for i:=1 to n do read(d[i]);

　　 for i:=1 to n-1 do

　　 begin

　　 for j:=n-1 downto i do

　　 if d[j+1]<d[j] then

　　 begin //相邻元素交换

　　 k:=d[j]; d[j]:=d[j+1]; d[j+1]:=k;

　　 end;

　　 end;

　　 for i:=1 to n do writeln(d[i]);

　　End.