《數(shù)據(jù)結(jié)構(gòu)與算法項目化教程》課件第7章

學(xué)習(xí)情境7排序7.1任務(wù)一認(rèn)識排序7.2任務(wù)二插入排序7.3任務(wù)三交換排序7.4任務(wù)四選擇排序7.5任務(wù)五歸并排序——兩路歸并排序7.6任務(wù)六基數(shù)排序排序(sorting)是對數(shù)據(jù)結(jié)構(gòu)序列中的數(shù)據(jù)按照指定關(guān)鍵字從小到大或從大到小的次序排列。排序是日常工作和軟件設(shè)計中最常用的運(yùn)算之一，排序可以提高查找效率。排序算法有多種，本學(xué)習(xí)情境主要介紹插入排序、交換排序、選擇排序和歸并排序等算法。每種算法都有自己的特點(diǎn)和巧妙之處，通過本學(xué)習(xí)情境可以掌握排序設(shè)計思想和程序設(shè)計。7.1任務(wù)一認(rèn)識排序7.1.1子任務(wù)1學(xué)習(xí)排序基礎(chǔ)知識

1．排序?qū)σ粋€數(shù)據(jù)表來說，不同的要求可能會選擇不同的字段作為其關(guān)鍵字，如在檔案表中，編號、姓名、職務(wù)、職稱，年齡等均可作為關(guān)鍵字來排序。

2．排序分類排序的要求和方法較多，對此有不同的分類方法。

(1)增排序和減排序。如果排序的結(jié)果是按關(guān)鍵字從小到大的次序排列的，就是增排序，否則就是減排序。

(2)內(nèi)部排序和外部排序。如果在排序過程中，數(shù)據(jù)表中的所有數(shù)據(jù)均在內(nèi)存中，則稱這類排序為內(nèi)部排序，否則為外部排序。程序設(shè)計語言中的排序大多是在數(shù)組中進(jìn)行的，而數(shù)組本身就是內(nèi)存的一部分，所以這種排序就是內(nèi)部排序。在某些場合下，數(shù)據(jù)表中的內(nèi)容可能較多，超出數(shù)組的內(nèi)存容量，在這種情況下，排序過程中就需要將部分?jǐn)?shù)據(jù)存放在外部存儲器中，另一部分?jǐn)?shù)據(jù)放在內(nèi)存中排序。這一過程需要反復(fù)進(jìn)行，直到排出全部次序為止。這一類排序就是外部排序。本教程主要學(xué)習(xí)內(nèi)部排序。

(3)穩(wěn)定排序和不穩(wěn)定排序。在排序過程中，如果關(guān)鍵字相同的多個不同數(shù)據(jù)在排序前后的次序不變，則稱為穩(wěn)定排序，否則是不穩(wěn)定排序。

3．常見排序算法排序算法有多種，按照各算法所采用的基本方法可將其劃分為：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序。7.1.2子任務(wù)2排序算法的指標(biāo)分析對各種排序算法性能的評價主要在于時間性能和空間性能方面，對某些算法還可能要涉及其他一些相關(guān)性能的分析。

1．時間性能分析在分析排序算法的時間性能時，主要以算法中用得最多的基本操作的執(zhí)行次數(shù)(或者其數(shù)量級)來衡量，這些操作主要是比較數(shù)據(jù)、移動或交換數(shù)據(jù)。在一些情況下，可能還要用這些操作次數(shù)的平均數(shù)來表示。

2．空間性能分析排序算法的實間性能主要是指在排序過程中所占用的輔助空間的情況，既是用來臨時存儲數(shù)據(jù)的內(nèi)存，在某些情況下還可能是用于程序運(yùn)行所需要的輔助空間。7.1.3子任務(wù)3程序算法的程序?qū)崿F(xiàn)基礎(chǔ)為了在學(xué)習(xí)后續(xù)每一種算法時能馬上實現(xiàn)程序運(yùn)行，本子任務(wù)先構(gòu)建主程序菜單和排序數(shù)產(chǎn)生方式等。

1．創(chuàng)建主程序

(1)創(chuàng)建排序的包，包名為ch7Sort。

(2)在包c(diǎn)h7Sort中創(chuàng)建排序主程序，命名為SortMain.java。①為了方便操作，可以由系統(tǒng)自動產(chǎn)生n位隨機(jī)數(shù)，也可以由操作者輸入排序數(shù)據(jù)，所以創(chuàng)建select()方法。②創(chuàng)建菜單操作項，菜單排序形式如下：③在main()中調(diào)用菜單排序程序SortMain.Menu()。④主程序SortMain.java的完整代碼如下：

packagech7Sort;

importjava.util.Scanner;

publicclassSortMain{

//選擇輸入待排序數(shù)字的方式

publicstaticintselect(){

Scannerscan=newScanner(System.in);

intinput;

System.out.println("輸入待排序數(shù)字的方式");

System.out.println("\n1-機(jī)選2-自己輸入");

System.out.println("(輸入其他數(shù)字鍵系統(tǒng)默認(rèn)為2)\n");System.out.print("請選擇：");input=scan.nextInt();if(input==1){return1;}else{return2;}}

publicstaticvoidMenu(){do{try{System.out.println("\n");System.out.print("\n<<<<<<<<<<排序算法菜單>>>>>>>>>\n");System.out.println("1--插入排序1：直接插入排序");System.out.println("2--插入排序2：希爾排序");System.out.println("3--交換排序1：冒泡排序");System.out.println("4--交換排序2：快速排序");System.out.println("5--選擇排序1：直接選擇排序");System.out.println("6--選擇排序2：堆排序");System.out.println("7--歸并排序：二路歸并排序");System.out.println("8--基數(shù)排序：三位基數(shù)排序");System.out.println("0退出");System.out.print("<<<<<<<<<<<<<>>>>>>>>>>>>");System.out.print("\n請根據(jù)菜單項選擇:");Scannersc=newScanner(System.in);intinputNum=sc.nextInt();System.out.println();switch(inputNum){case1:if(select()==1){System.out.print("請輸入您要隨機(jī)產(chǎn)生數(shù)字的個數(shù)");intinsertSize=sc.nextInt();Sort.insertSort(Sort.random(insertSize));}else{System.out.print("請輸入您要排序的數(shù)字個數(shù)：");intinsertSize=sc.nextInt();Sort.insertSort(Sort.input(insertSize));}break;case2:if(select()==1){System.out.print("請輸入您要隨機(jī)產(chǎn)生數(shù)字的個數(shù)：");intshellSize=sc.nextInt();Sort.shellSort((Sort.random(shellSize)));}else{System.out.print("請輸入您要排序的數(shù)字個數(shù)：");intshellSize=sc.nextInt();Sort.shellSort((Sort.input(shellSize)));}break;case3:if(select()==1){System.out.print("請輸入您要隨機(jī)產(chǎn)生數(shù)字的個數(shù)");intbbeSize=sc.nextInt();Sort.bubbleSort(Sort.random(bbeSize));}else{System.out.print("請輸入您要排序的數(shù)字個數(shù)：");intbbeSize=sc.nextInt();Sort.bubbleSort(Sort.input(bbeSize));}break;case4:if(select()==1){System.out.print("請輸入您要隨機(jī)產(chǎn)生數(shù)字的個數(shù)");intquickSize=sc.nextInt();Sort.quickSort(Sort.random(quickSize));}else{System.out.print("請輸入您要排序的數(shù)字個數(shù)：");intquickSize=sc.nextInt();Sort.quickSort(Sort.input(quickSize));}break;case5:if(select()==1){System.out.print("請輸入您要隨機(jī)產(chǎn)生數(shù)字的個數(shù)");intselSize=sc.nextInt();

Sort.selectSort(Sort.random(selSize));}else{System.out.print("請輸入您要排序的數(shù)字個數(shù)：");intselSize=sc.nextInt();Sort.selectSort(Sort.input(selSize));}break;

case6:if(select()==1){System.out.print("請輸入您要隨機(jī)產(chǎn)生數(shù)字的個數(shù)");intheaSize=sc.nextInt();Sort.mergeSort(Sort.random(heaSize));}else{System.out.print("請輸入您要排序的數(shù)字個數(shù)：");intheaSize=sc.nextInt();Sort.mergeSort(Sort.input(heaSize));}break;

case7:if(select()==1){System.out.print("請輸入您要隨機(jī)產(chǎn)生數(shù)字的個數(shù)");intshellSize=sc.nextInt();Sort.shellSort((Sort.random(shellSize)));}else{System.out.print("請輸入您要排序的數(shù)字個數(shù)：");intshellSize=sc.nextInt();Sort.shellSort((Sort.input(shellSize)));}break;

case8:if(select()==1){System.out.print("請輸入您要隨機(jī)產(chǎn)生數(shù)字的個數(shù)");intbaseSize=sc.nextInt();Sort.base(Sort.random(baseSize));}else{System.out.print("請輸入您要排序的數(shù)字個數(shù)：");intbaseSize=sc.nextInt();

Sort.base(Sort.input(baseSize));}break;case0:System.out.println("\n歡迎下次再使用！");System.exit(0);default:System.out.println("您的輸入有誤，請輸入0-8\n");}}catch(Exceptione){System.out.println("\n您的輸入有誤，請輸入數(shù)字！");}}while(true);}publicstaticvoidmain(String[]args){SortMain.Menu();}}

2．創(chuàng)建排序類在包c(diǎn)h7Sort中創(chuàng)建排序Sort.java類，步驟如下：

(1)構(gòu)造產(chǎn)生n個隨機(jī)數(shù)的random(intn)方法。

(2)構(gòu)造輸入要排序數(shù)字的input(intn)方法。

(3)構(gòu)造輸出數(shù)組元素的printList(int[]list)方法。

(4)?Sort.java中三個操作方法的完整代碼如下(注意，Sort.java的所有代碼在后續(xù)的各排序任務(wù)中逐步添加)：

packagech7Sort;

importjava.util.Scanner;

publicclassSort{

//產(chǎn)生n個隨機(jī)數(shù)，返回整型數(shù)組

publicstaticint[]random(intn){if(n>0){intlist[]=newint[n];

for(inti=0;i<list.length;i++){

//產(chǎn)生一個0～100之間的隨機(jī)數(shù)

list[i]=(int)(Math.random()*100);}returnlist;//返回待排序隨機(jī)數(shù)組

}returnnull;}//輸入要排序的數(shù)字

publicstaticint[]input(intn){Scannerscan=newScanner(System.in);int[]input=newint[n];System.out.print("請輸入要排序的數(shù)：");for(inti=0;i<input.length;i++){input[i]=scan.nextInt();}returninput;}//輸出數(shù)組元素

publicstaticvoidprintList(int[]list){if(list!=null){for(inti=0;i<list.length;i++){System.out.print(""+list[i]);}}System.out.println();}}7.2任務(wù)二插入排序插入排序(insertionsort)的基本思想是：將待排序表看做是左、右兩部分，其中左邊為有序區(qū)，右邊為無序區(qū)，每趟排序?qū)⒂也恳粋€數(shù)據(jù)，按其關(guān)鍵字大小，插入到它左部已排序的子序列中，使得插入后的子序列仍是排序的，依次重復(fù)直到全部數(shù)據(jù)插入完畢。插入排序算法有三種：直接插入排序、折半插入排序、希爾排序。本任務(wù)主要學(xué)習(xí)直接插入排序和希爾排序。7.2.1子任務(wù)1直接插入排序

1．直接插入排序算法

(1)第i(1≤i<n)趟，數(shù)據(jù)序列為{a0,a1,…,ai-1,ai,…,an-1}，當(dāng)前i個數(shù)據(jù)構(gòu)成的子序列{a0,a1,…,ai-1}是排序的，將數(shù)據(jù)插入到子序列{a0,a1,…,ai-1}的適當(dāng)位置，使插入后的子序列仍然是排序的，ai的插入位置由關(guān)鍵字比較決定。

(2)重復(fù)上述操作，n個數(shù)據(jù)共需n-1趟掃描，每趟將一個數(shù)據(jù)插入到它前面的子序列中。

2．直接插入排序?qū)嵗僭O(shè)要排序的數(shù)字是：678930737935372537直接排序操作過程如下：第1趟:6789||30737935372537第2趟:306789||737935372537第3趟:30677389||7935372537第4趟:3067737989||35372537第5趟:303567737989||372537第6趟:30353767737989||2537第7趟:2530353767737989||37第8趟:253035373767737989||排序后的結(jié)果是：2530353737677379893．算法分析

(1)穩(wěn)定性：由于算法在搜索插入位置的過程中遇到相等的數(shù)據(jù)時就停止，因而該算法為穩(wěn)定的排序算法。

(2)空間性能：該算法僅需要一個記錄的輔助存儲空間，直接插入排序的空間復(fù)雜度為O(1)。

(3)時間性能：設(shè)數(shù)據(jù)序列有n個數(shù)據(jù)，直接插入排序算法執(zhí)行n-1趟，每趟的比較次數(shù)和移動次數(shù)與數(shù)據(jù)序列的初始化排列有關(guān)。以下分最好、最壞和隨機(jī)三種情況分析直接插入排序算法的時間復(fù)雜度。①數(shù)據(jù)序列已排序(最好情況)的時間復(fù)雜O(n)。若一個數(shù)據(jù)序列已排序，每一趟數(shù)據(jù)ai與ai-1比較1次，移動次數(shù)為2(list[i]到temp再返回)，則總比較次數(shù)為n-1，總移動次數(shù)為2(n-1)。因此，直接插入排序算法在最好情況下的時間復(fù)雜度為O(n)。②數(shù)據(jù)序列反排列(最壞情況)的時間復(fù)雜度為O(n2)。若一個數(shù)據(jù)序列已排列，則第i趟插入數(shù)據(jù)ai的比較次數(shù)為i，移動次數(shù)為i+2?？偙容^次數(shù)C和移動次數(shù)M分別為因此，直接插入排序算法在最壞情況下的時間復(fù)雜度為O(n2)。③數(shù)據(jù)序列隨機(jī)排列的時間復(fù)雜度為O(n2)。若一個數(shù)據(jù)序列隨機(jī)排列，第i趟插入數(shù)據(jù)ai，則在等概念情況下，在前i個數(shù)據(jù)組成的子序列{a0,a1,…,ai-1}中，查找一個數(shù)據(jù)的平均比較次數(shù)為(i+1)/2，插入一個數(shù)據(jù)的平均移動次數(shù)為i/2。直接插入排序的比較次數(shù)C和移動次數(shù)M分別為因此，直接插入排序的時間復(fù)雜度為O(n2)?？傊?，數(shù)據(jù)序列的初始排列越接近有序，直接插入排序的時間效率越高，其時間效率在O(n)到O(n2)之間。

4．直接插入排序程序?qū)崿F(xiàn)在Sort.java類中增加直接插入排序的算法程序代碼，并在主程序中調(diào)用，直接插入排序算法完整代碼如下：

//直接插入排序

publicstaticvoidinsertSort(int[]list){

//數(shù)組是引用類型，元素值將被改變

System.out.print("您要排序的數(shù)字是：");

printList(list);

System.out.println("\n直接插入排序\n");

for(inti=1;i<list.length;i++)//n-1趟掃描

{//每趟將list[i]插入到前面已排序的序列中

inttemp=list[i],j;//將前面較大元素向后移動

for(j=i-1;j>-1&&temp<list[j];j--){list[j+1]=list[j];}//temp值到達(dá)插入位置

list[j+1]=temp;System.out.print("第"+i+"趟:");printList(list);}System.out.print("\n排序后的結(jié)果是：");printList(list);}7.2.2子任務(wù)2希爾排序希爾排序(shellsort)是D.L.Shell在1959年提出的，又稱縮小增量排序(diminishingincrementsort)，基本思想是分組的直接插入排序。

1．希爾排序直接插入排序算法的時間性能取決于數(shù)據(jù)的初始特性。一般情況下，時間復(fù)雜度為O(n2)，但是當(dāng)序列為正序或基本有序(即表中逆序的數(shù)據(jù)較少，或者說表中每個數(shù)據(jù)距離其最終位置的差距不大)時，時間復(fù)雜度為O(n)。因此，若能在此之前將排序序列調(diào)整為基本有序，則排序的效率會大大提高。另一方面，如果數(shù)據(jù)個數(shù)較少，則直接插入排序的效率也較高。希爾排序正是基于這樣的考慮。

2．基本思想希爾排序的基本思想是：將待排序列劃分為若干組，在每組內(nèi)進(jìn)行直接插入排序，以使整個序列基本有序，然后再對整個序列進(jìn)行直接插入排序。這種排序的關(guān)鍵是如何分組，如果簡單地逐段分割，則難以達(dá)到基本有序的目地。為此采用間隔方法分組，分組方法為：對給定的一個步長delta(delta>0)，將下標(biāo)相差為delta的倍數(shù)的數(shù)據(jù)分在一組，這樣共得到d組。

delta取什么值？事實上，delta的取值有多個，并且組成一個序列，典型的取值依次為d1?=?n/2，d2?=?d1/2,…,dk?=?1，這樣，隨著步長di的逐漸縮小，每組規(guī)模不斷擴(kuò)大。當(dāng)步長取值為1時，整個序列在一組內(nèi)執(zhí)行直接插入排序，這是希爾排序所必需的。通過前面若干趟的初步排序，使得此時的序列基本有序，因而只需較少的比較和移動次數(shù)。

3．希爾排序算法

(1)將一個數(shù)據(jù)序列分成若干組，每組由若干相隔一段距離的數(shù)據(jù)組成，這段距離稱為增量delta(增量的初始值為數(shù)據(jù)序列長度的一半)，在一個組內(nèi)采用直接插入排序算法進(jìn)行排序。

(2)以后每趟增量delta逐漸縮半，最后值為1，隨著增量逐漸減小，組數(shù)也減小，組內(nèi)元數(shù)個數(shù)增加，整個序列則接近有序。當(dāng)增量為1時，只有一組的數(shù)據(jù)是整個序列，再進(jìn)行一次直接插入排序即可。

4．希爾排序?qū)嵗僭O(shè)要排序的數(shù)是：51381086858065652573244985920希爾排序操作過程如下：

delta=720251024498595138738685806565

delta=320258244910595138736565808685

delta=181020242538495159656573808586排序后的結(jié)果是：81020242538495159656573808586

5．算法分析

(1)希爾排序時間性能的分析是一個復(fù)雜的問題?？紤]到每一趟都是在上一趟的基礎(chǔ)上進(jìn)行的，故可認(rèn)為是基本有序，因而各趟的時間復(fù)雜度為O(n)。由于按每次取上一個步長的一半的方式進(jìn)行，故需要的趟數(shù)為lbn，由此可知，整個排序算法的時間復(fù)雜度為O(n?×?lb?n)。

(2)該算法顯然是不穩(wěn)定的。

6．希爾排序程序?qū)崿F(xiàn)在Sort.java類中增加希爾排序的算法程序代碼，并在主程序中調(diào)用，希爾排序算法的完整代碼如下：

//希爾排序

publicstaticvoidshellSort(int[]list){

System.out.print("您要排序的數(shù)字是：");

printList(list);

System.out.println("\n希爾排序\n");

//控制增量，增量減半，若干趟掃描

for(intdelta=list.length/2;delta>0;delta/=2){

//一趟中若干組，每個元素在自己所屬組內(nèi)進(jìn)行直接插入排序

for(inti=delta;i<list.length;i++){

inttemp=list[i]; //當(dāng)前待插入元素

intj=i-delta; //相距delta遠(yuǎn)

//一組中前面較大的元素向后移動

while(j>=0&&temp<list[j]){list[j+delta]=list[j];j-=delta; //繼續(xù)與前面的元素比較

}

list[j+delta]=temp; //插入元素位置

}System.out.print("delta="+delta+"");

printList(list);}System.out.print("\n排序后的結(jié)果是：");printList(list);}7.3任務(wù)三交換排序交換排序的基本思想是：兩兩比較待排序列的數(shù)據(jù)，發(fā)現(xiàn)倒序即交換?；谶@種思想，有兩種排序：冒泡排序和快速排序。7.3.1子任務(wù)1冒泡排序

1．冒泡排序冒泡排序(bubblesort)的基本思想是：從一端開始，逐個比較相鄰的兩個數(shù)據(jù)，發(fā)現(xiàn)倒序即交換。典型的做法是從后往前或從下往上逐個比較相鄰數(shù)據(jù)，發(fā)現(xiàn)倒序即進(jìn)行交換。這樣一遍下來，一定能將其中最大(或最小)的數(shù)據(jù)交換到其最終位置上。如果約定為最上面，就像水中的氣泡那樣冒到水面上，故此得名。由于一趟只能使一個“氣泡”到位，因此必須對余下數(shù)據(jù)重復(fù)上述過程，即要重復(fù)n-1次冒泡操作。

2．冒泡排序操作實例排序的數(shù)字是：9272977457901650冒泡排序操作過程(大數(shù)沉底)如下：第1趟:72927457901650||97第2趟:727457901650||9297第3趟:7257741650||909297第4趟:57721650||74909297第5趟:571650||7274909297第6趟:1650||577274909297第7趟:16||50577274909297排序后的結(jié)果是：16505772749092973．冒泡排序算法分析

(1)時間復(fù)雜度。一般情況下，冒泡排序的時間復(fù)雜度為O(n2)。最好情況是數(shù)據(jù)的初始序列已排序，只需一趟掃描，比較次數(shù)為n，沒有數(shù)據(jù)移動，時間復(fù)雜度是O(n)。最壞情況是數(shù)據(jù)反序排列，需要n-1趟掃描，比較次數(shù)和移動次數(shù)都是O(n2)，時間復(fù)雜度是O(n2)?？傊?，數(shù)據(jù)序列的初始排列越接近有序，冒泡排序的時間效率越高，其時間效率在O(n)到O(n2)之間。

(2)冒泡排序需要一個輔助空間用于交換兩個數(shù)據(jù)，空間復(fù)雜度為O(1)。

(3)冒泡排序算法是穩(wěn)定的。

4．冒泡排序程序?qū)崿F(xiàn)在Sort.java類中增加冒泡排序的算法及交換算法swap()程序代碼，并在主程序中調(diào)用，冒泡排序算法的完整代碼如下：

//交換數(shù)組中下標(biāo)為i、j的元素

publicstaticvoidswap(int[]list,inti,intj){

//判斷i、j是否越界

if(i>=0&&i<list.length&&j>=0&&j<list.length&&i!=j){

inttemp=list[j];

list[j]=list[i];

list[i]=temp;

}

}//冒泡排序

publicstaticvoidbubbleSort(int[]list){System.out.print("您要排序的數(shù)字是：");printList(list);System.out.println("\n冒泡排序\n");booleanexchange=true; //是否交換的標(biāo)記

//有交換時再進(jìn)行下一趟，最多n-1趟

for(inti=1;i<list.length&&exchange;i++){exchange=false; //假定元素未交換

//一次比較、交換

for(intj=0;j<list.length-i;j++){if(list[j]>list[j+1]){ //反序時，交換

inttemp=list[j];list[j]=list[j+1];list[j+1]=temp;exchange=true; //有交換

}}System.out.print("第"+i+"趟:");printList(list);}System.out.print("\n排序后的結(jié)果是：");printList(list);}7.3.2子任務(wù)2快速排序由于冒泡排序算法中是以相鄰數(shù)據(jù)來比較和交換的，因此，若一個數(shù)據(jù)離其最終位置較遠(yuǎn)，則需要執(zhí)行較多次數(shù)的比較和移動操作。是否可以改變一下比較的方式，以使比較和移動操作更少一些？快速排序算法即是對冒泡排序算法的改進(jìn)。

1．快速排序的基本思想快速排序是一種分區(qū)交換排序算法，具體表現(xiàn)如下：

(1)選定一個數(shù)據(jù)作為中間數(shù)據(jù)，然后將表中所有數(shù)據(jù)與該中間數(shù)據(jù)相比較，將表中比中間數(shù)據(jù)小的數(shù)據(jù)調(diào)到表的前面，將比中間數(shù)據(jù)大的數(shù)據(jù)調(diào)到后面，再將中間數(shù)據(jù)放在這兩部分之間作為分界點(diǎn)，這樣便得到一個劃分。

(2)對左、右兩部分分別進(jìn)行快速排序，即對所有得到的兩個子表再采用相同的方式來劃分和排序，直到每個子表僅有一個數(shù)據(jù)或為空表為止。此時便得到一個有序表?？焖倥判蛩惴ㄍㄟ^一趟排序操作將待排序序列劃分成左、右兩部分，使得左邊任一數(shù)據(jù)不大于右邊任一數(shù)據(jù)，然后再分別對左、右兩部分分別進(jìn)行(同樣的)排序，直至整個數(shù)據(jù)表有序為止。由此可見，對數(shù)據(jù)表進(jìn)行劃分是快速排序算法的關(guān)鍵。

2．快速排序劃分實現(xiàn)為實現(xiàn)劃分，首先需要解決“中間數(shù)”的選擇：作為參考點(diǎn)的中間數(shù)的選擇沒有特別的規(guī)定，可有多種選擇方法，如選擇第一個數(shù)據(jù)，中間的某個數(shù)據(jù)或其他形式等。較典型的方法是選第一個數(shù)據(jù)。

(1)選取第一個數(shù)據(jù)作為基準(zhǔn)值，空出第一個數(shù)據(jù)位置；i、j分別是數(shù)據(jù)序列前后兩端數(shù)據(jù)的下標(biāo)，將j位置數(shù)據(jù)與基準(zhǔn)值比較，若小則移動到序列前端下標(biāo)為i的空位置，i++，此時j位置空出。

(2)將i位置數(shù)據(jù)與基準(zhǔn)值比較，若大則移動到序列后端的j空位置，j--。

(3)重復(fù)(2)，直到i==j，數(shù)據(jù)序列中的每個數(shù)據(jù)都與基準(zhǔn)值比較過了，并已將小于基準(zhǔn)值的數(shù)據(jù)移動到前端，將大于基準(zhǔn)值的數(shù)據(jù)移動到后端，當(dāng)前i(j)?位置則是基準(zhǔn)值的最終位置。

3．快速排序操作實例需要排序的數(shù)是：80299194041快速排序過程如下(序列的下界..序列的上界，vot是基準(zhǔn)值)：

0..5,vot=8041240198099

0..3,vot=4119240418099

0..2,vot=1921940418099快速排序的結(jié)果是：21940418099

4．快速排序算法分析

(1)時間復(fù)雜度：一趟劃分算法的時間復(fù)雜度為O(n)，因此，要分析整個快速排序算法的時間復(fù)雜度，就要分析其劃分的趟數(shù)。這可能有多種情況：①理想情況下，每次所選的中間數(shù)據(jù)正好能將子表幾乎等分為兩部分，為便于分析，認(rèn)為是等分。這樣，經(jīng)過lb?n趟劃分便可使所劃分的各子表的長度為1。由于一趟劃分所需的時間與數(shù)據(jù)個數(shù)成正比，因而可認(rèn)為是c?×?n(c為某常數(shù))。所以整個算法的時間復(fù)雜度為O(n?×?lb?n)。②極端壞情況是：每次所選的中間數(shù)據(jù)為其中最大或最小的數(shù)據(jù)，這將使每次劃分所得的兩個子表中的一個變?yōu)榭毡?，另一子表的長度為原長度-1，因為需要進(jìn)行n-1趟劃分,而每趟劃分中需掃描的數(shù)據(jù)個數(shù)為n-i+1(i為趟數(shù))，因而整個算法的時間復(fù)雜度為O(n2)。③一般情況下，從統(tǒng)計意義上說，選擇的中間數(shù)據(jù)是最大或最小的概率較小，因而可以認(rèn)為快速排序算法的平均時間復(fù)雜度O(k?×?n?×?lb?n)，其中k為某常數(shù)。經(jīng)驗明，在所有同量級的此類排序方法中，快速排序算法的常數(shù)因子K最小。因此，從平均時間性能來說，快速排序目前被認(rèn)為是最好的一種內(nèi)部排序方法。

(2)空間復(fù)雜度：快速排序算法在遞歸調(diào)用過程中需要使用棧保存參數(shù)，棧所占用的空間與遞歸調(diào)用的次數(shù)有關(guān)，最好情況下空間復(fù)雜度為O(lb?n)；最壞情況下空間復(fù)雜度為O(n)；平均空間復(fù)雜度為O(lb?n)。

(3)穩(wěn)定性：快速排序算法顯然是不穩(wěn)定排序。

5．快速排序程序?qū)崿F(xiàn)在Sort.java類中增加快速排序的算法程序代碼，并在主程序中調(diào)用，快速排序算法的完整代碼如下：//快速排序

publicstaticvoidquickSort(int[]list){System.out.print("您要排序的數(shù)字是：");printList(list);System.out.println("\n快速排序\n");quickSort(list,0,list.length-1);}//一趟快速排序，遞歸算法

privatestaticvoidquickSort(int[]list,intlow,inthigh){//low、high指定序列的下界和上界

if(low<high){ //序列有效

inti=low,j=high;

intvot=list[i]; //第一個值作為基準(zhǔn)值

while(i!=j){ //一趟排序

while(i<j&&vot<=list[j]){ //從后向前尋找較小值

j--;}if(i<j){list[i]=list[j]; //較小元素向前移動

i++;}while(i<j&&list[i]<vot){ //從前向后尋找較大值

i++;}

if(i<j){list[j]=list[i]; //較大元素向后移動

j--;}}list[i]=vot; //基準(zhǔn)值的最終位置

System.out.print(low+".."+high+",vot="+vot+"");printList(list);quickSort(list,low,j-1); //前端子序列再排序

quickSort(list,i+1,high); //后端子序列再排序

}}7.4任務(wù)四選擇排序選擇排序的基本思想是：在每一趟排序中，在待排序子序列中選出關(guān)鍵字最小或最大的數(shù)據(jù)放在其最終位置上?；谶@一思想的排序方法有多種，本任務(wù)介紹其中兩種選擇典型排序方法，即直接選擇排序和堆排序。7.4.1子任務(wù)1直接選擇排序直接選擇排序算法采用的方法較直觀：通過在待排序子序列中選擇最大(小)數(shù)據(jù)，并將該數(shù)據(jù)放在子表的最前(后)面。這是選擇排序中最簡單的一種。

1．直接選擇排序算法直接選擇排序(straightselectsort)算法：

(1)第一趟從n個數(shù)據(jù)的數(shù)據(jù)序列中選出關(guān)鍵字最小(或最大)的數(shù)據(jù)并放到最前(或最后)位置。

(2)第i趟再從n-i+1個數(shù)據(jù)中選出最小(大)的數(shù)據(jù)并放到次前(后)位置。

(3)重復(fù)(2)，經(jīng)過n-1趟完成排序。

2．直接選擇排序?qū)嵗僭O(shè)要排序的數(shù)字是：8425715181845314直接選擇排序操作過程如下：第0趟:[14]25715181845384第1趟:[1425]715181845384第2趟:[142551]7181845384第3趟:[14255153]81847184第4趟:[1425515371]848184第5趟:[142551537181]8484第6趟:[14255153718184]84排序后的結(jié)果是：1425515371818484

3．直接選擇排序算法分析

(1)直接選擇排序的比較次數(shù)與數(shù)據(jù)序列的初始排列無關(guān)。第i趟排序的比較次數(shù)是n-i，總比較次數(shù)為移動次數(shù)與數(shù)據(jù)序列的初始排列無關(guān)。當(dāng)數(shù)據(jù)序列已排序時，移動次數(shù)M=0；當(dāng)數(shù)據(jù)序列反序排列時，每一趟排序都要交換，移動次數(shù)M?=?3?×?(n-1)。因此，直接選擇排序的時間復(fù)雜度為O(n2)。

(2)直接選擇排序的空間復(fù)雜度為O(1)。

(3)直接選擇排序算法是不穩(wěn)定的。

4．直接選擇排序程序?qū)崿F(xiàn)在Sort.java類中增加直接選擇排序的算法程序代碼，并在主程序中調(diào)用，直接選擇排序算法的完整代碼如下：

//直接選擇排序

publicstaticvoidselectSort(int[]list){

System.out.print("您要排序的數(shù)字是：");

printList(list);

System.out.println("\n直接選擇排序\n");

for(inti=0;i<list.length-1;i++){ //n-1趟排序

//每趟在從list[i]開始的子序列中尋找最小元素

intmin=i; //設(shè)第i個數(shù)據(jù)元素最小

for(intj=i+1;j<list.length;j++){ //在子序列中查找最小值

if(list[j]<list[min]){

min=j; //記住最小元素下標(biāo)

}}if(min!=i){ //將本趟最小元素交換到前邊

inttemp=list[i];list[i]=list[min];list[min]=temp;}System.out.print("第"+i+"趟:");printList(list);}System.out.print("\n排序后的結(jié)果是：");printList(list);}7.4.2子任務(wù)2堆排序堆排序(heapsort)是完全二叉樹的應(yīng)用，是充分利用完全二叉樹特性的一種選擇排序。

1．什么是堆設(shè)n個數(shù)據(jù)的數(shù)據(jù)序列{k0，k1，…，kn-1}，當(dāng)且僅當(dāng)滿足時，序列{k0，k1，…，kn-1}稱為最小堆?；騥i≥k2i+1

且ki≥k2i+2

時，序列{k0，k1，…，kn-1}稱為最大堆。將最小(大)堆看成是一棵完全二叉樹的層次遍歷序列，則任意一個節(jié)點(diǎn)的關(guān)鍵字值都小于等于(大于等于)它的孩子節(jié)點(diǎn)的關(guān)鍵字值，由此可知，根節(jié)點(diǎn)值最小(大)。最小(大)堆及其完全二叉樹如圖7-1所示。根據(jù)二叉樹的性質(zhì)5，完全二叉樹中的第i(0≤i<n)個節(jié)點(diǎn)如果有孩子，則左孩子為第2i+1個節(jié)點(diǎn)，右孩子為第2i+2個節(jié)點(diǎn)。圖7-1最小(大)堆及其完全二叉樹

2．堆排序算法回顧一下二叉樹的性質(zhì)5：一棵具有n個節(jié)點(diǎn)的完全二叉樹，對序號為i(0<i≤n)的節(jié)點(diǎn)，有若i=1，則i為根節(jié)點(diǎn)，無父母節(jié)點(diǎn)；若i>1，則i的父母節(jié)點(diǎn)序號為int((i-1)/2)；若2i≤n，則i的左孩子節(jié)點(diǎn)序號為2i，否則i無左孩子；若2i+1≤n，則i的右孩子節(jié)點(diǎn)序號為2i+1，否則i無右孩子。可知，一個線性序列中的數(shù)據(jù)與一棵完全二叉樹中的節(jié)點(diǎn)一一對應(yīng)。完全二叉樹要承擔(dān)排序任務(wù)，節(jié)點(diǎn)之間的大小關(guān)系還必須滿足堆序列定義。堆排序算法：

(1)構(gòu)建完全二叉樹，序列中第i個數(shù)據(jù)作為二叉樹的第i個節(jié)點(diǎn)，形成初始堆，如圖7-2(a)所示。

(2)調(diào)整二叉樹成為堆序列，根節(jié)點(diǎn)值是最小(大)值，圖7-2(b)～(e)所示。

(3)每趟將根節(jié)點(diǎn)值(最小/最大)輸出，即交換到二叉樹后面。

(4)將未排序的其余節(jié)點(diǎn)調(diào)整成堆，重復(fù)(2)、(3)，直到排序完成。

3．堆排序過程對序列(9)(3)(18)(4)(17)(13)(5)(16)堆排序的過程如下：

(1)構(gòu)建最小堆(從最后節(jié)點(diǎn)開始往前，小于父節(jié)點(diǎn)的，要與父節(jié)點(diǎn)交換)。堆排序操作過程如下：堆下界:3到上界:7931841713516(見圖7-2(b))堆下界:2到上界:7935417131816(見圖7-2(c))堆下界:1到上界:7935417131816(見圖7-2(d))堆下界:0到上界:7395417131816(見圖7-2(e)，排序第1趟)堆下界:0到上界:6495161713183(排序第2趟)堆下界:0到上界:5591316171843(排序第3趟)堆下界:0到上界:4916131817543(排序第4趟)堆下界:0到上界:3131617189543(排序第5趟)堆下界:0到上界:2161817139543(排序第6趟)堆下界:0到上界:1171816139543(排序第7趟)堆下界:0到上界:0181716139543(排序第8趟)排序后的結(jié)果是：181716139543

(2)輸出根節(jié)點(diǎn)，輸出根節(jié)點(diǎn)(3)，即(16)與(3)交換，如圖7-3(a)所示，形成新的序列(16)(9)(5)(4)(17)(13)(18)；繼續(xù)構(gòu)造最小堆，得到最小堆(4)(9)(5)(16)(17)(13)(18)，如圖7-3(b)所示。圖7-2最小/大堆及其完全二叉樹圖7-3輸出根節(jié)點(diǎn)，繼續(xù)構(gòu)造最小堆

4．堆排序算法分析

(1)時間復(fù)雜度：建立和調(diào)整堆排序的時間復(fù)雜度為O(lb?n)，因為堆排序的時間復(fù)雜度為O(n?×?lb?n)。

(2)空間復(fù)雜度：堆排序的空間復(fù)雜度為1。

(3)堆排序算法是不穩(wěn)定的。

5．堆排序程序?qū)崿F(xiàn)在Sort.java類中增加堆排序的算法程序代碼，并在主程序中調(diào)用，堆排序算法的完整代碼如下：

//將以low為根的子樹調(diào)整成最小堆

privatestaticvoidcreateHeap(int[]list,intlow,inthigh){

//low、high是序列下界和上界

inti=low; //子樹的根

intj=2*i+1; //j為i節(jié)點(diǎn)的左孩子

inttemp=list[i]; //獲得第i個元素的值

while(j<=high){ //沿較小值孩子節(jié)點(diǎn)向下篩選

//數(shù)組元素比較(改成<為最大堆)if(j<high&&list[j]>list[j+1]){j++; //j為左右孩子的較小者

}if(temp>list[j]){ //若父母節(jié)點(diǎn)值較大(改成<為最大堆)list[i]=list[j]; //孩子節(jié)點(diǎn)中的較小值上移

i=j; //i、j向下一層

j=2*i+1;}else{j=high+1;}}list[i]=temp; //當(dāng)前子樹的原根值調(diào)整后的位置

System.out.print("堆下界:"+low+"到上界:"+high+"");printList(list);}//堆排序

publicstaticvoidheapSort(int[]list){System.out.print("您要排序的數(shù)字是：");printList(list);System.out.println("堆排序");intn=list.length;for(intj=n/2-1;j>=0;j--){ //創(chuàng)建最小堆

createHeap(list,j,n-1);}//每趟將最小值交換到后面，再調(diào)整成堆

for(intj=n-1;j>0;j--){

inttemp=list[0];list[0]=list[j];list[j]=temp;createHeap(list,0,j-1);}System.out.print("\n排序后的結(jié)果是：");printList(list);}7.5任務(wù)五歸并排序——兩路歸并排序歸并排序是一種基于歸并方法的排序方法，將兩個已排序的子序列合并，形成一個已排序數(shù)據(jù)序列，又稱兩路歸并排序。7.5.1子任務(wù)1歸并排序

1．歸并歸并是指兩個或者兩個以上的有序表合并成一個新的有序表。設(shè)兩個序列A?=?(a1,a2,a3,…)和B?=?(b1,b2,b3,…)均為非降序列，分別存儲在A、B兩個表中，現(xiàn)在要求將A和B這兩個表合并為一個非降序列C=(C1,C2,C3,C4,…)并存儲在C表中，分析如下：

(1)顯然，C表的第一個數(shù)據(jù)C1是從A或B的第一個數(shù)據(jù)選出來的。

(2)假設(shè)A和B表中各有若干個數(shù)據(jù)被選到C表中，不妨用ia和ib分別指向A和B表中余下數(shù)據(jù)的第一個數(shù)據(jù)，則可能有如下兩種情況：①A[ia]≤B[ib]：說明數(shù)據(jù)A在C表中的位置應(yīng)在B[ib]前，故將其放到C表的表尾，然后再用A[ia]的下一個數(shù)據(jù)與B[ib]比較確定下一個進(jìn)入C表的數(shù)據(jù)。②否則，說明數(shù)據(jù)B[ib]在C表中的位置應(yīng)在A[ia]前，故將其放到C表的表尾，然后再將B[ib]的下一個數(shù)據(jù)與A[ia]比較，以確定下一個進(jìn)入C表的數(shù)據(jù)。

(3)操作(2)的前提是A和B兩個表中都有數(shù)據(jù)，如果有一個表為空，則應(yīng)將另一表中的余下數(shù)據(jù)全部添加到C表的表尾。

2．歸并排序利用歸并的思想進(jìn)行排序：將n個數(shù)據(jù)的表看成是n個有序子表(每個數(shù)據(jù)都是有序的)，每個子表的長度為1，再兩兩歸并，得到n/2個長度為2的有序子表，然后再兩兩歸并，得到n/4個長度為4的有序子表。以此類推，直至得到每一個長度為n的有序表為止。假設(shè)要排序的數(shù)字是：91646462293153813576331歸并排序如下：子序列長度n=1[6491][646][2293][1538][1357][3163]子序列長度n=2[6466491][15223893][13315763]子序列長度n=4[615223846649193][13315763]子序列長度n=8[61315223138465763649193]

3．歸并排序算法分析

(1)時間復(fù)雜度：n個數(shù)據(jù)的歸并排序，每趟比較n-1次，共進(jìn)行l(wèi)b?n趟，因此時間復(fù)雜度為O(n?×?lb?n)。

(2)空間復(fù)雜度：歸并排序需要O(n)容量的附加空間，與數(shù)據(jù)序列的存儲容量相等，空間復(fù)雜度為O(n)。

(3)穩(wěn)定性：歸并排序算法是穩(wěn)定的。7.5.2子任務(wù)2歸并排序的程序?qū)崿F(xiàn)在Sort.java類中增加歸并排序的算法程序代碼，并在主程序中調(diào)用，歸并排序算法的完整代碼如下：

//歸并排序

publicstaticvoidmergeSort(int[]X){

System.out.print("您要排序的數(shù)字是：");

printList(X);

System.out.println("歸并排序");

intn=1;//已排序的子序列長度，初值為1

int[]Y=newint[X.length]; //Y數(shù)組長度同X數(shù)組

do{

mergepass(X,Y,n); //一趟歸并，將X數(shù)組中各子序列歸并到Y(jié)中

printList(Y);

n*=2; //子序列長度加倍

if(n<X.length){mergepass(Y,X,n); //將Y數(shù)組中各子序列再歸并到X中

printList(X);n*=2;}}while(n<X.length);}//一趟歸并

privatestaticvoidmergepass(int[]X,int[]Y,intn){System.out.print("子序列長度n="