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

1.冒泡排序（Bubble Sort）

(1)算法描述

冒泡排序是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

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

具體算法描述如下：

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

JavaScript代碼實(shí)現(xiàn)：

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

改進(jìn)后算法如下：

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

改進(jìn)后的算法為：

三種算法的運(yùn)行時(shí)間為：

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

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

（3）算法分析

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

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

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

　　當(dāng)輸入的數(shù)據(jù)是反序時(shí)

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

2.選擇排序（Selection Sort）

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

（1）算法簡介

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

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

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

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

Javascript代碼實(shí)現(xiàn)：

（3）算法分析

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

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論