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

這篇文章主要為大家詳細介紹了javascript基本常用排序演算法，具有一定的參考價值，有興趣的小夥伴們可以參考一下

備註：內容大部分從網路上複製，程式碼為自己手寫。僅做知識的溫故知新，並非原創。

1.冒泡排序（Bubble Sort）

(1)演算法描述

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

(2)演算法描述與實作

具體演算法描述如下：

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

JavaScript程式碼實作：

改進冒泡排序：設定一標誌性變數pos,用於記錄每趟排序中最後一次交換的位置。由於pos位置之後的記錄均已交換到位,故在進行下一趟排序時只要掃描到pos位置即可。

改進後演算法如下：

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

改進後的演算法為：

三種演算法的運行時間為：

#由運行結果可以看出時間複雜度更低，耗時更短了。大家可以親自嘗試下，運行的時候最好將三種演算法寫在一個檔案中運行，否則會因為瀏覽器等原因而產生誤差。

冒泡排序的動態圖示範：

（3）演算法分析

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

　　當輸入的資料已經是正序時

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

　　當輸入的資料是反序時

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

2.選擇排序（Selection Sort）

表現最穩定的排序演算法之一，因為無論什麼資料進去都是O(n²)的時間複雜度…..所以用到它的時候，資料規模越小越好。唯一的好處可能就是不佔用額外的記憶體空間了吧。理論上講，選擇排序可能也是平常排序一般人想到的最多的排序方法了吧。

（1）演算法簡介

選擇排序(Selection-sort)是一種簡單直覺的排序演算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素都排序完畢。

（2）演算法描述與實作

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

<1>.初始狀態：無序區為R[1..n]，有序區為空；<2>.第i趟排序(i=1 ,2,3…n-1)開始時，目前有序區和無序區分別為R[1..i-1]和R(i..n）。此行程排序從目前無序區中-選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R[i+1 ..n)分別變成記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；<3>.n-1趟結束，數組有序化了。

Javascript程式碼實作：

#（3）演算法分析

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

以上是JavaScript基本上常用排序演算法的實例解析的詳細內容。更多資訊請關注PHP中文網其他相關文章！