1、冒泡排序 2、快速排序 3、直接插入排序 4、希爾排序 5、直接選擇排序 ...
▓▓▓▓▓▓ 大致介紹
由於最近要考試複習，所以學習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 }
▓▓▓▓▓▓ 快速排序
快速排序（Quicksort）是對冒泡排序的一種改進。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數 據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。 一趟快速排序的演算法是： 1）設置兩個變數i、j，排序開始的時候：i=0，j=N-1； 2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]； 3）從j開始向前搜索，即由後開始向前搜索(j--)，找到第一個小於key的值A[j]，將A[j]和A[i]互換； 4）從i開始向後搜索，即由前開始向後搜索(i++)，找到第一個大於key的A[i]，將A[i]和A[j]互換； 5）重覆第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小於key,4中A[i]不大於key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為 止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令迴圈結束）。 快速排序的時間複雜度是O(n*logn) 代碼：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 }
▓▓▓▓▓▓ 插入排序
插入排序的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排序的序列中的適當位置，直到全部記錄插入完成為止，接下來介紹兩種常用的插入排序方法：直接插入排序和希爾排序
▓▓▓▓▓▓ 直接插入排序
直接插入排序(straight insertion sort)的做法是： 每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序。第一趟比較前兩個數，然後把第二個數按大小插入到有序表中； 第二趟把第 三個數據與前兩個數從後向前掃描，把第三個數按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以後就完成了整個排序過程。 直接插入排序的時間複雜度為
代碼：
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年提出 而得名。
希爾排序屬於插入類排序,是將整個有序序列分割成若幹小的子序列分別進行插入排序。 排序過程：先取一個正整數d1<n，把所有序號相隔d1的數組元素放一組，組內進行直接插入排序；然後取d2<d1，重覆上述分組和排序操作；直至di=1，即所有 記錄放進一 個組中排序為止。 希爾排序的時間複雜度為時間複雜度O(n*logn) 代碼：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 }
