经典算法之 冒 泡 排 序.

Presentation on theme: "经典算法之 冒 泡 排 序."— Presentation transcript:

1 经典算法之 冒 泡 排 序

2 小结： 对一个数组的n个元素进行排序，最多要进行n-1趟冒泡。 第一趟冒泡要经过n-1次比较 第二趟冒泡要经过n-2次比较 …….

3 升序的冒泡排序 For i= 1 to n-1 For j=n to i+1 step -1 if a(j)<a(j-1) then
t=a(j):a(j)=a(j-1):a(j-1)=t end if Next j Next i

4 冒泡排序算法的优化 可以从哪方面去优化冒泡排序算法呢？ 数组：30,40, 20,50,10 第一趟：10,30,40,20,50
第二趟：10,20,30,40,50 第三趟：10,20,30,40,50 （因不存在交换，排序ok） 优化思路：哪趟不存在交换，就意味着数组已经有序，无需继续排序。

5 优化的冒泡排序 i = 1 flag = True Do While flag = True And i <= n - 1
flag = False For j = n To i + 1 Step -1 If a(j) < a(j - 1) Then t = a(j): a(j) = a(j - 1): a(j - 1) =t End If Next j i = i + 1 Loop Label1.caption=”共需”+str(i-1)+”趟”

6 变式：往下沉的冒泡排序 下沉式冒泡： 把较大的数据逐次向下推移的一种排序。从第一个元素起，依次比较相邻的两个 元素中的数据，将较大的数据沉到下面。 例：数组元素：50,30, 40,20, 10 , 按从小到大排序。 往下沉的第一趟： 30, 40,20,10,50 第二趟： 30,20,10,40,50 第三趟： 20,10,30,40,50 第四趟： 10,20,30,40,50

7 下沉式升序冒泡 For i= 1 to n-1 For j=1 to n-i if a(j)>a(j+1) then
t=a(j):a(j)=a(j+1):a(j+1)=t end if Next j Next i

8 选择排序

9 选择排序算法 选择排序（递增）的思路是 先找出n个数中最小的数据（下标跟踪），与数组第一个元素中的数据交换位置
依次类推，直到排序结束。

10 选择排序和冒泡排序的比较 冒泡排序（教材） 选择排序 算法思维 相邻比较，直接交换
寻找及确定最小数的位置（下标），将该位置的数与第1个数交换，接着找第2小的数的位置（下标），与第2小的数交换…… 趟数（遍数） n-1 比较次数 1/2*n*(n-1) 交换次数 <=1/2*n*(n-1) <=n-1

11 特点：平行加一，下标跟随，数值交换，小数上冒。
n个数选择排序 For i = 1 To n - 1 k = i For j = i + 1 To n If a(j) <a(k) Then k = j Next j If k <> i Then t = a(i): a(i) = a(k) : a(k)= t End If Next I 特点：平行加一，下标跟随，数值交换，小数上冒。

12 变式一：从尾到头的选择排序 从尾到头的选择排序（升序）的思路是 先找出n个数中最大的数据（下标跟踪），与数组最后一个元素交换。
依次类推，直到排序结束。

13 VB代码实现从尾到头升序选择排序 For i = n To 2 step -1 k =i For j =1 To i-1
If a(j) > a(k) Then k = j Next j If k <> i Then t = a(k): a(k) = a(i): a(i) = t End If Next i

14 变式二：比较后直接交换的选择排序 第i趟：把第i+1个数到第n个数逐个与第i个数相比，若比a（i）小，直接交换

15 从头到尾直接交换的升序选择排序 For i = 1 To n - 1 For j = i + 1 To n
If a(j) < a(i) Then T=a(j):a(j)=a(i):a(i)=t End if Next j Next i