JavaScript基本常用排序算法的實例解析

備注：內(nèi)容大部分從網(wǎng)上復制，代碼為自己手寫。僅做知識的溫故知新，并非原創(chuàng)。

1.冒泡排序（Bubble Sort）

(1)算法描述

冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數(shù)列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

(2)算法描述和實現(xiàn)

具體算法描述如下：

<1>.比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；<2>.對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應該會是最大的數(shù)；<3>.針對所有的元素重復以上的步驟，除了最后一個；<4>.重復步驟1~3，直到排序完成。

JavaScript代碼實現(xiàn)：

改進冒泡排序：設(shè)置一標志性變量pos,用于記錄每趟排序中最后一次進行交換的位置。由于pos位置之后的記錄均已交換到位,故在進行下一趟排序時只要掃描到pos位置即可。

改進后算法如下：

傳統(tǒng)冒泡排序中每一趟排序操作只能找到一個最大值或最小值,我們考慮利用在每趟排序中進行正向和反向兩遍冒泡的方法一次可以得到兩個最終值(最大者和最小者) , 從而使排序趟數(shù)幾乎減少了一半。

改進后的算法為：

三種算法的運行時間為：

由運行結(jié)果可以看出時間復雜度更低，耗時更短了。大家可以親自嘗試下，運行的時候最好將三種算法寫在一個文件中運行，否則會由于瀏覽器等原因產(chǎn)生誤差。

冒泡排序的動態(tài)圖演示：

（3）算法分析

最佳情況：T(n) = O(n)

　　當輸入的數(shù)據(jù)已經(jīng)是正序時

最壞情況：T(n) = O(n2)

　　當輸入的數(shù)據(jù)是反序時

平均情況：T(n) = O(n2)

2.選擇排序（Selection Sort）

表現(xiàn)最穩(wěn)定的排序算法之一，因為無論什么數(shù)據(jù)進去都是O(n?)的時間復雜度…..所以用到它的時候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。理論上講，選擇排序可能也是平時排序一般人想到的最多的排序方法了吧。

（1）算法簡介

選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。

（2）算法描述和實現(xiàn)

n個記錄的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。具體算法描述如下：

<1>.初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空；<2>.第i趟排序(i=1,2,3…n-1)開始時，當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)；<3>.n-1趟結(jié)束，數(shù)組有序化了。

Javascript代碼實現(xiàn)：

（3）算法分析

最佳情況：T(n) = O(n2)最差情況：T(n) = O(n2)平均情況：T(n) = O(n2)

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com