2.3 有序列排序問題

1、有序列插入排序1前面我們學(xué)習(xí)了算法的基本結(jié)構(gòu)，包括順序結(jié)構(gòu)、選擇結(jié)構(gòu)以及循環(huán)結(jié)構(gòu)，以及利用變量和賦值的方式將算法進行優(yōu)化，在這一節(jié)，我們來看看它的實際應(yīng)用。你會使用這些字典嗎？2為了便于查詢和檢索，常常需要根據(jù)要求將被查尋的對象按照一定的順序排列，通常稱為排序，你會從這些書籍中查閱你想要的東西嗎？3新來的同學(xué)小黃升高1.75cm，在班上是中等升高，因為做操的需要，體育老師要將他插到隊中，你認(rèn)為老師應(yīng)該怎樣做？象這樣一種在已經(jīng)按一定順序排好的系列（有系列）中插入，我們就叫它有序列插入排序teacher小黃？4我們在一個已經(jīng)排好循序的一系列數(shù)中插入一個數(shù)據(jù)，成為一個新的系列，且仍按原來的規(guī)則排序。

2、有序列插入排序要將8插入到1,3,5,7,9,11,13中，我們怎樣考慮？確定8在原系列中的位置，使8小于或等于原系列中右邊的數(shù)據(jù)，大于或等于左邊的數(shù)據(jù)將這個位置空出來，將數(shù)據(jù)8插進去85例題分析例1已知有一組系列13,27,38,39,43,47,48,51,57,66,74,82，現(xiàn)要將數(shù)據(jù)52插入到數(shù)據(jù)中。數(shù)據(jù)系列123456789101112原系列號132738394347485157667482(1)請設(shè)計算法，確定52在新數(shù)據(jù)中的位置，并畫出算法示意圖(2)在確定52的序列號后，請將52插入系列中(3)請用流程圖描述這個插入過程的算法61.手工插入： 把原序列中912號的數(shù)據(jù)依次向

3、右挪一位，空出9號位置來，并插入52，得到一個新序列?；蛘撸簝刹酵瑫r進行，即從右邊最后一位開始，與52比較，若比52大就右挪，否則插入52. 確定52的序號：9;為什么要從右便開始？72.流程圖：1引入變量：引入變量i，Ri表示數(shù)據(jù)的位置系列號,則2確定52的位置：從有到左比較系列數(shù)與52的大小，使52在兩個數(shù)之間，位置為9R1=13,R2=27,R12=823插入數(shù)據(jù)，位置9以后的數(shù)據(jù)后移一位，在9位置插入5283.流程圖1.設(shè)置變量（數(shù)組）:Rj2循環(huán)變量和初始條件 系列號，初始條件為jn3循環(huán)體：Rj+1:=Rj4終止條件：1ARj2AR1你會畫出它的流程圖嗎？9但是，對于我們統(tǒng)計收集的數(shù)據(jù)，很多都是雜亂無章的，如何完成這些數(shù)據(jù)的排序呢？基本思想很簡單，就是反復(fù)使用有序列排序插入算法，使有序列的長度不但增加，一直到完成整個無系列的有序化。10反復(fù)使用有序列插入排序算法，即首先把第一個數(shù)當(dāng)作一個有序列，插入第二個數(shù)變成有兩個數(shù)據(jù)的有序列，再插入第三個數(shù)，依此類推，就完成了整個無序列的有序化。流程圖如下：這樣一種排序的方法我們就叫它無序列的直接插入排序