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)

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。