JavaScript實現常用的排序演算法

▓▓▓▓▓▓ 大致介紹

　　由於最近要考試複習，所以學習js的時間少了 -_-||，考試完還會繼續的努力學習，這次用原生的JavaScript實現以前學習的常用的排序演算法，有冒泡排序、快速排序、直接插入排序、希爾排序、直接選擇排序

▓▓▓▓▓▓ 交換排序

　　交換排序是一類在排序過程中藉助於交換操作來完成排序的方法，基本思想是兩兩比較排序記錄的關鍵字，如果發現兩個關鍵字逆序，則將兩個記錄位置互換，重覆此過程，直到該排序列中所有關鍵字都有序為止，接下來介紹交換排序中常見的冒泡排序和快速排序

▓▓▓▓▓▓ 冒泡排序

　　冒泡排序的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端，故名

　　冒泡排序演算法的運作如下：（從後往前）
　　1、比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
　   2、對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
　　3、針對所有的元素重覆以上的步驟，除了最後一個。
　　4、持續每次對越來越少的元素重覆上面的步驟，直到沒有任何一對數字需要比較。

　　冒泡排序的時間複雜度是 O(n^2)

　　代碼：

 1         // 冒泡排序
 2         function bubbleSort(arr){
 3 
 4             for(var i=0;i<arr.length;i++){
 5                 for(var j=0;j<arr.length-i-1;j++){
 6                     if(arr[j] > arr[j+1]){
 7                         var arrMax = arr[j+1];
 8                         arr[j+1] = arr[j];
 9                         arr[j] = arrMax;
10                     }
11                 }
12             }
13 
14             return arr;
15         }

▓▓▓▓▓▓ 快速排序　

 1         // 快速排序
 2         function quickSort(arr){
 3             // 結束遞歸條件
 4             if(arr.length <= 1){
 5                 return arr;
 6             }
 7 
 8             var left = [];
 9             var right = [];
10             var key = arr[0];
11 
12             // 分組
13             for(var i=1;i<arr.length;i++){
14                 if(arr[i] < key){
15                     left.push(arr[i]);
16                 }else{
17                     right.push(arr[i]);
18                 }
19             }
20 
21             // 遞歸分組
22             return quickSort(left).concat(key,quickSort(right));
23         }

▓▓▓▓▓▓ 插入排序

　　插入排序的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排序的序列中的適當位置，直到全部記錄插入完成為止，接下來介紹兩種常用的插入排序方法：直接插入排序和希爾排序

▓▓▓▓▓▓ 直接插入排序

　　直接插入排序的時間複雜度為

 1         // 直接插入排序
 2         function insertSort(arr){
 3             // 預設第一個元素是有序的
 4             for(var i=1;i<arr.length;i++){
 5 
 6                 if(arr[i] < arr[i-1]){
 7                     var guard = arr[i];
 8                     var j = i - 1;
 9                     // 將有序數組擴大一位
10                     arr[i] = arr[j];
11 
12                     //遍歷有序組，找到自己的位置
13                     while(j >= 0 && guard < arr[j]){
14                         arr[j+1] = arr[j];
15                         j--;
16                     }
17 
18                     // 插入檢查的元素
19                     arr[j+1] = guard;
20                 }
21             }
22             return arr;
23         }

▓▓▓▓▓▓ 希爾排序

　　希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。該方法因DL．Shell於1959年提出      而得名。　　

 1         // 希爾排序
 2         function shellSort(arr){
 3             var len = arr.length;
 4             var stepLen = 1;
 5             // 確定首次遍歷的步長
 6             while(stepLen < len/3){
 7                 stepLen = 3*stepLen + 1;
 8             }
 9             // 開始遍歷
10             while(stepLen >= 1){
11                 for(var i=stepLen;i<len;i++){
12                     for(var j=i;j>=stepLen && arr[j] < arr[j-stepLen];j-=stepLen){
13                         swap(arr,j,j-stepLen);
14                     }
15                 }
16                 stepLen = (stepLen - 1)/3;
17             }
18 
19             return arr;
20         }
21 
22         function swap(arr,i,j){
23             var temp = arr[j];
24             arr[j] = arr[i];
25             arr[i] = temp;
26         }

▓▓▓▓▓▓ 選擇排序

　　選擇排序的基本思想是：每一趟排序在n-i+1個帶排序記錄中選出關鍵字最小的記錄，作為有序序列的第i個記錄，直到全部記錄排序完畢。常用的排序方法有直接選擇排序和堆排序(由於js不能很好的體現堆排序的特點就不寫了)

▓▓▓▓▓▓ 直接選擇排序

　　基本思想是：第一次從R[0]~R[n-1]中選取最小值，與R[0]交換，第二次從R[1]~R[n-1]中選取最小值，與R[1]交換，....，第i次從R[i-1]~R[n-1]中選取最小值，與R[i-1]交換，.....，第n-1次從R[n-2]~R[n-1]中選取最小值，與R[n-2]交換，總共通過n-1次，得到一個按排序碼從小到大排列的有序序列

　　直接選擇排序的時間複雜度：O(n^2)

　　代碼：

 1         // 直接選擇排序
 2         function straightSelectSort(arr){
 3             // 預設第一個元素是最小的
 4             var min;
 5             var k;
 6             var lArr = [];
 7             for(var i=0;i<arr.length-1;i++){
 8                 min = arr[i];
 9                 k = i;
10                 for(var j=i+1;j<arr.length;j++){
11                     if(arr[j] < min){
12                         min = arr[j];
13                         k = j;
14                     }
15                 }
16                 if(k != i){
17                     arr[k] = arr[i];
18                     arr[i] = min;
19                 }
20             }
21             return arr;
22         }