第9章 排序電子課件

第9章排序本章講解排序。要求了解排序分類；掌握各種排序算法思想；靈活應(yīng)用排序。重慶是中國三大火爐之一。熱！夏天愛喝稀飯、下泡菜，比其他地方好吃因為熱！喝稀飯補充身體水分，吃泡菜補充流失的鹽分，因此各種粥和泡菜層出不窮吃喝得精光。誰越“光盤行動”得干凈，誰越愛惜糧食！來比比，來排排序。提綱9.1排序基本概念9.2插入排序9.3交換排序9.4選擇排序9.5歸并排序9.6分配排序9.7排序應(yīng)用9.8排序?qū)W習(xí)總結(jié)9.1排序基本概念定義排序在日常應(yīng)用較廣，如高考排名、高矮站隊、招聘擇優(yōu)、輕重緩急事務(wù)處理等等。它將1個無序序列按照關(guān)鍵字排成有序序列。9.1排序基本概念2.分類升序——降序穩(wěn)定——不穩(wěn)定內(nèi)部排序——外部排序9.1排序基本概念順序表元素類型類RecType描述順序表排序類SqListSort描述9.2插入排序插入排序的基本思想是每次將1個無序區(qū)元素插入到有序區(qū)中，直到所有元素插入完。插入排序主要有直接插入排序、折半插入排序和希爾排序。9.2.1直接插入排序舉例：摸撲克牌，要求最終手上的牌有序。初始：無序區(qū)是桌上1摞要摸的撲克牌，有序區(qū)為空空的手。摸了第1張牌后，以后每次摸了牌都要和手上的牌比較（從最大1張開始比較），再插入到合適的位置，直到摸完牌。這個摸牌過程就是直接插入排序。9.2.1直接插入排序設(shè)待排序表有10個元素，其關(guān)鍵字序列為（9，8，7，6，5，4，3，2，1，0）。說明采用直接插入排序方法進行排序的過程。9.2.1直接插入排序【算法9.1】設(shè)計1個算法，對R[0..n-1]按遞增有序進行直接插入排序。思路：見前面的直接插入排序算法思路。代碼見算法9.19.2.2折半插入排序折半插入排序思路是對直接插入排序思路的改進，不相同的是在將無序區(qū)某個元素插入到有序區(qū)時，不再是在有序區(qū)從右到左找到插入位置，而是通過在有序區(qū)折半查找算法找到插入位置，其他都相同。9.2.2折半插入排序【算法9.2】設(shè)計1個算法，對R[0..n-1]按遞增有序進行折半插入排序。思路：見前面的折半插入排序算法思路。代碼見算法9.29.2.3希爾排序

9.2.3希爾排序設(shè)待排序表有10個元素，其關(guān)鍵字分別為（9，8，7，6，5，4，3，2，1，0）。說明采用希爾排序方法進行排序的過程。9.2.3希爾排序【算法9.3】設(shè)計1個算法，對R[0..n-1]按遞增有序進行希爾排序。思路：見前面的希爾排序算法思路。代碼見算法9.39.3交換排序交換排序的基本思想是兩兩比較待排序元素的關(guān)鍵字，若為正序則繼續(xù)比較，若為反序則交換之，直到?jīng)]有反序的元素為止。交換排序主要有冒泡排序和快速排序。舉例：有男有女請7位同學(xué)上講臺，隨意站成1排，從左往右進行身高從矮到高的冒泡排序。再請1位同學(xué)當(dāng)導(dǎo)演，指揮他們?nèi)绾巫?。這位導(dǎo)演說：從左往右，第1趟兩兩比較經(jīng)過交換之后，最高的張三站到了最右邊；第2趟次高的李四站在了右邊倒數(shù)第2，依此類推經(jīng)過6趟后，排序完成。9.3.1冒泡排序初始：有序區(qū)為空，無序區(qū)為R[0...n-1]。無序區(qū)元素兩兩比較，若反序則交換；這樣1趟后最大/最小元素歸位（如氣泡一樣冒于水面）。重復(fù)（2），n-1趟后所有元素歸位即完成排序。9.3.1冒泡排序設(shè)待排序的表有10個元素，其關(guān)鍵字分別為{9，8，7，6，5，4，3，2，1，0}。說明采用冒泡排序方法進行排序的過程。9.3.1冒泡排序【算法9.4】設(shè)計1個算法，對R[0..n-1]按遞增有序進行冒泡排序。思路：見前面的冒泡排序算法思路。代碼見算法9.49.3.2快速排序在排序表中取第1個元素作為基準。將基準歸位到最終位置，即1次劃分：所有小于基準的元素放在基準左邊（構(gòu)成左子表），所有大于基準的元素放在右邊（構(gòu)成右子表）。對左右子表重復(fù)（1）、（2），直到每個子表只有1個元素或空為止。9.3.2快速排序設(shè)待排序的表有10個元素，其關(guān)鍵字分別為（6，8，7，9，0，1，3，2，4，5）。說明采用快速排序方法進行排序的過程。第1趟結(jié)果：5432016978 第2趟結(jié)果：1423056879第3趟結(jié)果：0123456789第4趟結(jié)果：0123456789第5趟結(jié)果：0123456789遞歸樹的高度決定了快速排序的趟數(shù)9.3.2快速排序【算法9.5】設(shè)計1個算法，對R[0..n-1]按遞增有序進行快速排序。思路：見前面的快速排序算法思路。代碼見算法9.59.4選擇排序選擇排序的基本思想是初始有序區(qū)為空，每1趟排序從無序區(qū)中選出最小/最大的元素放在有序區(qū)最后，從而擴大有序區(qū)直到無序區(qū)為空。選擇排序主要有簡單選擇排序和堆排序。9.4.1簡單選擇排序9.4.1簡單選擇排序設(shè)待排序的表有10個元素，其關(guān)鍵字分別為（6，8，7，9，0，1，3，2，4，5）。說明采用簡單選擇排序方法進行排序的過程。9.4.1簡單選擇排序【算法9.6】設(shè)計1個算法，對R[0..n-1]按遞增有序進行簡單選擇排序。思路：見前面的簡單選擇排序算法思路。代碼見算法9.69.4.2堆排序堆排序是用二叉樹來選出最小/最大元素，是1種樹形選擇排序方法。堆的定義：1個序列R[1..n]，關(guān)鍵字分別為k1、k2...kn，將關(guān)鍵字序列按層次遍歷構(gòu)造為1棵完全二叉樹，如圖9.10所示。若ki≤k2i且ki≤k2i+1，則稱其為小根堆；若ki≥k2i

且ki≥k2i+1，則稱其為大根堆，其中1≤i≤n/2。9.4.2堆排序設(shè)待排序的表有10個記錄，其關(guān)鍵字分別為{6，8，7，9，0，1，3，2，4，5}。說明采用堆排序方法進行排序的過程。9.4.2堆排序

9.5歸并排序歸并排序的基本思路是將2個或2個以上的相鄰有序子表合并為1個有序表，經(jīng)過多趟排序而完成整個序列有序。根據(jù)歸并路數(shù)分為2路歸并、3路歸并、多路歸并。9.5歸并排序設(shè)排序序列有10個元素，其關(guān)鍵字分別為（18，2，20，34，12，32，6，16，1，15）。說明采用自頂向下2路歸并排序方法進行排序的過程。9.5歸并排序【算法9.8】設(shè)計1個算法，對R[0..n-1]按遞增進行二路歸并排序。思路：見前面的2路歸并排序算法思路。代碼見算法9.89.6分配排序分配排序的基本思想是不比較關(guān)鍵字大小，根據(jù)關(guān)鍵字各位上的值，進行若干趟“分配”和“收集”而完成排序。舉例：4個同學(xué)，2男2女。按照性別和高矮排序，要求女同學(xué)先出列，個子矮的先出列。如圖9.15所示，從右到左是出列順序。在這個例子中，可將關(guān)鍵看作2位組成的，1位是性別，1位是高矮。9.6.1桶排序桶排序?qū)⒋判蛐蛄袆澐殖扇舾蓚€區(qū)間，每個區(qū)間可形象地看作一個桶，如果桶中的記錄多于一個則使用較快的排序方法進行排序，把每個桶中的記錄依次收集起來，得到有序序列。9.6.1桶排序有10個學(xué)生的成績（68,75,54,70,83,48,80,12,75,92），對該成績序列進行桶排序。學(xué)生成績在0～100，可以劃分為10個桶，即0～9，10～19，20～39，…，90～100。將學(xué)生成績依次放入桶中；對桶內(nèi)數(shù)據(jù)進行排序；依次收集桶中數(shù)據(jù)得有序序列（12，48，54，68，70，75，75，80，83，92）。9.6.1桶排序【算法9.9】設(shè)計1個算法，對R[0..n-1]按遞增有序進行桶排序。思路：（1）按照數(shù)值區(qū)間劃分桶，即初始化桶。（2）遍歷無序表，根據(jù)元素值將其分配到對應(yīng)桶中。（3）對每個桶中的元素進行排序。（4）收集每個桶中的元素，并將其輸出為有序序列。代碼見算法9.99.6.2基數(shù)排序基數(shù)排序是桶排序的擴展，它是1種多關(guān)鍵字排序算法。舉例：撲克牌排序，撲克牌由數(shù)字和花色2個關(guān)鍵字組成。假設(shè)先按花色（?,?,?,?）順序排序，再按面值（2,3,…,10,J,Q,K,A）順序排序，則排序結(jié)果為2?，...，A?，2?，...，A?，2?，...，A?，2?，...，A?。假設(shè)2個關(guān)鍵字排序優(yōu)先級交換，則排序結(jié)果為2?，2?，2?，2?，...，3?，3?，3?，3?，...，A?，A?，A?，A?。9.6.2基數(shù)排序設(shè)待排序表有8個元素，其序列為(369，367，167，239，237，138，230，139)。說明采用基數(shù)排序方法進行排序的過程。9.6.2基數(shù)排序【算法9.10】設(shè)計1個算法，按照最低位優(yōu)先進行基數(shù)排序。思路：見前面的基數(shù)排序算法思路。代碼見算法9.109.7排序應(yīng)用【例9.1】小藍老師教的編程課有N名學(xué)生，編號依次是1...N。第i號學(xué)生這學(xué)期刷題的數(shù)量是Ai。對于每一名學(xué)生，請你計算他至少還要再刷多少道題，才能使得全班刷題比他多的學(xué)生數(shù)不超過刷題比他少的學(xué)生數(shù)。（藍橋杯競賽真題）思路：（1）先對輸入的數(shù)排序，如升序。（2）找到中間數(shù)（偏大）。（3）用中間數(shù)減比它小的那些數(shù)再加1。（4）輸出中間數(shù)之前的值，和后面的若干個0。代碼見應(yīng)用9.19.7排序應(yīng)用【進一步思考】例9.1算法不采用排序，能否實現(xiàn)？答：可以實現(xiàn)。只不過查找中間數(shù)不如折半查找效率高。9.7排序應(yīng)用【例9.2】設(shè)a[0...n-1]表示n個學(xué)生的分數(shù)，每個分數(shù)在0到100之間，大于等于90為等級A，大于等于80小于90為B，大于等于70小于80為C，大于等于60小于70為D，其他為E。設(shè)計1個算法將