[参考博客](https://www.cnblogs.com/why-not-try/p/8098757.html)  https://leetcode-cn.com/problems/sort-an-array/solution/fu-xi-ji-chu-pai-xu-suan-fa-java-by-liweiwei1419/ <hr> <div id="div1"><h3> <font color=red > 希尔排序 </font><h3></div>  第一层循环：将gap依次折半，对序列进行分组，直到gap=1 第二、三层循环：也即直接插入排序所需要的两次循环。 ```javascript function shellSort(arr) { let d = arr.length while (true) { d = Math.floor(d / 2) for (let x = 0; x < d; x++) { for (let i = x + d; i < arr.length; i = i + d) { let temp = arr[i] let j for (j = i - d; j >= 0 && arr[j] > temp; j = j - d) { arr[j + d] = arr[j] } arr[j + d] = temp } } if (d == 1) { break } } return arr } console.log(shellSort([7, 3, 4, 5, 10, 7, 8, 2])) ``` <hr> <div id="div1"><h3> <font color=red > 简单选择排序 </font><h3></div> 第一层循环：依次遍历序列当中的每一个元素 第二层循环：将遍历得到的当前元素依次与余下的元素进行比较，符合最小元素的条件，则交换。 ```javascript function directSelectSort(arr) { for (let i = 0; i < arr.length; i++) { let min = arr[i] let index = i for (let j = i + 1; j < arr.length; j++) { if (arr[j] < min) { // 找到最小值，并标注最小值索引，方便后续与元素arr[i]交换位置 min = arr[j] index = j } } arr[index] = arr[i] arr[i] = min } return arr } console.log(directSelectSort([7, 3, 4, 5, 10, 7, 8, 2])) ``` <hr> <div id="div1"><h3> <font color=red > 堆排序 </font><h3></div> 大顶堆要求节点的元素都要大于其孩子，小顶堆要求节点元素都小于其左右孩子 <hr> <div id="div1"><h3> <font color=red > 冒泡排序 </font><h3></div> 将序列当中的左右元素，依次比较，保证右边的元素始终大于左边的元素； （ 第一轮结束后，序列最后一个元素一定是当前序列的最大值；） 对序列当中剩下的n-1个元素再次执行步骤1。 ```javascript function bubbleSort(arr) { for (let i = 0; i < arr.length; i++) { // 因为每次比较时都已经有i个元素沉下去了，所以j<arr.length-1-i for (let j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { // 这里采用了解构赋值。如果一般做法，借助临时变量，则辅助空间是O(1) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] } } } return arr } console.log(bubbleSort([7, 3, 4, 5, 10, 7, 8, 2])) ``` <hr> <div id="div1"><h3> <font color=red > 快速排序 </font><h3></div> 选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。 >1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。 2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。 3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。 4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中 ```javascript let quicksort = function(arr) { if(arr.length <= 1) return arr; let pivot = Math.floor((arr.length -1)/2); let val = arr[pivot], less = [], more = []; arr.splice(pivot, 1); arr.forEach(function(e,i,a){ e < val ? less.push(e) : more.push(e); }); return (quicksort(less)).concat([val],quicksort(more)) } console.log(quicksort([7, 3, 4, 5, 10, 7, 8, 2])) ``` <hr> <div id="div1"><h3> <font color=red > 归并排序 </font><h3></div> 分解----将序列每次折半拆分 合并----将划分后的序列段两两排序合并 ```javascript 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()) } } return result.concat(left).concat(right) } function mergeSort(arr) { if (arr.length == 1) { return arr } let middle = Math.floor(arr.length / 2), left = arr.slice(0, middle), right = arr.slice(middle) return merge(mergeSort(left), mergeSort(right)) } console.log(mergeSort([7, 3, 4, 5, 10, 7, 8, 2])) ``` <hr> <div id="div1"><h3> <font color=red > 基数排序 </font><h3></div> 将所有待比较元素（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从个位开始，进行排序；然后十位，进行排序；以此进行！这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。 基数排序两种方法： MSD 从高位开始进行排序 LSD 从低位开始进行排序 ```javascript // LSD Radix Sort // helper function to get the last nth digit of a number var getDigit = function(num,nth){ // get last nth digit of a number var ret = 0; while(nth--){ ret = num % 10 num = Math.floor((num - ret) / 10) } return ret } // radixSort function radixSort(arr){ var max = Math.floor(Math.log10(Math.max.apply(Math,arr))), // get the length of digits of the max value in this array digitBuckets = [], idx = 0; for(var i = 0;i<max+1;i++){ // rebuild the digit buckets according to this digit digitBuckets = [] for(var j = 0;j<arr.length;j++){ var digit = getDigit(arr[j],i+1); digitBuckets[digit] = digitBuckets[digit] || []; digitBuckets[digit].push(arr[j]); } // rebuild the arr according to this digit idx = 0 for(var t = 0; t< digitBuckets.length;t++){ if(digitBuckets[t] && digitBuckets[t].length > 0){ for(j = 0;j<digitBuckets[t].length;j++){ arr[idx++] = digitBuckets[t][j]; } } } } return arr } console.log(radixSort([7, 3, 4, 5, 10, 7, 8, 2])) ```