一、冒泡排序
(1)算法描述和實現
1陨晶、比較相鄰的元素猬仁。如果第一個比第二個大，就交換它們兩個先誉；
2湿刽、對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對褐耳，這樣在最后的元素應該會是最大的數诈闺；
3、針對所有的元素重復以上的步驟铃芦，除了最后一個雅镊；
4襟雷、重復步驟1~3，直到排序完成仁烹。
動圖演示：http://img.blog.csdn.net/20160916160748389
(2)算法分析
最佳情況：T(n) = O(n)
最差情況：T(n) = O(n2)
(3)JavaScript代碼實現：
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)算法描述和實現
首先從原始數組中找到最小的元素，并把該元素放在數組的最前面卓缰，
然后再從剩下的元素中尋找最小的元素计呈，放在之前最小元素的后面，直到排序完畢征唬。
動圖演示：http://img.blog.csdn.net/20160916164754013
(2)算法分析
最佳情況：T(n) = O(n2)
最差情況：T(n) = O(n2)
(3)JavaScript代碼實現：
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]){//尋找最小的數
minIndex?=?j;//將最小數的索引保存
}
}
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)算法描述和實現
將n個元素的數列分為已有序和無序兩個部分。
數列：{a1鳍鸵，a2苇瓣，a3尉间，a4偿乖，…，an}
將該數列的第一元素視為有序數列哲嘲，后面都視為無序數列：
{{a1}贪薪，{a2，a3眠副，a4画切，…，an}}
將無序數列中的元素插入到有序數列的對應位置囱怕，插入前通過比大小的方式找到其在有序數列中的對應位置霍弹。
1、從第一個元素開始娃弓，該元素可以認為已經被排序典格；
2、取出下一個元素台丛，在已經排序的元素序列中從后向前掃描耍缴；
3、如果該元素（已排序）大于新元素挽霉，將該元素移到下一位置防嗡；
4、重復步驟3侠坎，直到找到已排序的元素小于或者等于新元素的位置蚁趁；
5、將新元素插入到該位置后实胸；
6荣德、重復步驟2~5闷煤。
動圖演示：http://img.blog.csdn.net/20160916173802597
(2)算法分析
最佳情況：T(n) = O(n)
最差情況：T(n) = O(n2)
(3)JavaScript代碼實現：
functioninsertionSort(array)?{
//假設第0個元素是一個有序的數列，第1個以后的是無序的序列涮瞻，
//所以從第1個元素開始將無序數列的元素插入到有序數列中
for(vari?=1;?i?<?array.length;?i++)?{
//取出無序數列中的第i個作為被插入元素
varkey?=?array[i];
//記住有序數列的最后一個位置
varj?=?i?-1;
//比大小鲤拿，找到被插入元素所在的位置
while(j?>=0&&?array[j]?>?key)?{
array[j?+1]?=?array[j];
j--;
}
//插入
array[j?+1]?=?key;
}
returnarray;
}
四、快速排序
(1)算法描述和實現
快速排序的基本思想：通過一趟排序將待排記錄分隔成獨立的兩部分署咽，其中一部分記錄的關鍵字均比另一部分的關鍵字小近顷，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序宁否。
1窒升、從數列中挑出一個元素，稱為“基準”（pivot）慕匠；
2饱须、所有小于"基準"的元素，都移到"基準"的左邊台谊；所有大于"基準"的元素蓉媳，都移到"基準"的右邊。
3锅铅、對"基準"左邊和右邊的兩個子集酪呻，不斷重復第一步和第二步，直到所有子集只剩下一個元素為止盐须。
(2)算法分析
最佳情況：T(n) = O(nlogn)
最差情況：T(n) = O(n2)
(3)JavaScript代碼實現：
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)算法描述和實現
歸并排序：其基本思想是分治策略，先進行劃分贼邓，然后再進行合并阶冈。
假設要對數組C進行歸并排序，步驟是：
1.先將C劃分為兩個數組A和B（即把數組C從中間分開）
2.再分別對數組A塑径、B重復步驟1的操作女坑，逐步劃分，直到不能再劃分為止(每個子數組只剩下一個元素)晓勇，這樣堂飞，劃分的過程就結束了。
如：[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.然后從下層往上層不斷合并數組绑咱，每一層合并相鄰的兩個子數組绰筛，合并的過程是每次從待合并的兩個子數組中選取一個最小的元素，然后把這個元素放到合并后的數組中描融，不斷重復直到把兩個子數組的元素都放到合并后的數組為止铝噩。
4.依次類推，直到合并到最上層結束窿克，這時數據的排序已經完成了骏庸。
[if !vml]
[endif]
[if !vml]
[endif]
動圖演示：http://img.blog.csdn.net/20160917001326254
(2)算法分析
最佳情況：T(n) = O(n)
最差情況：T(n) = O(nlogn)
(2)JavaScript代碼實現：
functionmergeSort(arr){//采用自上而下的遞歸方法
varlen?=?arr.length;
if(len?<2){
returnarr;
}
varmiddle?=?Math.floor(len?/2),
left?=?arr.slice(0,middle),//得到下標從0~index-1的數組
right?=?arr.slice(middle);//得到下標從index開始到末尾的數組
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));
