2021学年第二章 数据与链表本章综合与测试课堂教学ppt课件

这是一份2021学年第二章 数据与链表本章综合与测试课堂教学ppt课件，共16页。PPT课件主要包含了1第一遍冒泡，2第二遍冒泡，3第三遍冒泡，我来拼一拼，选择排序的基本思想，1第1遍排序，2第2遍排序，3第3遍排序，算法演示分析，第1遍选择等内容，欢迎下载使用。

共进行（ ）次比较，（ ）次交换
选择排序（升序）的方法是 第1步： 找出n数组元素（d(1)~d(n))中最小的数据，使它与第1个数据d(1) 交换位置。 第2步：在余下的元素d(2)~d(n))中继续找最小的数据，使它与第2个数据d(2) 交换位置。 …………………… 第i步：在剩下的元素（d(i)~d(n)) 中找出最小数，使它与第i个数据d(i)交换位置。
*代表未排序子序列中 的最小元素
4个数选择排序(升序)
共进行（ ）次交换
k=1Fr j=2 t 4 if d(k)>d(j) then k=jNext j 交换d(1)和d(k)
If k<>1 then
k=2Fr j=3 t 4 if d(k)>d(j) then k=jNext jIf k<>2 then 交换d(2)和d(k)
k=3Fr j=4 t 4 if d(k)>d(j) then k=jNext jIf k<>3 then 交换d(3)和d(k)
k=1Fr j=2 t 4 if d(k)>d(j) then k=jNext jIf k<>1 then 交换d(1)和d(k)
找一找带颜色数字与i的关系？
*第1遍选择 ，j从2开始到4
k=1Fr j=2 t 4 if d(k)>d(j) then k=jNext jIf k<>1，交换d(1)和d(k)
k=2Fr j=3 t 4 if d(k)>d(j) then k=jNext jIf k<>2 then 交换d(2)和d(k)
*第2遍选择 ，j从3开始到4
*第3遍选择 ，j从4开始到4
k=3Fr j=4 t 4 if d(k)>d(j) then k=jNext jIf k<>3 then 交换d(3)和d(k)
Fr i=1 t 3k=ifr j=i+1 t 4 if d(k)>d(j)then k=jnext jif k <> i then 交换d(i)和d(k)end ifNext i
n个数选择排序的基本算法
找出d(i)至d(n)中的最小值
将最小值与第i个数据d(i)交换位置
Fr j = i+1 t n
Fr i = 1 T n - 1 k = i Fr j = i + 1 T n If d(k) > d(j) Then k = j endif Next j If k <> i Then t = d(i) d(i) = d(k) d(k) = t End IfNext i
利用已学的选择排序算法，对初始数据【49,38,65,97,76,13,27,59】升序排序。
与待排序元素的初始状态有关，当待排序已经有序时，交换0次。最坏情况下：
比较次数：与待排序元素的初始状态无关