初中信息技術(shù)-python編程【用排序讓數(shù)據(jù)更有序】

1、初中信息技術(shù)python編程【用排序讓數(shù)據(jù)更有序】計算機(jī)誕生之初是為了幫人類簡化計算工作，其處理的對象是數(shù)據(jù)。數(shù)據(jù)操作里 面，排序是數(shù)據(jù)進(jìn)一步處理的基礎(chǔ)。在生活和學(xué)習(xí)中，我們經(jīng)常會遇到排序問題，如 班級成績排名、跑操時按身高排序、計算機(jī)中文件的排序方式等。將數(shù)據(jù)排序?qū)⒂欣?于對信息進(jìn)行高效地檢索、分類，對當(dāng)前人工智能的開展具有重要意義。通過本章的學(xué)習(xí)，你將能夠掌握：Python中的列表排序冒泡排序桶排序選擇排序算法的時間復(fù)雜度微工程1合并分區(qū)的列表排序成績單上的成績是按總分從高到底排序的、上體育課大家站隊時是按照身高從高 到低排序的、超市里的商品總是按種類擺放展示的生活中排序的例子比比皆是，

2、同學(xué)們有沒有自己做過排序呢？還記得學(xué)習(xí)過的Excel表格嗎？在Excel中我們可以點 擊數(shù)據(jù)菜單下的排序?qū)崿F(xiàn)簡單的排序，既然Python這么強(qiáng)大，那么Python中是否也有 排序的方法呢？接下來讓我們一起學(xué)習(xí)Python中內(nèi)置的排序方法吧！通過本節(jié)的學(xué)習(xí)，你將掌握以下技能：學(xué)會列表中的sort。、sorted。函數(shù)學(xué)會使用列表內(nèi)置函數(shù)處理數(shù)據(jù)的程序并實際運行；二是所得時間的統(tǒng)計量依賴于計算機(jī)的硬件、軟件等環(huán)境因素， 有時容易掩蓋算法本身的優(yōu)勢。事前分析估算法即在計算機(jī)程序編寫前，依據(jù)統(tǒng)計方法對算法進(jìn)行估算。這種方 法拋開與計算機(jī)硬件軟件有關(guān)的因素，一個程序的運行時間，依賴于算法的好壞和問 題的

3、輸入規(guī)模，所謂問題輸入規(guī)模是指輸入量的多少。這種方法是我們通常采用的方 法。1.2時間復(fù)雜度估算學(xué)習(xí)完理論知識，我們通過一個小例子來體驗問題輸入規(guī)模對程序運行時間的影 響。為了得出程序的運行時間，我們只要在程序執(zhí)行前后分別獲取系統(tǒng)時間，然后計 算兩者的時間差，就能簡單的估算出程序運行的大致時間。在程序中，通過增加執(zhí)行次數(shù)，來估算對一個數(shù)字加一減一假設(shè)干次所需的時間， 從而比擬一個算法在不同問題規(guī)模下的實際運行時間。#模擬計算程序運行時間import timeproblemSize=1000print(1 ProblemsizeTime1)for count inrange(5):start=t

4、ime.time()work=lfor x inrange(problemSize):for y in range(problemSize):work+=lwork-=luseTime=time.time()-startprint( 1%8d%16.3f 1 %(problemSizeuseTime)problemsize *= 2控制臺Time 0.1950.7853.04311.46053.679ProblemSize 1000 2000 4000 800016000 程序運行結(jié)束problemSize記錄的是數(shù)字完成加一減一的次數(shù)，從結(jié)果可以看出，計算時間和問 題規(guī)模并不成正比，而是指數(shù)

5、關(guān)系，因為中間嵌套的是兩次循環(huán)，當(dāng)問題規(guī)模增加一 倍，計算量隨即增加至嫄來的四倍，因此計算時間也會增加到原來的四倍。用這種方法估算運算時間并不準(zhǔn)確，因為計算機(jī)在運行這一段代碼的時候，也同 時穿插運行在同一個計算機(jī)中的其他代碼，但是可以用于大致的時間估算。不同的計算機(jī)在執(zhí)行同一算法的時候所用時間不同，這導(dǎo)致用時間來估算算法性 能并不客觀。在一個算法中，某個步驟執(zhí)行次數(shù)并不會因為運行環(huán)境而有所差異，因 此我們使用算法的基本操作執(zhí)行次數(shù)來描述運行時間，基本執(zhí)行操作次數(shù)又稱為“執(zhí)行 頻次。專題二：大O表示法為了更清晰的表示算法的運行時間，我們使用大。表示法描述。那么什么是大0 表示法呢？2.1大O表示

6、法大O表示法是關(guān)于一個算法的最壞情況下的估算。即使是同一計算機(jī)，不同的輸 入大小會造成運行時間不同，假如輸入規(guī)模為n(輸入量的多少)，那么n的大小決定了 執(zhí)行頻次，所有語句的執(zhí)行頻次描述為問題規(guī)模n的函數(shù)T(n)o用大0表示法描述算 法的時間復(fù)雜度為：T(n)=O(f(n)其中，f(n)是與輸入規(guī)規(guī)模n有關(guān)的函數(shù)。#時間復(fù)雜度計兌 T J T -/* I Tm=0n=100for i in range(n):I m = m+i右圖中為累加求和的程序，通過讀程序可以知道，12第2、3行語句只執(zhí)行一次，此時f(n)=2 ,而第4行為 3一個n次的單重for循環(huán)，每次循環(huán)執(zhí)行的語句為第54行的m=m

7、+i ,因此第4行、第5行代碼都執(zhí)行n次，5 此時 f(n)=2n+2 次。當(dāng)n趨近于無窮大時，f(n)中的常數(shù)項2對于整個公式的值的影響可以忽略，同樣, 最大項的系數(shù)2相比于數(shù)據(jù)規(guī)模n也可以忽略不計，最后變?yōu)閒(n) = n ,這就是分析算 法時間復(fù)雜度時常用的漸進(jìn)記法，因此該算法的時間復(fù)雜度為0(n)。像這樣的表示法 就叫做大。表示法。大O表示法指出了算法有多快。算法的時間復(fù)雜度用于表達(dá)算法的運算次數(shù)和問題規(guī)模的關(guān)系，不同算法有不一樣的復(fù)雜度，如下表所示：問題規(guī)模n對數(shù)階log2n線性階n平方階n2指數(shù)階2n1007100104約 1.27*1031000101000106數(shù)值過大1000

8、0002010000001012數(shù)值過大有時候在少量數(shù)據(jù)的情況下，因為現(xiàn)在計算機(jī)速度相對較快，所以實際運算時間 相差無幾。比方假設(shè)n是100 ,計算2的n次方和2n的值時計算機(jī)幾乎瞬間就可以計 算出結(jié)果，可是一旦問題規(guī)模倍數(shù)增長，那么運算時間會有明顯不同。12345678910#時間復(fù)雜度計算import timen=int(input(請輸入n的值：,)start=time.time()print(2*n)print(%16.3f1%(time.time()-start)start = time.timeOprint(2*n)print(1%16.3f1 % (time.time()-sta

9、rt)控制臺請輸入n的值：1000.0012000.000n=100控制臺2.42420000000.000n=1000000從圖中可以看出,當(dāng)n的值為1000000時，計算2的n次方大致需要2.424秒。但是計算2n的時間很短暫，以至于無法準(zhǔn)確估算（顯示需要時間為0 ）。由此可見，即 使相同規(guī)模的輸入，不同算法的運行時間也可能不同。2.2最好情況、最差情況和平均情況假設(shè)有一個算法可以把下面兩個序列按照從小到大排序。A ： 1 2345 6B ： 23 7 1 04兩個序列雖然都是六個數(shù)字，但是A序列已經(jīng)排序完畢，并不需要任何移動的操 作，而B序列是混亂的，排序過程需要一定的移動次數(shù)。如果用同

10、一種方法進(jìn)行排序, 那么可能會出現(xiàn)運算時間上的不同。我們會把最正確情況下算法進(jìn)行排序的時間叫做最好情況，而相對的，也存在最大 混亂度的排序，這時候運行時間那么為最壞情況，但是實際上這兩種情況都比擬少見。 一般對算法的評估是指算法在平均情況下的性能。鞏固與提高1、下面描述正確的選項是：()A、算法每一步的描述可以是概括的、籠統(tǒng)的，只要人們能夠理解讀懂即可。B、輸入規(guī)模與算法執(zhí)行時間無關(guān)。C、大0表示法表示的是最正確情況下算法的運行時間。D、算法是計算或者解決特定問題的步驟，同一個問題可以用不同算法解決。2、假設(shè)某一算法執(zhí)行頻次T=4n3+3n2+6，那么用大O表示法得出的算法復(fù)雜度為 ()A、O

11、(4n3) B、O(4n3+3n2) C、0(n3)D、O(4n3+3n2+6)3、某算法的時間復(fù)雜度為0(/),說明該算法()A、問題規(guī)模是n2B、執(zhí)行時間等于n2C、執(zhí)行時間與成n2正比D、問題規(guī)模與n2成正比專題一：Python中的內(nèi)置排序期中考試結(jié)束了，為了知道班里學(xué)生的考試情況，我們需要對班級所有學(xué)生的總 分按從高到低排序，那么要如何進(jìn)行排序呢？先來了解下排序函數(shù)吧！Python內(nèi)置的排序函數(shù)Python中內(nèi)置的排序函數(shù)有兩個：sort函數(shù)和sorted函數(shù),其中：sort。函數(shù)是列表內(nèi)置的方法，沒有返回值，該函數(shù)可以直接修改列表。函數(shù)原 型為：L.sort(key=None, re

12、verse=False)其中L為待排序的列表，key參數(shù)是指用來比擬的關(guān)鍵字，可以說是列表元素的一 個權(quán)值。key一般用來接受一個函數(shù)(或者匿名函數(shù))，這個函數(shù)只接受一個元素，并返 回其權(quán)值，默認(rèn)key值為空，如果為key進(jìn)行了賦值，那么sort函數(shù)將按照權(quán)值大小進(jìn) 行排序。reverse參數(shù)表示是否逆序排列，默認(rèn)的False。sorted。函數(shù)是全局內(nèi)置的方法，有返回值，它會將一個可迭代對象構(gòu)建出一個新的排序列表，但是原列表不變，函數(shù)原型為：sorted(iterable, key=None, reverse=False)當(dāng)排序?qū)ο笫亲值鋾r，sorted函數(shù)默認(rèn)的排序是對字典key的排序，除

13、列表、字典 外，sorted函數(shù)也可以對元組數(shù)據(jù)排序,參數(shù)key和reverse用法與列表中的相同。那么sort函數(shù)和sorted函數(shù)到底有何不同1 #Python中的sort排序 23 listl = 4,6,7,3,5,1,2,8)9#調(diào)用sort函數(shù)排序listl.sort()print(1listl:1 listl)1 #Python 中的sorted 排序23 listl = 4,6,7,3,5,1,2,8,9#調(diào)用sort函數(shù)排序sorted(listl)print(listl:, listl)控制臺控制臺listl: 1, 2, 3, 4, 5, 6, 7, 8, 9fl lis

14、tl: 4, 6, 7, 3, 5, 1, 2, Q, 9程序運行結(jié)束程序運行結(jié)束從程序中可以看出，列表list1在調(diào)用sort函數(shù)后已經(jīng)變成了有序的列表，而在使 用sorted函數(shù)后，list1列表沒有變化，那么sorted函數(shù)的排序結(jié)果要如何輸出呢?將 sorted(listl)賦值給新的列表list2即可。#Python 中的sorted 排序listl = 4j6j7,3,5,l,2j8,9#調(diào)用sort函數(shù)排序list2 = sorted(listl)print(1list2: )list2)print(1listl:listl)控制臺list2: lr 2r 3, 4, 5, 6,

15、 7, 8，9 listl: 4, 6, 7, 3, 5, 1, 2, 8r 9程序運行結(jié)束.2全班成績來排序借助sorted函數(shù)對班級中每一位學(xué)生的成績做排序，我們排序時需要保存學(xué)生的姓名和分?jǐn)?shù)，因此用字典存儲學(xué)生的成績信息。第一步：新建字典dictl ,將班里學(xué)生的姓名設(shè)置為key值，考試分?jǐn)?shù)為value值。#全班成績來排序#新建字典，姓名：分?jǐn)?shù)4 dictl = ,Daivd,:864 ,Tom,:90, Lucy:88, Amy:89 Lily:93)第二步：使用sorted函數(shù)將學(xué)生成績按降序排序，sorted函數(shù)默認(rèn)的排序為升序， 這是因為參數(shù)reverse的取值默認(rèn)值為False

16、。#全班成績來排序#新建字典，姓名：分?jǐn)?shù)dictl = Daivd :86, Tom* :90 Lucy:88, Amy:89, *Lily, :9325卜使用sorted函數(shù)按分?jǐn)?shù)降序排序listl = sorted(diet 1.itemsO., key=lambda item: itemfl.,reverse=True)程序中的dictLitems。實際上是將dictl轉(zhuǎn)換為可迭代對象，迭代對象的元素為 (Daivd,86)、(Tom,90)、(Tucy88)x (9Amy89)x (9Lily93) , items。方法將字典的 元素轉(zhuǎn)化為了元組，而這里key參數(shù)對應(yīng)的lambda表達(dá)

17、式的意思那么是選取列表中元組 的第二個元素作為key值的比擬參數(shù),如果寫作key=lambdaitem:itemO的話那么是選取 第一個元素作為key值的比擬對象。所以采用這種方法可以對字典的value進(jìn)行排序。 注意排序后的返回值是一個列表，原字典中的鍵值對被轉(zhuǎn)換為了列表中的元組。lambda是Python中關(guān)鍵字，用于定義lambda函數(shù)，lambda函數(shù)即匿名函數(shù)是指 一類無需定義函數(shù)名的函數(shù)或子程序。如lambda x: x*x中的x表示輸入?yún)?shù)，x*x表示lambda函數(shù)的返回值，與以下寫法等價：def f(x): return x+x第三步：將排序好的成績信息依次輸出。sorted

18、函數(shù)排序后將字典轉(zhuǎn)換成了包含元組的列表。因此，我們只需要將列表的元組元素按照姓名、成績的順序輸出即可。#全班成績來排序#新建字典，姓名：分?jǐn)?shù)dictl = Daivd:86, Tom:90, 1 Lucy:88, Amy:89, ,Lily,:93)#使用sorted函數(shù)按分?jǐn)?shù)降序排序listl = sorted(dictl.items(), key=lambda item: itemlreverse=True)#輸出排序好的成績信息print(Name Score)b for i in listl:print(%-6s%4d %il)程序中利用for循環(huán)遍歷listl中的元組，然后將讀取到的

19、元組按照姓名和分?jǐn)?shù)的 樣式對齊輸出。專題二：Timsort算法Timsort算法是Tim Peters在2002年設(shè)計出的一種結(jié)合了歸并排序和插入排序而得 出的排序算法，是Python中l(wèi)ist.sort的默認(rèn)實現(xiàn)。該算法的核心過程是找到數(shù)據(jù)中已經(jīng) 排好序的塊分區(qū)，每一個分區(qū)叫一個run ,然后按規(guī)那么合并這些run?，F(xiàn)在JavaSE7和 Android也采用Timsort算法對數(shù)組排序。在現(xiàn)實中，給定的大局部數(shù)組中通常是有局部已經(jīng)排好序的(無論是升序還是降 序)，Timsort算法正是利用了這一點。Timsort排序算法的輸入的單位不是一個個單獨 的數(shù)字，而是一個個的分區(qū)。針對這些run序列

20、，每次拿一個run出來進(jìn)行歸并。每次 歸并會將兩個run合并成一個run ,每個run最少要有2個元素。Timsort算法在進(jìn)行分區(qū)的時候是按照升序和嚴(yán)格降序的規(guī)那么進(jìn)行的，將原來的數(shù) 組分解為假設(shè)干個run ,升序的run就保持不變，嚴(yán)格降序的run就翻轉(zhuǎn)，最終得到假設(shè)干 個升序的run。比方：現(xiàn)在有一個目標(biāo)的數(shù)組1,598,6,4,5,6,7,我們可以看到1,5,9符 合升序，8,6,4符合嚴(yán)格降序，4,5,6,7符合升序，將嚴(yán)格降序的run翻轉(zhuǎn)，然后拼湊 得到新的數(shù)組口 59,6,8,4,5,6,7。在分割完run后定義最小run長度，短于此的run通過插入排序合并為長度高于最 小run

21、的長度，然后反復(fù)歸并相鄰的run ,在歸并的過程中要防止歸并長度相差很大的 run ,直至整個排序完成。當(dāng)然真實的Timsort算法比我們描述的要更加復(fù)雜，比方對run長度的優(yōu)化、相鄰 run的合并等，總體來說，Timsort算法是一種混合、穩(wěn)定高效的排序算法，在最壞的 情況下，Timsort算法時間復(fù)雜度為O(nlogn)。在最正確情況下，即輸入已經(jīng)排好序，它 的時間復(fù)雜度為0(n),由此可以看出Timsort算法是目前最好的排序方式。鞏固與提高1、關(guān)于sort函數(shù)和sorted函數(shù)的說法正確的選項是()A、sort函數(shù)可以對列表、字典、元組等排序B、執(zhí)行l(wèi)istl.sort()后,list

22、l仍然是無序的C、sorted函數(shù)只能對列表排序D、當(dāng)使用sorted函數(shù)對列表listl排序后,listl不變微工程2相鄰比擬的冒泡排序課本上評委打分冒泡排序的例子(第2冊71-75頁)#冒泡排序Is=9,8,7,6,5,4,3,2,1for k in range(0,len(s)-l):for i in rang(0,len(s)-k-l):if sisi+l:|si,si+l=si+l,siprint(第次比擬的結(jié)果： .format(i+l,s) print(，第輪比擬的結(jié)束，結(jié)果為：，.format(k+l, s) print()微工程3快速穩(wěn)定的桶排序課本技術(shù)探索(第2冊76-77

23、頁)微工程4明明同學(xué)的隨機(jī)數(shù)信息學(xué)奧賽題目明明想在學(xué)校中請一些同學(xué)一起做一項問卷調(diào)查，為了實驗的客觀性，他先用計算機(jī)生成了N個1到1000 之間的隨機(jī)整數(shù)(Ng 100),對于其中重復(fù)的數(shù)字，只保存一個，把其余相同的數(shù)去掉，不同的數(shù)對應(yīng)看 不同的學(xué)生的學(xué)號。然后再把這些數(shù)從小到大排序，按照其好的)噴序去找同學(xué)做調(diào)查。請你協(xié)助明明完成去重與排序”的工作。1的甬排序，明明的隨機(jī)數(shù)n=int(input()a=input().split()d=int(c) for c in acount=0b=for i in range(0,1001):b.append(0)for i in range(n):bdi=lfor i in range(l1001):if bi!=0:count+=