冒泡排序算法

冒泡排序（也称为Exchange排序）是一种简单的排序算法。它的工作方式是重复遍历要排序的列表, 一次比较两个项目, 如果顺序错误则交换它们。重复遍历列表, 直到不需要交换为止, 这意味着对列表进行了排序。

这是所有排序算法中最简单的方法。

BUBBLE SORT (A)
1. for i ← 1 to length [A]
2. for k ← length [A] down to i+1
3. if A[k] <A[k-1]
4. exchange (A[k], A [k-1])

分析

输入：给出n个元素。
输出：进行排序所需的比较数。
逻辑：如果在气泡排序中有n个元素, 则需要n-1次通过才能找到排序后的数组。

In pass 1: n-1 comparisons are required
  In pass 2: n-2 comparisons are required
  In pass 3: n-3 comparisons are required
 ............................................................................
 ...............................................................................
  In pass n-1: 1 comparisons is required 
  Total comparisons: T (n) = (n-1) + (n-2) +...........+ 1
                           = 
                           = o (n2)
   Therefore complexity is of order n2

例：

未排序清单：A = {7, 2, 1, 4, 4, 5, 9, 6}

即A [] =

Here length [A] =7 
 i=1 to 7 and j=7 to 2			
i=1, j=7
A [7] =6 and A [6] =9. So A [7] <A [6]
Now Exchange (A [7], A [6])
Now, i=1, j=6 then A [6] =6
		A [5] = 3 and A [5] < A [6]
Now, i=1, j=5 then A [5] = 3
		A [4] = 4 and A [5] < A [4]
So, exchange (A [5], A [4])

和A [] =

Now, i=1, j=4 then A [4] =3
		A [3] = 1 and A [4] > A [3]
Now, i=1, j=3 then A [3] = 1
		A [2] = 2 and A [3] < A [2]
So, exchange (A [3], A [2])

然后A [] =

Now, i=2, j-2 then A [2] =1
		A [1] =7 and A [2] <A [1]
	So, exchange (A [2], A [1])

然后A [] =

Now, i=1, j=7 then A [7] =9
				A [6] =6 and A [7] > A [6], No Exchange
	Similarly, i=2, j=6, 5, 4.	No change.
Then i = 2, j=3
	A [3] = 2
		A [2] = 7 and A [3] < A [2]
So, exchange (A [3], A [2])

和A [] =

Now, i=3, j=5, 6, 7 No change
Then i=3, j=4
	A [4] = 3
		A [3] = 7   and A [4] < A [3]
So, exchange (A [4], A [3])

然后A [] =

Now, i=4, j= 6, 7 No change
Now, i=4, j=5 then A [5] = 4
		A [4] = 7 and A [5] < A [4]
So exchange (A [5], A [4])

和A [] =

Now, i=5, j= 6, 7 No change
    Now, i=5, j=6 then A [6] = 6
		A [5] = 7   and A [6] < A [5]
So exchange (A [6], A [5])

和A [] =

是排序的数组。

分析

例：

猜你喜欢