53數(shù)據(jù)排序-選擇課件高二上學(xué)期選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》第五章浙教版

5.5數(shù)據(jù)排序–選擇排序（升序?yàn)槔稊?shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》一、選擇排序基本思想：是對(duì)參加排序的數(shù)組中所有元素中找出最?。ɑ蜃畲螅┑臄?shù)據(jù)，使它與第一個(gè)（或最后一個(gè)）元素中的數(shù)據(jù)進(jìn)行相互交換位置。然后在余下的元素中找出最?。ɑ蜃畲螅┑臄?shù)據(jù)，與第二個(gè)（或最后第二個(gè)）元素中的數(shù)據(jù)交換位置。以此類推，直到所有元素稱為一個(gè)有序的序列。一、選擇排序過(guò)程每趟排序后數(shù)組a的值分別為：第1趟：[1,9,3,8,5,2]第2趟：[1,2,3,8,5,9]第3趟：[1,2,3,8,5,9]第4趟：[1,2,3,5,8,9]第5趟：[1,2,3,5,8,9]一、選擇排序過(guò)程注意：紅色標(biāo)記最小值

綠色標(biāo)記待排序區(qū)間

黃色標(biāo)記有序區(qū)間三、選擇排序和冒泡排序

對(duì)比小結(jié)冒泡排序選擇排序排序遍數(shù)比較次數(shù)交換次數(shù)時(shí)間復(fù)雜度n-1n-1(n-1)*n/2(n-1)*n/2逆序?qū)?shù)量<=n-1O(n2)O(n2)選擇排序的比較次數(shù)與待排序元素的初始狀態(tài)無(wú)關(guān)，而交換次數(shù)與待排序元素的初始狀態(tài)有關(guān)，當(dāng)待排序元素已經(jīng)有序時(shí)，交換

0次，最壞情況下交換n-1次。一、選擇排序程序?qū)崿F(xiàn)(以升序?yàn)槔?i=0;min=?forjinrange(1,?)#依次比較找最小值的下標(biāo)ifa[j]

?

a[min]:#升序排序min=jifmin!=?:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值i=0;min=0forjinrange(1,6)#依次比較找最小值的下標(biāo)ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值一、選擇排序程序?qū)崿F(xiàn)(以升序?yàn)槔?i=1;min=?#假設(shè)待排序區(qū)間第一個(gè)元素為擂主forjinrange(?,?)#依次比較找最小值的下標(biāo)ifa[j]

?

a[min]:#升序排序min=jifmin!=?:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值i=1;min=1#假設(shè)待排序區(qū)間第一個(gè)元素為擂主forjinrange(2,6)#依次比較找最小值的下標(biāo)ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值一、選擇排序程序?qū)崿F(xiàn)(以升序?yàn)槔?i=2;min=?forjinrange(?,?)#依次比較找最小值的下標(biāo)ifa[j]

<

a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值i=2;min=2forjinrange(3,6)#依次比較找最小值的下標(biāo)ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值一、選擇排序程序?qū)崿F(xiàn)(以升序?yàn)槔?i=3;min=?forjinrange(?,?)#依次比較找最小值的下標(biāo)ifa[j]

<

a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值i=3;min=3forjinrange(4,6)#依次比較找最小值的下標(biāo)ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值一、選擇排序程序?qū)崿F(xiàn)(以升序?yàn)槔?i=4;min=?forjinrange(?,?)#依次比較找最小值的下標(biāo)ifa[j]

<

a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值i=4;min=4forjinrange(5,6)#依次比較找最小值的下標(biāo)ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值一、選擇排序程序?qū)崿F(xiàn)(6個(gè)元素升序?yàn)槔?i=0;min=0#第一趟排序forjinrange(1,6)#依次比較找最小值的下標(biāo)ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值i=1;min=1#第二趟排序forjinrange(2,6)#依次比較找最小值的下標(biāo)ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值i=2;min=2#第三趟排序forjinrange(3,6)#依次比較找最小值的下標(biāo)ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值i=3;min=3#第四趟排序forjinrange(4,6)#依次比較找最小值的下標(biāo)ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值i=4;min=?#第五趟排序forjinrange(5,6)#依次比較找最小值的下標(biāo)ifa[j]

<

a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交換a[min]與a[i]的值n=len(a)

#n個(gè)元素規(guī)模升序排序

做個(gè)筆記寶典P82foriinrange(?)#外循環(huán)表示排序趟次

min=?#假設(shè)待排序區(qū)間第一個(gè)元素為擂主

forjinrange(?,?):#將每個(gè)元素跟當(dāng)前擂主PK

ifa[j]

?

a[min]:#PK成功則更換擂主min=j

#更換擂主ifmin!=i

:a[min],a[i]=a[i],a[min]

#交換n-1ii+1n<二、選擇排序和冒泡排序

程序?qū)Ρ刃〗Y(jié)n=len(a)

#選擇排序

順序掃描foriinrange(n-1)#排序最多n-1趟

min=i#假設(shè)待排序區(qū)間第一個(gè)元素為擂主

forjinrange(i+1,n):#將每個(gè)元素跟當(dāng)前擂主PK

ifa[j]

<

a[min]:#PK成功則更換擂主

升序

min=j

#更換擂主ifmin!=i

:

a[min],a[i]=a[i],a[min]

#交換n=len(a)#冒泡排序

逆序掃描foriinrange(n-1):#排序n-1趟

forjinrange(n-1,i,-1):#從后往前掃描ifa[j-1]>a[j]:#相鄰元素比較

升序

a[j],a[j-1]=a[j-1],a[j]#交換選擇與冒泡排序的最大區(qū)別:選擇排序待排序區(qū)間內(nèi)的元素a[min]能與最左端（或最右端）的元素a[i]發(fā)生交換，冒泡排序是相鄰元素交換。對(duì)比兩段程序，為何選擇排序更高效，主要就是因?yàn)橛衜in變