JavaScript 排序算法
前言：在前端大全中看到這句話，以此共勉。 基礎決定你可能達到的高度， 而業務決定了你的最低瓶頸
其實javascript算法在平時的編碼中用處不大，不過不妨礙我們學習它，學習一下這些算法的思想，鍛煉一下自己的思維模式。
本文不會每種方法都介紹一下，只介紹一下七種，純屬為了學習而學習，如果覺得代碼不是很好理解，可以將數組里面的內容代入函數里面。
不過剛開始理解的時候確實挺頭疼的。廢話少說，搞起來！！
冒泡排序
原理：
從第一個元素開始，往后比較，遇到比自己小的元素就交換位置
特點：
交換的次數最多，所以它的性能是最差的
代碼實現：
function bubbleSort(arr){
var len=arr.length;
for(var i=0;i<len;i++){
for(var j=0;j<len-1-i;j++){
if(arr[j]>arr[j+1]){ //相鄰元素兩兩對比
var temp=arr[j+1]; //交互位置,所以大的都放到了最后面
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(bubbleSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]
插入排序
原理：
插入排序的基本操作就是將一個數據插入到 已經排好序的有序數據中 ，從而得到一個新的、個數加一的有序數據
如圖所示
在插入排序中，數組會被劃分為兩種，“有序數組塊”和“無序數組塊”，
第一遍的時候從”無序數組塊“中提取一個數20作為有序數組塊。
第二遍的時候從”無序數組塊“中提取一個數60有序的放到”有序數組塊中“，也就是20，60。
第三遍的時候同理，不同的是發現10比有序數組的值都小，因此20，60位置后移，騰出一個位置讓10插入。
然后按照這種規律就可以全部插入完畢。
下面是一張gif圖
特點：
插入算法把要排序的數組分成兩部分：
第一部分包含了這個數組的所有元素，但將第一個元素除外（讓數組多一個空間才有插入的位置）.
第二部分就只包含這一個元素（即待插入元素）。在第一部分排序完成后，再將這個最后元素插入到已排好序的第一部分中
比冒泡排序快一點
代碼實現：
//插入排序
//假定當前元素之前的元素已經排好序，先把自己的位置空出來，
//然后前面比自己大的元素依次向后移，直到空出一個"坑"，
//然后把目標元素插入"坑"中
function insertSort(arr){
// 從第二個元素開始，因為要留出一個坑
for(var i=1;i<arr.length;i++){
var x=arr[i];
for(var j=i-1;arr[j]>x;j--){ //后挪空出位置 .
arr[j+1]=arr[j];
}
if(arr[j+1]!=x){
arr[j+1]=x;
}
}
return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(insertSort(arr,2)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]
希爾排序
原理：
希爾排序也叫 遞減增量排序算法 ，是插入排序的一種神龜進化版。
什么叫遞減增量呢，就是定義一個間隔序列，例如是5，3，1。第一次處理，會處理所有間隔為5的，
下一次會處理間隔為3的，最后一次處理間隔為1的元素。也就是相鄰元素執行標準插入排序。
步驟如下：
1、先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。
2、所有距離為d1的倍數的記錄放在同一個組中，在各組內進行直接插入排序。
3、取第二個增量d2<d1重復上述的分組和排序，
4、直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
這里增量的取法如下：
第一次增量的取法為： d=count/2;
第二次增量的取法為: d=(count/2)/2;
最后一直到: d=1;
看上圖觀測的現象為：
d=3時：將40跟50比，因50大，不交換。
將20跟30比，因30大，不交換。
將80跟60比，因60小，交換。
d=2時：將40跟60比，不交換，拿60跟30比交換，此時交換后的30又比前面的40小，又要將40和30交換，如上圖。
將20跟50比，不交換，繼續將50跟80比，不交換。
d=1時：這時就是前面講的插入排序了，不過此時的序列已經差不多有序了，所以給插入排序帶來了很大的性能提高。
特點：
由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，
相同的元素可能在各自的插入排序中移動，最后其穩定性就會被打亂，所以shell排序是不穩定的。
打個比方，我原來的數組是[5,4,3,2,1]的，這樣一打亂就全部重新排了。
代碼實現：
function shellSort(arr){
var gap=Math.floor(arr.length/2);
while(gap>0){
for(var i=gap;i<arr.length;i++){
temp=arr[i];
for(var j=i;j>=gap&&arr[j-gap]>temp;j-=gap){
arr[j]=arr[j-gap];
}
arr[j]=temp;
}
gap=Math.floor(gap/2);
}
return arr;
}
var arr = [2,3,6,4,2,1,90,100,20,5];
console.log(shellSort(arr)); //[1, 2, 2, 3, 4, 5, 6, 20, 90, 100]
歸并排序
原理：
歸并排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。
有以下幾個步驟：
1、把長度為n的輸入序列分成兩個長度為n/2的子序列;
2、對這兩個子序列繼續分為m/2的子序列，一直分下去
3、將兩個排序好的子序列合并成一個最終的排序序列。
再來一張靜態圖，比較好理解
這里需要補充是，歸并中對數組的分割是從上往下的，歸并中數組的比較是從下往上的。
特點：
速度僅次于快速排序，為穩定排序算法，一般用于對總體無序，但是各子項相對有序的數列.
屬于分治思想，遞歸歸并
代碼實現：
/* 排序并合并*/
function merge(left, right) {
var re = [];
while(left.length > 0 && right.length > 0) {
if(left[0] < right[0]) {
// 如果左邊的數據小于右邊的數據，將左邊的數據取出，放到新數組那里
re.push(left.shift());
} else {
re.push(right.shift());
}
}
/* 當左右數組長度不等.將比較完后剩下的數組項鏈接起來即可 */
return re.concat(left).concat(right);
}
function mergeSort(arr) {
if(arr.length == 1){
return arr;
}
/* 首先將無序數組劃分為兩個數組 */
var mid = Math.floor(arr.length / 2);
var left = arr.slice(0, mid);
var right = arr.slice(mid);
/* 遞歸分別對左右兩部分數組進行排序合并 */
return merge(mergeSort(left), mergeSort(right));
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(mergeSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]
快速排序
原理：
1、在數據集之中，選擇一個元素作為"基準"（pivot）。比如選擇下面數字45
2、所有小于"基準"的元素，都移到"基準"的左邊；所有大于"基準"的元素，都移到"基準"的右邊。
3、對"基準"左邊和右邊的兩個子集，不斷重復第一步和第二步，直到所有子集只剩下一個元素為止。
特點：速度 最快 。和歸并排序不同的是，歸并排序是先分為兩組再繼續排，而快速排序是邊分邊排
代碼實現：
// 大致分三步：
// 1、找基準（一般是以中間項為基準）
// 2、遍歷數組，小于基準的放在left，大于基準的放在right
// 3、遞歸
function quickSort(arr){
//如果數組<=1,則直接返回
if(arr.length<=1){
return arr;
}
var pivotIndex=Math.floor(arr.length/2);
//找基準，并把基準從原數組刪除
var pivot=arr.splice(pivotIndex,1)[0];
//定義左右數組
var left=[];
var right=[];
//比基準小的放在left，比基準大的放在right
for(var i=0;i<arr.length;i++){
if(arr[i]<=pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
//遞歸
return quickSort(left).concat([pivot],quickSort(right));
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(quickSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]
選擇排序
原理：在要排序的一組數中，選出最小的一個數與第一個位置的數交換，然后剩下的數當中找出最小的與第二個位置的數交換，如此循環直到倒數第二個數和最后一個數為止。
靜態圖：
特點：可以說是冒泡排序的衍生品，效率比較一般般
代碼實現：
// 在無序區中選出最小的元素，然后將它和無序區的第一個元素交換位置。
function selectSort(arr){
length = arr.length;
for (var i = 0; i < length; i++){ // 循環數組
var _min = arr[i]; // 把每一次的 數組里面的數字記錄下來
var k = i; // 記錄下來索引
for (var j = i + 1; j < length; j++){ // 當前的數字與后一個數字相比較
if (_min > arr[j]){ //當前的數 大于 后面一個數的話
_min = arr[j]; // 就講后面 的數值 保存下來
k = j; /// 保存索引
}
}
arr[k] = arr[i]; // 進行交換位置
arr[i] = _min;
}
return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(selectSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]
奇偶排序
原理：
選取所有奇數列的元素與其 右側 相鄰的元素進行比較，將較小的元素排序在前面；
選取所有偶數列的元素與其 右側 相鄰的元素進行比較，將較小的元素排序在前面；
重復前面兩步，直到所有序列有序為止。
如下圖所示：
gif圖：
特點：奇數和偶數序列交替比較
代碼實現：
function oddEvenSort(arr){
//swaped用來控制循環是否要繼續，如果左邊的都比右邊的小，則退出循環，返回排好的數組
var swaped=true;
var k=0;
while(swaped){
if(k>0){
swaped=false;
}
for(var i=k;i<arr.length-1;i+=2){
if(arr[i]>arr[i+1]){
// 如果左邊的數字比右邊的大，兩者交換位置
arr[i]=[ arr[i+1], arr[i+1]=arr[i] ][0];
swaped=true;
}
}
k=[1,0][k]; //奇數和偶數之間的轉行
}
return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(oddEvenSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]
總結
本文只是總結了算法中的一部分，算法的精髓就在于他們的思想，在js中用處應該不是很大。如果第一遍看不太懂那些代碼，可以試著自己敲一遍，我在總結的時候，遇到理解不了的代碼，自己敲完理解程度就會加深一些。
理解完，確實這些算法的實現思想博大精深，不得不感慨一下前輩們思想的深度。
來自：http://www.cnblogs.com/xianyulaodi/p/6001122.html