相信排序是任何一個程序猿都會用到的東西，今天簡單總結記錄下常見的排序算法。
一.冒泡排序
說起冒泡排序，可能每個人都不會陌生，實現思路相當簡單明了，就是不停的對數組進行兩兩比較，將較大（較小）的一項放在前面；
如 var arr = [7, 3, 10, 1, 8, 4, 2, 4, 4, 3] 進行升序排列,排序過程如下
第一次 [3, 7, 1, 8, 4, 2, 4, 4, 3, 10]
第二次 [3, 1, 7, 4, 2, 4, 4, 3, 8, 10]
以此類推 。。。。
結果 [1, 2, 3, 3, 4, 4, 4, 7, 8, 10]；
//冒泡排序
function bubbleSort(arr){
var len = arr.length,t
for(j=0;j<=len-1;j++){
for(i=0;i<=len-j-1;i++){
if(arr[i]>arr[i+1]){
t = arr[i+1];
arr[i+1] = arr[i];
arr[i] = t;
}
}
}
return arr;
}
二.快速排序
快速排序也是我們常用到的一種排序方式，核心步驟如下
1.選擇中間數。
2.構建兩個臨時數組，比中間數小的放到左邊，大的放到右邊
3.對臨時數組重復1-2；
例如，我們原始數組為[2,4,1,5,6,3,12,9,7]，第一步我們選擇第5項 6 為中間數，創建臨時數組left，right，則left 結果為[2,4,1,5,3],right 結果為 [12,9,7]。然後再分別對left和right進行相同的操作，直至left及right數組長度為1.
具體代碼如下：
//快速排序
function quickSort(arr){
if(arr.length <= 1){ //數組長度為1時，則停止遞歸
return arr
}
var l = Math.floor(arr.length/2); //選擇中間數
var left = [],right=[];
var splitEle = arr.splice(l,1)[0] //將中間數從原數組刪除並保存
for(i=0;i<arr.length;i++){
if(arr[i] < splitEle){
left.push(arr[i])
}else{
right.push(arr[i])
}
}
return arguments.callee(left).concat(splitEle,arguments.callee(right))
}
三.選擇排序
選擇排序核心思想如下：
加入我們進行升序排列，我們假設數組第一項為最小值，然後將第一項與其他項分別比較，如果其他項小於第一項，則交換位置，這樣第一次循環結束我們可以保證第一項為最小值。然後第二項做類似操作，然後以此類推，具體如下圖所示
代碼如下：
//選擇排序
function selectQuot(arr){
for(i=0; i<arr.length-1; i++){
for(j=i+1;j<arr.length;j++){
if(arr[i] > arr[j]){
var temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr
}
四.插入排序
插入排序很好理解，首先我們取出第一項放入一個虛構的數組，然後取第二項，假如第二項小於第一項，則將第二項放於第一項的前面，否則放在後面；然後取第三項，分別與前兩項進行比較（是不是有點兒類似打撲克牌~~）
如我們的數組為[2, 4, 1, 5, 3, 8 ,7 ,9 , 6]；
假定我們有一個虛擬數組，則第一步數組為[2],然後我們取數組的第二項，發現要比剛才取得數組項大，則我們放在後面即虛擬數組變成[2,4]，然後取下一項與虛擬數組中的項分別比較，按上述思路結果為[1,2,4],以此類推……當然在實際編程中我們並不需要單獨創建數組。
代碼如下：
//插入排序
function insertSort(arr){
for(i=1 ; i<arr.length ; i++ ){
var temp = arr[i],
j = i - 1;
while(j>=0 && temp < arr[j]){
arr[j+1] = arr[j]; //相當於將虛擬數組當前項後移一位，同時虛擬數組長度+1
j--;
}
arr[j+1] = temp; //新加項最終插入的位置
}
return arr;
}
五.希爾排序
希爾排序是插入排序的升級版，又稱為縮小增量排序。
對於插入排序算法來說，如果原來的數據就是有序的，那麼數據就不需要移動，基於此，希爾排序首先將數組按照一定間隔分為若干個小數組分別進行插入排序，然後逐漸減小間隔，直至為1，這樣最後一次處理即間隔為1的排序，但由於之前的操作後數組基本變為有序數組，這樣就能提高些效率。示意如下：
我們原始數組為[3, 4, 6, 5, 1, 9, 6, 10, 8, 8]
第一步我們假設增量為3，按照希爾排序思路我們將數組如下分割
我們每一次將同樣的分組賦予同一顏色，然後對每一分組進行插入排序，空白顏色為結果。
實現代碼如下：
//希爾排序
function shellSort(array) {
var len = array.length;
var gap = len;
do {
gap = Math.floor(gap/3)+1; // 減小增量
// 把距離為gap的元素編為一個組，掃描所有組
for (var i = gap; i < len; i++) {
var temp = array[i],
j = i - gap;
while(j>=0 && temp < array[j]){
array[j + gap] = array[j];
j -= gap;
}
array[j+gap] = temp;
}
}while(gap > 1)
return array
}
六.歸並排序
歸並排序的核心思想是，首先將數組分成若干個子數組變成有序數組，再合並有序數組。
具體流程盜用網絡上一張圖，一看便知
代碼如下：
var mergeSort = {
splitArr : function(arr){
if(arr.length == 1) return arr;
var mid = Math.floor(arr.length/2),
left = arr.slice(0,mid),
right = arr.slice(mid);
return this.merge(this.splitArr(left),this.splitArr(right))
},
merge : function(left , right){
var result = [];
while(left.length > 0 && right.length > 0){
if(left[0] < right[0]){
result.push(left.shift())
}else{
result.push(right.shift())
}
}
return result.concat(left).concat(right)
}
}