冒泡排序
思路：重復遍歷數(shù)組中的元素，依次比較兩個相鄰的元素，如果前一個元素大于后一個元素，就依靠第三個變量將它們換過來，直到所有元素遍歷完。
function bubbleSort(arr){
? ? ? ? ? for(let i = 0; i < arr.length - 1; i ++){
? ? ? ? ? ? ? ? for(let j = 0; j < arr.length - 1 - i; j ++){
? ? ? ? ? ? ? ? ? ? ? if(arr[j] > arr[j+1]){? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? let tem = arr[j];
? ? ? ? ? ? ? ? ? ? ? ? ? ? arr[j] = arr[j+1];
? ? ? ? ? ? ? ? ? ? ? ? ? ? arr[j+1] = tem;
? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? ? ? console.log(arr);
? ? }
? ? bubbleSort([2,5,6,1,2,9,4,6,3]);? ? // output：[1, 2, 2, 3, 4, 5, 6, 6, 9]
選擇排序
思路：每一次從數(shù)組中選出最小的一個元素，存放在數(shù)組的起始位置，然后，再從剩余未排序的數(shù)組中繼續(xù)尋找最小元素，然后放到已排序序列的末尾。直到全部數(shù)據(jù)元素排完。
function selectSort(arr){
? ? ? ? ? let min = 0; // 用來保存數(shù)組中最小的數(shù)的索引值
? ? ? ? ? for(let i = 0; i < arr.length - 1; i ++){
? ? ? ? ? ? ? ? min = i;
? ? ? ? ? ? ? ? for(let j = i + 1; j < arr.length; j ++){
? ? ? ? ? ? ? ? ? ? ? if(arr[j] < arr[min]){
? ? ? ? ? ? ? ? ? ? ? ? ? ? min = j;
? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? if(min != i){
? ? ? ? ? ? ? ? ? ? ? swap(arr,i,min);
? ? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? ? ? console.log(arr);
? ? };
? ? function swap(arr,index1,index2){?
? ? let tem = arr[index1];
? ? ? ? ? arr[index1] = arr[index2];
? ? ? ? ? arr[index2] = tem;
? ? }
? ? selectSort([7,5,1,2,6,4,8,3,2]);? ? // output： [1, 2, 2, 3, 4, 5, 6, 7, 8]
插入排序
插入算法的工作原理就是對已排序數(shù)據(jù)序列從后向前掃描，將未排序數(shù)據(jù)找到對應的位置并插入。
思路：
（1）從第一個元素開始，該元素可以被認為已經被排序了；
（2）取出下一個元素，在已經排好序的序列中從后往前掃描；
（3）直到找到小于或等于該元素的位置；
（4）將該位置后面的所有已排序的元素從后往前依次向后移一位；
（5）將該元素插入到該位置；
（6）重復步驟 2-5；
function insertSort(arr){
? ? ? ? ? for(let i = 1; i < arr.length; i ++){
? ? ? ? ? ? ? ? let j = i,? ? ? ? ? ? key = arr[j];
? ? ? ? ? ? ? ? while( --j > -1 ){
? ? ? ? ? ? ? ? ? ? ? if(arr[j] > key){
? ? ? ? ? ? ? ? ? ? ? ? arr[j + 1] = arr[j];
? ? ? ? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? arr[j + 1] = key;
? ? ? ? ? }
? ? ? ? ? console.log(arr);
? ? }
? ? insertSort([12,25,41,2,3,15]); // output：[2, 3, 12, 15, 25, 41]
希爾排序
希爾排序是插入排序的一種，又稱“縮小增量排序”，是直接插入排序算法的一種更高效的改進版本。
思路：把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個數(shù)據(jù)列恰好被分成一組，算法便終止。
function shellSort(arr){
? ? ? ? ? let gaps = [5, 3, 1];
? ? ? ? ? for (let g = 0; g < gaps.length; ++g) {
? ? ? ? ? ? ? ? for (let i = gaps[g]; i < arr.length; ++i) {
? ? ? ? ? ? ? ? ? ? ? let temp = arr[i];
? ? ? ? ? ? ? ? ? j = i；
? ? ? ? ? ? ? ? ? ? ? for (j; j >= gaps[g] && arr[j - gaps[g]] > temp; j -= gaps[g]) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? arr[j] = arr[j - gaps[g]];
? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? arr[j] = temp;
? ? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? ? ? console.log(arr);
? ? }
? ? shellSort([12,21,32,14,15,18]); output：[12, 14, 15, 18, 21, 32]
歸并排序
歸并排序是建立在歸并操作上的一種有效排序算法，該算法是采用分治法的一個非常典型的應用。即先進行劃分，然后再進行合并。
思路：假設對一個數(shù)組 C 進行歸并排序，步驟如下
（1）先將 C 劃分為兩個數(shù)組 A 和 B（即把數(shù)組 C 從中間分開）
（2）再分別對數(shù)組 A、B 重復步驟1的操作，逐步劃分，直到不能再劃分為止（每個子分組只剩下一個元素），至此劃分結束。
（3）然后從下層往上層不斷合并數(shù)組，每一層合并相鄰的兩個子數(shù)組。合并的過程是每次從待合并的兩個子數(shù)組中選取一個最小的元素，然后把這個元素放到合并后的數(shù)組中，不斷重復直到把兩個子數(shù)組的元素都放到合并后的數(shù)組為止。
（4）以此類推，直到合并到最上層結束，這時數(shù)據(jù)的排序已經完成。
function merge(left, right) {
? ? ? ? let result = [];
? ? ? ? while(left.length > 0 && right.length > 0) {
? ? ? ? ? ? ? if(left[0] < right[0]) {
? ? ? ? ? ? ? ? ? ? result.push(left.shift());
? ? ? ? ? ? ? }? ? ? else {
? ? ? ? ? ? ? ? ? ? ? result.push(right.shift());
? ? ? ? ? ? ? }
? ? ? ? }
? /* 當左右數(shù)組長度不等.將比較完后剩下的數(shù)組項鏈接起來即可 */
? ? ? ? return result.concat(left).concat(right);
? }
? function mergeSort(arr){
? ? ? ? if(arr.length == 1){
? ? ? ? ? ? ? return arr;
? ? ? ? };
? ? ? ? let mid = Math.floor( arr.length/2 );
? ? ? ? let left_arr = arr.slice(0, mid),
? ? ? ? ? ? ? ? right_arr = arr.slice( mid );
? ? ? ? return merge( mergeSort(left_arr), mergeSort(right_arr) );
? }
? console.log(mergeSort([12,20,30,21,15,33,26,19,40,25])); output：[12, 15, 19, 20, 21, 25, 26, 30, 33, 40]
快速排序
對冒泡排序的一種改進。通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都比另一部分的所有數(shù)據(jù)小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。
思路：
（1）找基準（一般以中間項為基準）
（2）遍歷數(shù)組，小于基準的放在 left，大于基準的放在 right
（3）遞歸
function quickSort(arr){
? ? if(arr.length<=1){return arr;}? ? //如果數(shù)組<=1,則直接返回
? ? let pivotIndex = Math.floor(arr.length/2);? ?
? ? let pivot = arr.splice(pivotIndex,1)[0]; //找基準，并把基準從原數(shù)組刪除
? ? let left=[], right=[];? ? //定義左右數(shù)組
? ? for(let i=0; i<arr.length; i++){? ? ? ? //比基準小的放在left，比基準大的放在right
? ? ? ? if(arr[i] <= pivot){
? ? ? ? ? ? left.push(arr[i]);? ?
? ? ? ? } else {?
? ? ? ? right.push(arr[i]);
? ? ? ? }
? ? }
? ? return quickSort(left).concat([pivot],quickSort(right));? ? //遞歸
}
console.log(quickSort([5,3,4,8,6,9,12]));? // output：[3, 4, 5, 6, 8, 9, 12]
效率比較：
