經(jīng)典排名算法在面試中占有很大比重，也是基礎(chǔ)。包括冒泡排序、插入排序、選擇排序、希爾排序、合并排序、快速排序和堆排序。希望能幫助到有需要的同學(xué)。整個程序用Java實現(xiàn)。

本文中的所有排序?qū)崿F(xiàn)都是從小到大默認的。

首先，泡沫不要進行泡沫分類

簡介:

氣泡排序的原理很簡單。它重復(fù)訪問要排序的序列，一次比較兩個元素，如果它們的順序錯誤，就交換它們。

步驟:

比較相鄰元素。如果第一個比第二個大，就換。

對第0到第(n-1)個數(shù)據(jù)執(zhí)行相同的操作。此時，最大的數(shù)字“浮動”到數(shù)組的最后一個位置。

對除最后一個元素之外的所有元素重復(fù)上述步驟。

一次對越來越少的元素重復(fù)上述步驟，直到?jīng)]有要比較的數(shù)字對。

/**

*冒泡排序算法

*原理是相鄰號碼成對比較，按從小到大或從大到小的順序交換，這樣一趟旅行后，最大或最小的號碼交換到最后一個位置，然后從開始到倒數(shù)第二個位置結(jié)束進行成對比較交換

* @param nums排序數(shù)組

* @param n數(shù)組長度

*最壞情況:O(n2)如果氣泡排序沒有優(yōu)化，最好的情況是O(n2)，優(yōu)化后最好的情況是O(n)

*/

public void Bullersort(int[]nums，int len){

for(int I = 0；i<。len-1；I++){ //一個比較

for(int j = 0；j<。& ltstrong>。len-1-i<。/strong>。；J++){ //為了比較，每次最大值都放在后面，下次比較后不需要比較I的個數(shù)。

int temp = nums[j]；

if(nums[j]>nums[j+1]){

nums[j]= nums[j+1]；

nums[j+1]= temp；

}

}

}system.out.println("冒泡排序:")；

for (int i : nums) {

system . out . print(I+" ")；

}

}

但是，上面的代碼有兩種優(yōu)化方案。

優(yōu)化1:如果某次遍歷沒有數(shù)據(jù)交換，說明已經(jīng)排序了，不用再迭代了。用標(biāo)簽記錄該狀態(tài)(程序如下)。

優(yōu)化二:記錄某次遍歷的最后一次數(shù)據(jù)交換位置。這個位置之后的數(shù)據(jù)顯然是有序的，不需要排序。因此，下一個周期的范圍可以通過記錄最后一次數(shù)據(jù)交換的位置來確定(“j

public void better bulletorsort(int[]nums，int len){

布爾標(biāo)志；

flag = true

for(int I = 0；i<。len-1和& amp旗幟；I++){ // A比較如果前面的比較沒有交換，說明順序安排在后面，不用再比較了

flag = false

for(int j = 0；j<。len-1-I；J++){ //為了比較，每次最大值都放在后面，下次比較后不需要比較I的個數(shù)。

int temp = nums[j]；

if(nums[j]>nums[j+1]){

nums[j]= nums[j+1]；

nums[j+1]= temp；

flag = true

}

}

}

System.out.println("優(yōu)化氣泡排序:")；

for (int i : nums) {

system . out . print(I+" ")；

}

}

第二，選擇排序選擇開始

簡介:

選擇排序無疑是最簡單直觀的排序。工作原理如下。

步驟:

在未排序的序列中找到最小的(大的)元素，并將其存儲在排序序列的開頭。

然后繼續(xù)從剩余的未排序元素中搜索最小的(大的)元素，然后把它放在排序序列的末尾。

以此類推，直到所有元素都被排序。

& ltspan style = " font-size:14px；font-weight: normal>。/**

*選擇排序算法

*基本思路是從每次行程要排序的記錄中選擇關(guān)鍵字最小的記錄，放在排序后的子序列前面，直到所有記錄排序完畢。

* @param nums排序數(shù)組

* @param n數(shù)組長度

*最壞情況:0(N2)，最好情況:0(N2)

*/

public void select sort(int[)nums，int len){

for(int I = 0；i<。leni++){

int min = nums[I]；//每次行程的最小值暫定為nums[i]

int index = I；//記錄最小值的索引值

for(int j = I+1；j<。lenJ++){ //開始比較:從i+1位置到數(shù)組末尾比較，找出最小值，記錄位置

if(nums[j]& lt；min){

min = nums[j]；

index = j；

}

}

//用最小值交換nums[i]

[指數(shù)]=[指數(shù)]；

nums[I]= min；

}

system . out . println(" select sort:")；

for (int i : nums) {

system . out . print(I+" ")；

}

} & lt/span>。

第三，插入排序插入排序

簡介:

插入排序的工作原理是，對于每個未排序的數(shù)據(jù)，在排序后的序列中從后往前掃描，找到對應(yīng)的位置，插入。

步驟:

從第一個元素開始，可以認為這個元素已經(jīng)排序

取出下一個元素，按照元素的排序順序從后向前掃描

如果掃描的元素(已排序)大于新元素，則將該元素向后移動一位

重復(fù)步驟3，直到找到排序元素小于或等于新元素的位置

將新元素插入此位置后，

重復(fù)步驟2~5

/**

*插入排序算法

* @param nums排序數(shù)組

* @param n數(shù)組長度

*最差情況:輸入數(shù)組已被倒o排序(N2)；最佳情況:輸入數(shù)組排序為o(n)；平均情況:0(N2)

*因為插入排序的內(nèi)部循環(huán)非常緊湊，所以對于小規(guī)模輸入，插入排序是一種非常快速的排序算法

*/

public void InsertSort(int[] nums，int len){

int j；

for(int I = 1；i<。leni++){

int temp = nums[I]；

for(j = I；j>。0;j - ){

if(temp & lt；nums[j-1]){

nums[j]= nums[j-1]；//將nums[i]之前大于nums[i]的所有值移回一位

}

否則中斷；

}

//在移動所有大于nums[i]的值后，j只需指向大于nums[i]的前面位置

nums[j]= temp；

}

system . out . println(" insert sort:")；

for (int i : nums) {

system . out . print(I+" ")；

}

}

第四，希爾排序殼排序

簡介:

希爾排序，也稱為降序遞增排序算法，本質(zhì)上是分組插入排序。是唐納德·謝爾在1959年提出的。希爾排序是一種不穩(wěn)定的排序算法。

希爾排序的基本思想是在一個表中列出數(shù)組，并分別插入和排序列，重復(fù)這個過程，但每次使用更長的列(步長更長，列更少)。最后整個表只有一列。數(shù)組轉(zhuǎn)換成表的目的是為了更好的理解算法，算法本身就是用數(shù)組來排序的。

例如，假設(shè)有這樣一組數(shù)字

[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]

如果我們以5的步長開始排序，我們可以通過將這個列表放在一個有5列的表中來更好地描述算法，這樣它們應(yīng)該是這樣的:

13 14 94 33 82

25 59 94 65 23

45 27 73 25 39

10

然后我們對每一列進行排序:

10 14 73 25 23

13 27 94 33 39

25 59 94 65 82

45

當(dāng)以上四行數(shù)字按順序連接在一起時，我們得到:

[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]

。此時，10已經(jīng)移動到正確的位置，然后按照3:

10 14 73

25 23 13

27 94 33

39 25 59

94 65 82

45

排序后，它變成:

10 14 13

25 23 33

27 25 59

39 65 73

45 94 82

94

最后按1步排序(此時簡單插入排序)。

/**

*希爾排序算法

* @param nums排序數(shù)組

* @param n數(shù)組長度

*最差情況:0(N2)使用Hibbard增量的最差情況:0(n = 3/2)

*/

public void ShellSort(int[] nums，int len){

int增量；

int temp，I，j；

for(increment = len/2；增量>。0;增量/= 2){ //增量為len/2len/4len/8...一

for(I =增量；i<。lenI++){ //插入并排序每個子序列

temp = nums[I]；

for(j = I；j>。=增量；j -=增量){

if(temp & lt；nums[j-increment]){

nums[j]= nums[j-increment]；

}

其他

打破；

}

nums[j]= temp；

}

}

system . out . println(" Hill Sort:")；

for (int k : nums) {

system . out . print(k+" ")；

}

}

動詞 （verb的縮寫）合并排序合并排序

簡介:

合并排序是分治法的典型應(yīng)用。

合并成

排序的思想是先交付

返回

分解數(shù)組，然后

接近

和數(shù)組。

考慮先合并兩個有序數(shù)組?；舅悸肥潜容^兩個數(shù)組的前數(shù)，先取較小的那個。取完之后，對應(yīng)的指針會向后移動一位。然后比較，直到一個數(shù)組是空，最后復(fù)制另一個數(shù)組的剩余部分。

考慮遞歸分解，基本思想是將數(shù)組分解成

左邊的

和

正確的

如果這兩個數(shù)組的內(nèi)部數(shù)據(jù)是有序的，那么這兩個數(shù)可以通過上述合并數(shù)組的方法進行合并排序。如何讓這兩個數(shù)組內(nèi)部有序？可以進一步分為兩部分，直到分解后的群只包含一個元素，此時認為群是有序的。然后合并并排序兩個相鄰的組。

/**

*合并排序算法

*對待序列R[0...n-1]排序為n個長度為1的有序序列，將相鄰有序表成對合并，得到n/2個長度為2的有序表；再次合并這些有序序列，

*得到長度為4的n/4有序序列；如此反復(fù)，最終得到長度為n的有序序列。

*總結(jié)一下，合并排序其實有兩件事要做:(1)“分解”——一次把序列分成兩半。(2)“合并”——將分割后的序列片段成對合并后進行排序。

* @param nums

* @param透鏡

* O(nlogn)

*/

public void MergeSort(int[] nums，int len){

sort(nums，0，len-1)；

system . out . println(" merge sort:")；

for (int k : nums) {

system . out . print(k+" ")；

}

}

//將一個數(shù)組按段分成兩個數(shù)組

public void sort(int[] nums，int low，int high){

int mid =(高+低)/2；

if(低& lt高){

排序(nums，low，mid)；

排序(nums，中間+1，高)；

合并(nums，低，中，高)；

}

}

//按節(jié)排序，然后重新組合在一起

public void merge(int[] array，int low，int mid，int high){

int i =低電平；//第一個序列的下標(biāo)

int j = mid+1；//第二個序列的下標(biāo)

int k = 0；//第三個序列的下標(biāo)

int[]array 2 = new int[high-low+1]；//新序列

while(I & lt；=mid &。& ampj<。=high){ //比較兩個子序列的首元素，取較小的一個進入新序列，然后跳過舊序列中較小的值，開始下一次比較

if(array[I]& lt；= array[j]){

array 2[k++]= array[i++]；

}

else{

array 2[k++]= array[j++]；

}

}

if(I & lt；= mid){ //表示以上是J溢出退出循環(huán)，也就是序列1還沒有比較。

while(I & lt；=mid){ //如果第一個序列沒有被掃描，將其全部復(fù)制到合并的序列中

array 2[k++]= array[i++]；

}

}

else if(j & lt；=高){

while(j & lt；=high){ //如果第二個序列沒有被掃描，將其全部復(fù)制到合并的序列中

array 2[k++]= array[j++]；

}

}

for(k = 0；k<。array 2 . length；k++){

array[k+low]= array 2[k]；//將按段排序的新數(shù)組復(fù)制到以前的數(shù)組中

}

}

第六，快速排序快速排序

簡介:

快速排序通常比其他同樣是ο (n log n)的算法快，所以經(jīng)常使用。而且快速排序采用分而治之的思想，所以在很多筆試面試中經(jīng)常能看到快速排序的影子?？梢娬莆湛炫藕苤匾?/p>

步驟:

從系列中選出一個元素作為參考編號。

在分割過程中，大于參考數(shù)的數(shù)字放在右邊，小于或等于參考數(shù)的數(shù)字放在左邊。

然后在左右區(qū)間遞歸執(zhí)行第二步，直到每個區(qū)間只有一個數(shù)字。

/**

*快速分類

*快速排序的思路是分而治之。快速排序就是找一個元素(理論上可以找任意一個)作為支點，

*然后對數(shù)組進行分區(qū)，使基準(zhǔn)左側(cè)元素的值不大于基準(zhǔn)值，基準(zhǔn)右側(cè)元素的值不小于基準(zhǔn)值，這樣作為基準(zhǔn)的元素排序后調(diào)整到正確的位置。

*遞歸快速排序，排序后將其他n-1個元素調(diào)整到正確的位置。最后，每個元素排序后都在正確的位置，排序完成。

*所以快速排序的核心算法是分區(qū)操作，也就是如何調(diào)整基準(zhǔn)的位置，調(diào)整返回基準(zhǔn)的最終位置，從而分治遞歸。

* @param nums

* @param透鏡

* O(NlogN)

*/

public void Quickort(int[]nums，int len){

Qsort(nums，0，len-1)；

System.out.println("快速排序:")；

for (int k : nums) {

system . out . print(k+" ")；

}

}

public void Qsort(int[] nums，int left，int right) {

if(左>;右)返回；

int pivot = nums[left]；

int i = left

int j = right

while(I & lt；j){

while(nums[j]>=樞軸& amp& ampi<。J){ //從右向左找一個小于nums[i]的數(shù)

j-；

}

nums[I]= nums[j]；//找到后交換

while(nums[I]& lt；=樞軸& amp& ampi<。J){ //從左到右找一個大于nums[j]的數(shù)

i++；

}

nums[j]= nums[I]；//找到后交換

}

//而在執(zhí)行之后，必然有i==j = J。

nums[I]= pivot；//重置參考號

Qsort(nums，左側(cè)，I-1)；//遞歸處理左側(cè)

Qsort(nums，i+1，右)；//遞歸處理右側(cè)

}

七、堆排序堆

簡介:

堆排序常用于前K個問題。堆排序是利用二進制堆的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的，雖然本質(zhì)上是一維數(shù)組。二進制堆是一個近似完整的二叉樹。

二進制堆棧具有以下屬性:

父節(jié)點的鍵值總是大于或等于(小于或等于)任何子節(jié)點的鍵值。

每個節(jié)點的左右子樹都是二進制堆(最大堆和最小堆)。

步驟:

Build_Max_Heap:如果數(shù)組下標(biāo)范圍是0~n，考慮到單個元素是一個很大的根堆，從下標(biāo)開始

n/2

起始元素都是大根樁。所以就從

n/2-1

首先依次向前構(gòu)造根堆，以保證在構(gòu)造一個節(jié)點時，其左右子樹已經(jīng)是根堆。

HeapSort:因為堆是由數(shù)組模擬的。得到一個很大的根堆后，數(shù)組內(nèi)部并不有序。因此，需要對堆數(shù)組進行排序。思路是去掉根節(jié)點，做最大堆調(diào)整的遞歸運算。將是第一次

堆[0]

和

希普·[n-1]

交換，對嗎

堆[0...n-2]

做最大的調(diào)整。第二次將是

希普·[[0]

和

希普·[n-2]

交換，對嗎

堆[0...n-3]

做最大的調(diào)整。重復(fù)此操作，直到

希普·[[0]

和

希普·[1]

交換。因為每次最大數(shù)合并到下面的有序區(qū)間，所以運算后整個數(shù)組都是有序的。

Max heap adjust (Max_Heapify):這個方法是為上面兩個過程調(diào)用提供的。目的是調(diào)整堆的末端子節(jié)點，使子節(jié)點始終小于父節(jié)點。

/**

*堆排序算法(最大堆)

* @param nums排序數(shù)組

* @param n數(shù)組長度

*時間復(fù)雜度O(nlogn)

*先構(gòu)建最大的堆，然后循環(huán)刪除堆根節(jié)點上的最大值，并移動到堆的末尾，將堆的長度減少一，然后開始下一次刪除根節(jié)點

*/

public void HeapSort(int[] nums，int len){

//構(gòu)建最大堆

for(int I = len/2；i>。=0;i - ){

PerDoWn(nums，I，len)；

}

//循環(huán)，每次改變根節(jié)點和最后一個節(jié)點的位置

for(int I = len-1；i>。=1;i - ){

//Swap(nums[0]，nums[i])交換nums[0]和nums[i]

int temp = nums[0]；

nums[0]= nums[I]；

nums[I]= temp；

percDown(nums，0，I)；

}

System.out.println("堆排序:")；

for (int k : nums) {

system . out . print(k+" ")；

}

}

/**

*堆調(diào)整，使其生成最大的堆

* @param nums

* @param i

* @param大小

*/

public void PerDown(int[]nums，int i，int size){

int left = 2 * I+1；

int right = 2 * I+2；

int max = I；

if(左& lt尺寸和尺寸。& ampnums[left]>nums[max]){

max =左側(cè)；

}

if(右& lt尺寸和尺寸。& ampnums[right]>nums[max]){

max =右；

}

if(max！= i){

int temp = nums[I]；

nums[I]= nums[max]；

nums[max]= temp；

percDown(nums，max，size)；

}

}

總結(jié)

以下是七種經(jīng)典排序算法指標(biāo)的比較:

-結(jié)束-

定價:59.80元

書號:9787302501725