首页 > 代码库 > 排序算法之冒泡排序
排序算法之冒泡排序
今天说的仍然是一中简单排序——冒泡排序,时间复杂度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趟排序后,整个冒泡排序结束。
假设我们将把225 220 41 190 242 185 42 231这8个数排序
排序过程演示 澳门赌场有哪些
初始关键字:[225 220 41 190 242 185 42 231]不交换
d[8]和d[7]:[225 220 41 190 242 185 42 231]交换
d[7]和d[6]:[225 220 41 190 242 42 185 231]交换
d[6]和d[5]:[225 220 41 190 42 242 185 231]交换
d[5]和d[4]:[225 220 41 42 190 242 185 231]不交换
d[4]和d[3]:[225 220 41 42 190 242 185 231]交换
d[3]和d[2]:[225 41 220 42 190 242 185 231]交换
d[2]和d[1]:[41 225 220 42 190 242 185 231]
以上是一趟排序的演示,总共需要进行n-1趟排序
第一趟排序后:41 [225 220 42 190 242 185 231]
第二趟排序后:41 42 [225 220 185 190 242 231]
第三趟排序后:41 42 185 [225 220 190 231 242]
第四趟排序后:41 42 185 190 [225 220 231 242]
第五趟排序后:41 42 185 190 220 [225 231 242]
第六趟排序后:41 42 185 190 220 225 [231 242]
第七趟排序后:41 42 185 190 220 225 231 242