一、冒泡排序

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

1、比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；

2、對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應(yīng)該會是最大的數(shù)；

3、針對所有的元素重復(fù)以上的步驟，除了最后一個；

4、重復(fù)步驟1~3，直到排序完成。

動圖演示：http://img.blog.csdn.net/20160916160748389

(2)算法分析

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

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

(3)JavaScript代碼實現(xiàn)：

functionbubbleSort(arr)?{

varlen?=?arr.length;

for(vari?=0;?i?<?len;?i++)?{

for(varj?=0;?j?<?len?-1-?i;?j++)?{

if(arr[j]?>?arr[j+1])?{//相鄰元素兩兩對比

vartemp?=?arr[j+1];//元素交換

arr[j+1]?=?arr[j];

arr[j]?=?temp;

}

}

}

returnarr;

}

vararr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];

console.log(bubbleSort(arr));//[2,?3,?4,?5,?15,?19,?26,?27,?36,?38,?44,?46,?47,?48,?50]

二、選擇排序

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

首先從原始數(shù)組中找到最小的元素，并把該元素放在數(shù)組的最前面，

然后再從剩下的元素中尋找最小的元素，放在之前最小元素的后面，直到排序完畢。

動圖演示：http://img.blog.csdn.net/20160916164754013

(2)算法分析

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

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

(3)JavaScript代碼實現(xiàn)：

functionselectionSort(arr){

varlen?=?arr.length;

varminIndex,temp;

for(vari?=0;?i?<?len?-1;?i?++){

minIndex?=?i;

for(varj?=?i?+1;?j?<?len;?j?++){

if(arr[j]?<?arr[minIndex]){//尋找最小的數(shù)

minIndex?=?j;//將最小數(shù)的索引保存

}

}

temp?=?arr[i];

arr[i]?=?arr[minIndex];

arr[minIndex]?=?temp;

}

returnarr;

}

vararr?=?[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];

console.log(selectionSort(arr));//[2,?3,?4,?5,?15,?19,?26,?27,?36,?38,?44,?46,?47,?48,?50]

三、插入排序

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

將n個元素的數(shù)列分為已有序和無序兩個部分。

數(shù)列：{a1，a2，a3，a4，…，an}

將該數(shù)列的第一元素視為有序數(shù)列，后面都視為無序數(shù)列：

{{a1}，{a2，a3，a4，…，an}}

將無序數(shù)列中的元素插入到有序數(shù)列的對應(yīng)位置，插入前通過比大小的方式找到其在有序數(shù)列中的對應(yīng)位置。

1、從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序；

2、取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；

3、如果該元素（已排序）大于新元素，將該元素移到下一位置；

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

5、將新元素插入到該位置后；

6、重復(fù)步驟2~5。

動圖演示：http://img.blog.csdn.net/20160916173802597

(2)算法分析

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

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

(3)JavaScript代碼實現(xiàn)：

functioninsertionSort(array)?{

//假設(shè)第0個元素是一個有序的數(shù)列，第1個以后的是無序的序列，

//所以從第1個元素開始將無序數(shù)列的元素插入到有序數(shù)列中

for(vari?=1;?i?<?array.length;?i++)?{

//取出無序數(shù)列中的第i個作為被插入元素

varkey?=?array[i];

//記住有序數(shù)列的最后一個位置

varj?=?i?-1;

//比大小，找到被插入元素所在的位置

while(j?>=0&&?array[j]?>?key)?{

array[j?+1]?=?array[j];

j--;

}

//插入

array[j?+1]?=?key;

}

returnarray;

}

四、快速排序

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

快速排序的基本思想：通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠郑渲幸徊糠钟涗浀年P(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。

1、從數(shù)列中挑出一個元素，稱為“基準(zhǔn)”（pivot）；

2、所有小于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的左邊；所有大于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的右邊。

3、對"基準(zhǔn)"左邊和右邊的兩個子集，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個元素為止。

(2)算法分析

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

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

(3)JavaScript代碼實現(xiàn)：

functionquickSort(arr)?{

if(arr.length?<=1)?{returnarr;?}

varpivotIndex?=?Math.floor(arr.length?/2);

varpivot?=?arr.splice(pivotIndex,1)[0];

varleft?=?[];

varright?=?[];

for(vari?=0;?i?<?arr.length;?i?++){

if(arr[i]?<?pivot)?{

left.push(arr[i]);

}else{

right.push(arr[i]);

}

}

returnquickSort(left).concat([pivot],?quickSort(right));

};

vararr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];

console.log(quickSort(arr));//[2,?3,?4,?5,?15,?19,?26,?27,?36,?38,?44,?46,?47,?48,?50]

五、歸并排序

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

歸并排序：其基本思想是分治策略，先進行劃分，然后再進行合并。

假設(shè)要對數(shù)組C進行歸并排序，步驟是：

1.先將C劃分為兩個數(shù)組A和B（即把數(shù)組C從中間分開）

2.再分別對數(shù)組A、B重復(fù)步驟1的操作，逐步劃分，直到不能再劃分為止(每個子數(shù)組只剩下一個元素)，這樣，劃分的過程就結(jié)束了。

如：[12 20 30 21 15 33 26 19 40 25]

劃分為: ?[12 20 30 21 15]

[33 26 19 40 25]

[12 20] ? ? ?[30 21 15] ? ? ? [33 26]

[19 40 25]

[12] ?[20] ? [30] ?[21 15] ? ? [33] ?[26]

[19] ? ?[40 25]

[12] ?[20] ? [30] [21] [15] ? ?[33] ?[26]

[19] ? [40] [25]

3.然后從下層往上層不斷合并數(shù)組，每一層合并相鄰的兩個子數(shù)組，合并的過程是每次從待合并的兩個子數(shù)組中選取一個最小的元素，然后把這個元素放到合并后的數(shù)組中，不斷重復(fù)直到把兩個子數(shù)組的元素都放到合并后的數(shù)組為止。

4.依次類推，直到合并到最上層結(jié)束，這時數(shù)據(jù)的排序已經(jīng)完成了。

[if !vml]

[endif]

[if !vml]

[endif]

動圖演示：http://img.blog.csdn.net/20160917001326254

(2)算法分析

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

最差情況：T(n) = O(nlogn)

(2)JavaScript代碼實現(xiàn)：

functionmergeSort(arr){//采用自上而下的遞歸方法

varlen?=?arr.length;

if(len?<2){

returnarr;

}

varmiddle?=?Math.floor(len?/2),

left?=?arr.slice(0,middle),//得到下標(biāo)從0~index-1的數(shù)組

right?=?arr.slice(middle);//得到下標(biāo)從index開始到末尾的數(shù)組

returnmerge(mergeSort(left),mergeSort(right));//里面采用遞歸

}

functionmerge(left,right){//每次left或者right都是要shift掉第一個元素，最后arr.concat，因為不知道left或者right其中一個哪個剩下元素，所以要將剩下的元素給加上

varresult?=?[];

while(left.length?&&?right.length){

if(left[0]?<=?right[0]){

result.push(left.shift());

}else{

result.push(right.shift());

}

}

while(left.length)

result.push(left.shift());

while(right.length)

result.push(right.shift());

returnresult;

}

vararr?=?[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];

console.log(mergeSort(arr));