算法之排序

假定，你要為你的生日聚會邀請你的朋友和親戚。對此，你需要給他們打電話。你正在擁有10,000條記錄的電話本中查找名為Steve的電話號碼。然而，電話本中的記錄是以隨意順序存儲的。要在這樣一個目錄中查找你朋友的電話號碼，你需要按順序在目錄中瀏覽每個條目。這將非常耗時，你如何解決此問題呢？
? ??

節省時間和高效搜索數據的簡單解決方案是排序。
排序是按照某些預定義的順序或序列排列數據的過程。此順序可以是升序或降序。
如果數據被排序，則可以直接轉到存儲以‘S’開頭的姓名部分，因此減少了要遍歷的記錄數。

選擇排序算法

通過使用一算法實現在程序中排序。
一些排序算法有：
冒泡（Bubble）排序
選擇排序
插入排序
殼（Shell）排序
合并排序
快速排序
堆排序
要選擇合適的算法，你需要考慮以下方面：
執行時間
存儲空間
編程工作

冒泡排序算法：
是最簡單的排序算法之一
此算法具有二次方程增長階，因此適合僅排序小列表
通過列表重復掃描、比較相鄰元素和按錯誤順序交換，此算法會有作用.

編寫一算法以實現冒泡排序。
冒泡排序的算法是：
1.設置通道(圈數) = 1。
2.重復步驟3??區分0到n – 1通道中的j。
1.如果索引j處的元素大于索引j + 1處的元素，則交換這兩個元素。
3.按1遞增通道;圈數加1
4.如果通道 <= n-1，則轉到第2步。

排序算法的效率按照比較次數來測量。
在冒泡排序中，通道1內有n– 1 次比較，通道2中有n– 2次比較，依此類推。
比較總數= (n – 1) + (n – 2) + (n – 3) + … + 3 + 2 + 1= n(n– 1)/2。
n(n – 1)/2是O(n2)階的級數。因此，冒泡排序算法是階O(n2)的算法。

什么是冒泡排序算法的增長階？
答案：
n – 1 次比較

答案：
冒泡排序算法具有二次方增長階

當實現冒泡排序算法時，在通道1中將執行多少次比較？
答案：
n –1次比較

使用選擇排序來排序數據

選擇排序算法：
選擇排序還具有二次方程增長階，且因此僅適用于排序小的列表。
選擇排序通過列表反復掃描，每次掃描選擇一項，然后將這一項移動到列表中正確的位置。

要理解選擇排序算法的實現，考慮數組中存儲的未排序的數字列表。每次都尋找最小值，將最小值往前放

編寫一算法以實現選擇排序。
選擇排序的算法：
1.重復步驟2和3區分0到n -2通道中的j
2.找出arr[j]到arr[n– 1]中的最小值：
a.設置min_index = j
b.重復步驟c區分j + 1到n – 1的i
c.如果arr[i] < arr[min_index]:
? i.?? min_index = i
3.將arr[j]與arr[min_index]交換

在選擇排序中，在查找最小元素的通道1中有n– 1次比較。在查找第二個最小元素的通道2中有n -2次比較，依此類推。
比較總數 = (n – 1) + (n – 2) + (n – 3) + … + 3 + 2 + 1 =n(n– 1)/2
n(n – 1)/2是O(n2)階的級數。因此，選擇排序算法是階O(n2)的算法。

插入排序算法：
具有二次方程增長階，且因此僅用于排序小列表。
如果需要排序的列表幾乎已經排序，則插入排序比冒泡排序和選擇排序更有效率。

要理解插入排序算法的實現，考慮數組中存儲的未排序的數字列表。

要使用插入排序算法排序此列表：
你需要將列表分為兩個子列表，即排序和未排序。

若要通過使用插入排序排序大小為n的列表，您需要執行(n– 1) 次通道。
最佳用例效率：
當列表已經被排序時產生最佳用例。
在這種情況下，您必須在每個通道中僅做一次比較。
在n– 1次通道中，您將需要做n– 1次比較。
插入排序的最佳用例效率是O(n)階的。
最糟用例效率：
當列表按反向順序排序時產生最糟用例效率。
在這種情況下，您需要在第1個通道中做1次比較，在第二個通道中做2次比較，在第3個通道中做3次比較，在第n– 1 個通道中做n – 1次比較。
插入排序的最糟用例效率是O(n2)階的。

銷售經理對2004-2006念市場上最佳冷飲銷售員進行調查。David是一名軟件開發人員，他有一個冷飲品牌及其銷售數據的文件。 David 必須向銷售經理提供排序好的數據。文件總的數據或多或少都要進行排序。存儲此數據最有效率的排序算法是哪個？為什么？
記錄是以隨意順序存儲的。 ? ?

答案：
當列表部分排序時，插入排序提供了比泡泡排序和選擇排序更好的有效。因此David應使用插入排序算法。

殼排序算法：
只要此列表已經部分排序且造成平均用例中的無效解決方案，則插入算法是高效算法。
為了克服此限制，計算機科學家D.L. Shell提議改進插入排序算法。
新的算法稱為殼（Shell）排序，是按照他的姓名命名的。

殼排序：
通過按若干位置的距離形成多個子列表分隔元素并進行比較來改進插入排序算法
對每個子列表應用插入排序使元素朝著其正確的位置移動
幫助元素快速靠近正確的位置，因此減少了比較的次數

小結

在本章中，你已經學到：
排序是按照某些預定義的順序或關鍵值排列數據的過程。此順序可以是升序或降序。
用于排序數據有各種排序算法。其中一些如下：
冒泡排序
選擇排序
插入排序
殼排序
合并排序
快速排序
堆排序

若要選擇合適的算法，您需要考慮以下內容：
執行時間
存儲空間
編程工作
冒泡排序和選擇排序算法具有二次方程增長階，且因此僅適用于排序小的列表。
插入排序執行不同次數的比較，這取決于最初的元素分階。當元素已經處于排序階，則插入排序需要進行極少比較。
如果需要排序的列表幾乎已經排序，則插入排序比冒泡排序和選擇排序更有效率。

通過比較按若干位置的距離分隔的元素，殼排序改善了插入排序。這幫助元素快速靠近正確的位置，因此減少了比較的次數。