chapter3simplesorting中文

1、Data Structures and Algorithms with JavaChapter 3 Simple SortingSimple Sortingv一旦你創(chuàng)建了一個重要的數(shù)據(jù)庫，你可能會想出各種各樣的理由來解決它。你需要安排的名字按字母順序排列的，學(xué)生的年級、郵編客戶，房屋銷售價格，在人口增長，城市，國家的國民生產(chǎn)總值，等等。overviewHow Would You Do It?Bubble Sort氣泡排序Selection Sort選擇排序Insertion Sort插入排序Sorting Objects分類對象Comparing the Simple Sorts比較簡單的種類

2、How Would You Do It?v想象一下你的孩子聯(lián)盟棒球隊(duì)排在了場地上。該條例九名球員，外加一個額外的，已經(jīng)顯示出來的做法。你要安排的球員，以增加高度（在左邊的最短的球員），為球隊(duì)的圖片。vThe three algorithms in this chapter all involve two steps, executed over and over until the data is sorted:v1. Compare two items.v2. Swap two items or copy one item.v這一章中的三種算法都涉及2個步驟，在數(shù)據(jù)被排序時執(zhí)行：v1。比較2

3、項(xiàng)。v2。交換2項(xiàng)或復(fù)制一項(xiàng)。Bubble SortvThe bubble sort is notoriously slow, but its conceptually the simplest of the sorting algorithmsvHere are the rules youre following:1. Compare two players.2. If the one on the left is taller, swap them.3. Move one position right.4. When you reach the first sorted player, s

4、tart over at the left end of the line.APPLETv這種“泡沫排序”是眾所周知的緩慢，但它的概念是最簡單的排序算法以下是你的規(guī)則：v1。比較兩家。v2。如果左邊的一個更高，交換他們。v3。移動一個位置。v4。當(dāng)你到達(dá)第一個排序的球員，開始在結(jié)束的路線。JAVA CODE FOR A BUBBLE SORTBook52INVARIANTSvIn many algorithms there are conditions that remain unchanged as the algorithm proceeds. These conditions are c

5、alled invariants.vIn the bubbleSort.java program, the invariant is that the data items to the right of outer are sorted. This remains true throughout the running of the algorithm.v在許多算法中，有條件保持不變，作為算法的收益。在許多算法中，有條件保持不變，作為算法的收益。這些條件被稱為不變量。這些條件被稱為不變量。v在在bubblesort.java程序，不變的是，外對數(shù)據(jù)項(xiàng)進(jìn)程序，不變的是，外對數(shù)據(jù)項(xiàng)進(jìn)行排序。這仍

6、然是真實(shí)的，在整個運(yùn)行的算法。行排序。這仍然是真實(shí)的，在整個運(yùn)行的算法。EFFICIENCY OF THE BUBBLE SORTthere will be about N2/2 comparisonsthere will be about N2/4 swaps大約有2個比較;大約有4個交換協(xié)議the bubble sort runs in O(N2) time.在阿（在阿（N）的時間內(nèi)的氣泡排序運(yùn)行。）的時間內(nèi)的氣泡排序運(yùn)行。當(dāng)你看到那些在泡泡排序和其他排序算法中的嵌套循環(huán)時，當(dāng)你看到那些在泡泡排序和其他排序算法中的嵌套循環(huán)時，你可能會懷疑一個算法在（你可能會懷疑一個算法在（2）時間內(nèi)運(yùn)行。

7、）時間內(nèi)運(yùn)行。Selection SortvThe selection sort improves on the bubble sort by reducing the number of swaps necessary from O(N2) to O(N). Unfortunately, the number of comparisons remains O(N2).v通過減少所需的交換數(shù)量（通過減少所需的交換數(shù)量（N），以減少的選擇），以減少的選擇排序的氣泡排序上的選擇排序減少了。不幸的是，排序的氣泡排序上的選擇排序減少了。不幸的是，比較的數(shù)量仍然是（比較的數(shù)量仍然是（N2）。）。A Br

8、ief Descriptionv所涉及的是通過所有的球員所涉及的是通過所有的球員和采摘（或選擇，因此，該和采摘（或選擇，因此，該名稱的排序）最短的一個。名稱的排序）最短的一個。這是最短的球員然后與左邊這是最短的球員然后與左邊的線端的球員交換，在位置的線端的球員交換，在位置0?，F(xiàn)在最左邊的玩家進(jìn)行。現(xiàn)在最左邊的玩家進(jìn)行排序，而不需要再被移動。排序，而不需要再被移動。注意，在這個算法中，排序注意，在這個算法中，排序的玩家堆積在左邊（較低的的玩家堆積在左邊（較低的指標(biāo)），而在泡沫排序他們指標(biāo)），而在泡沫排序他們積累的權(quán)利。積累的權(quán)利。APPLETJAVA CODE FOR SELECTION SOR

9、TBook57INVARIANTvIn the selectSort.java program, the data items with indices less than or equal to outer are always sorted.v在在selectsort.java程序，數(shù)據(jù)項(xiàng)指標(biāo)小于或等于程序，數(shù)據(jù)項(xiàng)指標(biāo)小于或等于外總是排。外總是排。EFFICIENCY OF THE SELECTION SORTv選擇排序執(zhí)行相同數(shù)量的比較，作為泡沫排序：選擇排序執(zhí)行相同數(shù)量的比較，作為泡沫排序：N*（1）/ 2。v對于大的值，比較次將占主導(dǎo)地位，所以我們不對于大的值，比較次將占主導(dǎo)地位，所

10、以我們不得不說，選擇排序運(yùn)行在阿（得不說，選擇排序運(yùn)行在阿（N2）的時間，正如）的時間，正如泡沫般的。泡沫般的。v然而，這無疑是更快因?yàn)楹苌儆谢Q。對于較小然而，這無疑是更快因?yàn)楹苌儆谢Q。對于較小的值，它可能實(shí)際上是相當(dāng)快，特別是如果交換的值，它可能實(shí)際上是相當(dāng)快，特別是如果交換時間是遠(yuǎn)遠(yuǎn)大于比較時間。時間是遠(yuǎn)遠(yuǎn)大于比較時間。Insertion Sortv在大多數(shù)情況下，插入排序是本章中描述的基本在大多數(shù)情況下，插入排序是本章中描述的基本類型的最好的部分。它仍然執(zhí)行在（類型的最好的部分。它仍然執(zhí)行在（2）的時間，）的時間，但它的約兩倍的速度快的泡沫排序和速度比正常但它的約兩倍的速度快的泡沫排

11、序和速度比正常情況下的選擇排序。情況下的選擇排序。APPLETJAVA CODE FOR INSERTION SORTBook62INVARIANTS IN THE INSERTION SORTvAt the end of each pass, following the insertion of the item from temp, the data items with smaller indices than outer are partially sorted.v每一關(guān)結(jié)束后，從臨時性的項(xiàng)目的插入，數(shù)據(jù)項(xiàng)每一關(guān)結(jié)束后，從臨時性的項(xiàng)目的插入，數(shù)據(jù)項(xiàng)與較小的指標(biāo)比外部部分排序。與較小的指

12、標(biāo)比外部部分排序。EFFICIENCY OF THE INSERTION SORTvHow many comparisons and copies does this algorithm require?拷貝數(shù)與比較的數(shù)量大致相同。然而，一個拷貝并不是一個拷貝數(shù)與比較的數(shù)量大致相同。然而，一個拷貝并不是一個交換，所以對于隨機(jī)數(shù)據(jù)，該算法運(yùn)行的速度快兩倍的泡沫交換，所以對于隨機(jī)數(shù)據(jù)，該算法運(yùn)行的速度快兩倍的泡沫排序和更快的選擇排序。排序和更快的選擇排序。comparisons :bubble sort: N*(N1)/2selection sort : N*(N1)/2vIn any case,

13、 like the other sort routines in this chapter, the insertion sort runs in O(N2) time for random data.vFor data that is already sorted or almost sorted, the insertion sort does much better.In this case the algorithm runs in O(N) time.vHowever, for data arranged in inverse sorted order, every possible

14、 comparison and shift is carried out, so the insertion sort runs no faster than the bubble sort.v在任何情況下，像其他排序例程，在本章中，插入排序在任何情況下，像其他排序例程，在本章中，插入排序運(yùn)行在阿（運(yùn)行在阿（N）的隨機(jī)數(shù)據(jù)的時間。）的隨機(jī)數(shù)據(jù)的時間。v對于已排序或幾乎排序的數(shù)據(jù)，插入排序會更好。在這對于已排序或幾乎排序的數(shù)據(jù)，插入排序會更好。在這種情況下，該算法在運(yùn)行種情況下，該算法在運(yùn)行O（N）時間。）時間。v然而，對于按順序排列的數(shù)據(jù)，每一個可能的比較和移然而，對于按順序排列的數(shù)據(jù)，每一個

15、可能的比較和移位都進(jìn)行了，所以插入排序的運(yùn)行速度比不快。位都進(jìn)行了，所以插入排序的運(yùn)行速度比不快。Sorting ObjectsvFor simplicity weve applied the sorting algorithms weve looked at thus far to a primitive data type: double. However, sorting routines will more likely be applied to objects than primitive types.v為簡單起見，我們已經(jīng)應(yīng)用了排序算法，我們已為簡單起見，我們已經(jīng)應(yīng)用了排序算法，

16、我們已經(jīng)看到了迄今為止的原始數(shù)據(jù)類型：雙。然而，經(jīng)看到了迄今為止的原始數(shù)據(jù)類型：雙。然而，排序例程將更容易被應(yīng)用于對象比原始類型。排序例程將更容易被應(yīng)用于對象比原始類型。Book66STABILITYvYou want the algorithm to sort only what needs to be sorted, and leave everything else in its original order. Some sorting algorithms retain this secondary ordering; theyre said to be stable.v你需要該算法來

17、排序，只有需要進(jìn)行排序，并把你需要該算法來排序，只有需要進(jìn)行排序，并把一切都在它的原始順序。一些排序算法保留此二一切都在它的原始順序。一些排序算法保留此二次排序，他們說是穩(wěn)定的。次排序，他們說是穩(wěn)定的。Comparing the Simple Sortsv 如果你沒有使用該算法的書，那就可能是沒有用的。這個如果你沒有使用該算法的書，那就可能是沒有用的。這個泡泡排序很簡單，你可以把它寫在內(nèi)存中。即使如此，它泡泡排序很簡單，你可以把它寫在內(nèi)存中。即使如此，它的實(shí)際應(yīng)用，只有當(dāng)數(shù)據(jù)量小。的實(shí)際應(yīng)用，只有當(dāng)數(shù)據(jù)量小。v 該選擇排序減少了交換的數(shù)量，但是比較的數(shù)量仍然很高。該選擇排序減少了交換的數(shù)量，但

18、是比較的數(shù)量仍然很高。它可能是有用的，當(dāng)數(shù)據(jù)量是小的和交換數(shù)據(jù)的項(xiàng)目是非它可能是有用的，當(dāng)數(shù)據(jù)量是小的和交換數(shù)據(jù)的項(xiàng)目是非常耗時的比較，比較它們。常耗時的比較，比較它們。v 插入排序是最通用的三個，是最好的賭注在大多數(shù)情況下，插入排序是最通用的三個，是最好的賭注在大多數(shù)情況下，假設(shè)數(shù)據(jù)量小或數(shù)據(jù)幾乎排序。對于大數(shù)據(jù)量，快速排序假設(shè)數(shù)據(jù)量小或數(shù)據(jù)幾乎排序。對于大數(shù)據(jù)量，快速排序通常被認(rèn)為是最快的方法；通常被認(rèn)為是最快的方法；v我們比較了排序算法的速度。對任何算法的另一我們比較了排序算法的速度。對任何算法的另一個考慮是，它需要多少內(nèi)存空間。本章中的所有個考慮是，它需要多少內(nèi)存空間。本章中的所有三個

19、算法都進(jìn)行了它們的排序，這意味著，在初三個算法都進(jìn)行了它們的排序，這意味著，在初始陣列的旁邊，很少需要額外的內(nèi)存。所有的類始陣列的旁邊，很少需要額外的內(nèi)存。所有的類需要一個額外的變量來存儲一個項(xiàng)目暫時當(dāng)它被需要一個額外的變量來存儲一個項(xiàng)目暫時當(dāng)它被換。換。Summaryv本章中的排序算法均假定一個數(shù)組作為數(shù)據(jù)存儲本章中的排序算法均假定一個數(shù)組作為數(shù)據(jù)存儲結(jié)構(gòu)。結(jié)構(gòu)。v排序包括比較數(shù)組中的數(shù)據(jù)項(xiàng)的鍵和移動的項(xiàng)目排序包括比較數(shù)組中的數(shù)據(jù)項(xiàng)的鍵和移動的項(xiàng)目（實(shí)際上是引用的項(xiàng)目），直到他們的排序順序。（實(shí)際上是引用的項(xiàng)目），直到他們的排序順序。v本章中的所有算法都在本章中的所有算法都在O（N2）時間內(nèi)

20、執(zhí)行。盡）時間內(nèi)執(zhí)行。盡管如此，一些人可能比其他人快。不變的是一個管如此，一些人可能比其他人快。不變的是一個在算法運(yùn)行時保持不變的情況在算法運(yùn)行時保持不變的情況.v泡沫排序是最有效的，但最簡單的排序。泡沫排序是最有效的，但最簡單的排序。v插入排序是本章所描述的最常用的（插入排序是本章所描述的最常用的（N）類型的）類型的插入類型。插入類型。v一種是穩(wěn)定的，如果元素的順序與相同的密鑰被一種是穩(wěn)定的，如果元素的順序與相同的密鑰被保留。保留。v在本章中，沒有一個比一個單一的臨時變量，除在本章中，沒有一個比一個單一的臨時變量，除了原來的數(shù)組了原來的數(shù)組v1 1 計算機(jī)排序算法與人類排序相比較，它的局限計

21、算機(jī)排序算法與人類排序相比較，它的局限性是性是：vA A 人類擅長發(fā)明新算法。人類擅長發(fā)明新算法。vB B 計算機(jī)只能處理數(shù)量固定的數(shù)據(jù)。計算機(jī)只能處理數(shù)量固定的數(shù)據(jù)。vC C 人類知道什么需要排序，而計算機(jī)不知道人類知道什么需要排序，而計算機(jī)不知道vD D 計算機(jī)一次只能比較兩件東西。計算機(jī)一次只能比較兩件東西。v2 2 冒泡排序算法在哪兩者之間交替進(jìn)行：冒泡排序算法在哪兩者之間交替進(jìn)行：vA A 比較和交換比較和交換vB B 移動和復(fù)制移動和復(fù)制vC C 移動和比較移動和比較vD D 復(fù)制和比較復(fù)制和比較v3 3 選擇排序中選擇排序中vA A 最大的關(guān)鍵字聚集到左邊最大的關(guān)鍵字聚集到左邊(

22、 (較小的下標(biāo)較小的下標(biāo)) )。vB B 最小的關(guān)鍵字被重復(fù)的發(fā)現(xiàn)。最小的關(guān)鍵字被重復(fù)的發(fā)現(xiàn)。vC C 為了將每個數(shù)據(jù)項(xiàng)插入到正確排序的位置，很為了將每個數(shù)據(jù)項(xiàng)插入到正確排序的位置，很多數(shù)據(jù)項(xiàng)將被移動多數(shù)據(jù)項(xiàng)將被移動vD D 有序的數(shù)據(jù)項(xiàng)聚集到右邊。有序的數(shù)據(jù)項(xiàng)聚集到右邊。v4 4 插入排序中，文中描述的插入排序中，文中描述的“被標(biāo)記的隊(duì)員被標(biāo)記的隊(duì)員”對對應(yīng)于應(yīng)于insertSort.avainsertSort.ava中的哪個變量中的哪個變量vA inA invB outB outvC tempC tempvD aoutD aoutv5.5.在插入排序中，在插入排序中，“局部有序局部有序”是

23、指：是指：vA A 一些數(shù)據(jù)項(xiàng)已經(jīng)排好序了一些數(shù)據(jù)項(xiàng)已經(jīng)排好序了, ,但它們可能需要被移但它們可能需要被移動。動。vB B 大部分?jǐn)?shù)據(jù)項(xiàng)已在它們最終排序的位置了，但大部分?jǐn)?shù)據(jù)項(xiàng)已在它們最終排序的位置了，但仍有一些需要排序仍有一些需要排序vC C 只有一些數(shù)據(jù)項(xiàng)有序。只有一些數(shù)據(jù)項(xiàng)有序。vD D 組內(nèi)的數(shù)據(jù)項(xiàng)已經(jīng)排好序，而組外面的數(shù)據(jù)項(xiàng)組內(nèi)的數(shù)據(jù)項(xiàng)已經(jīng)排好序，而組外面的數(shù)據(jù)項(xiàng)需要插入到組中來需要插入到組中來v6 6在插入排序中，一個數(shù)據(jù)項(xiàng)被插入到局部有序在插入排序中，一個數(shù)據(jù)項(xiàng)被插入到局部有序的組合后，它將的組合后，它將vA A 永遠(yuǎn)不會再移動。永遠(yuǎn)不會再移動。vB B 永遠(yuǎn)不會向左邊移動。永遠(yuǎn)不會向左邊移動。vC C 經(jīng)常被移出這個組。經(jīng)常被移出這個組。vD D 發(fā)現(xiàn)這組的數(shù)據(jù)項(xiàng)不斷減少發(fā)現(xiàn)這組的數(shù)據(jù)項(xiàng)不斷減少。v7 穩(wěn)定性是指：穩(wěn)定性是指：vA 在排序中排除有次關(guān)鍵字的項(xiàng)。在排序中排除有次關(guān)鍵字的項(xiàng)。vB 在對州進(jìn)行排序時，每個州的城市還要求按人在對州進(jìn)行排序時，每個州的城市還要求按人口遞增有序口遞增有序vC 讓相同的名配相同的姓。讓相同的名配相同的姓。vD 數(shù)據(jù)項(xiàng)按照主關(guān)鍵字有序，不考慮次關(guān)鍵字。數(shù)據(jù)項(xiàng)按照主關(guān)鍵字有序，不考慮次關(guān)鍵字。v8 簡單排序算法中的兩個基本操作是簡單排序算法中