JavaScript十大排序的算法是什么
这篇文章主要讲解了"JavaScript十大排序的算法是什么"，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习"JavaScript十大排序的算法是什么"吧！
冒泡排序
通过相邻元素的比较和交换，使得每一趟循环都能找到未有序数组的最大值或最小值。
最好：O(n)，只需要冒泡一次数组就有序了。
最坏：O(n²)
平均：O(n²)
单向冒泡
1. function bubbleSort(nums) { 2. for(let i=0, len=nums.length; i nums[j+1]) { 7. [nums[j], nums[j+1]] = [nums[j+1], nums[j]]; 8. mark = false; 9. } 10. } 11. if(mark) return; 12. } 13. } 一个人学习会有迷茫，动力不足。这里推荐一下我的前端学习交流群：731771211 ，里面都是学习前端的，如果你想制作酷炫的网页，想学习编程。自己整理了一份2019最全面前端学习资料，从最基础的HTML+CSS+JS【炫酷特效，游戏，插件封装，设计模式】到移动端HTML5的项目实战的学习资料都有整理，送给每一位前端小伙伴，有想学习web前端的，或是转行，或是大学生，还有工作中想提升自己能力的，正在学习的小伙伴欢迎加入学习。
双向冒泡
普通的冒泡排序在一趟循环中只能找出一个最大值或最小值，双向冒泡则是多一轮循环既找出最大值也找出最小值。
1. function bubbleSort_twoWays(nums) { 2. let low = 0; 3. let high = nums.length - 1; 4. while(low < high) { 5. let mark = true; 6. // 找到最大值放到右边 7. for(let i=low; i nums[i+1]) { 9. [nums[i], nums[i+1]] = [nums[i+1], nums[i]]; 10. mark = false; 11. } 12. } 13. high--; 14. // 找到最小值放到左边 15. for(let j=high; j>low; j--) { 16. if(nums[j] < nums[j-1]) { 17. [nums[j], nums[j-1]] = [nums[j-1], nums[j]]; 18. mark = false; 19. } 20. } 21. low++; 22. if(mark) return; 23. } 24. } 选择排序
和冒泡排序相似，区别在于选择排序是将每一个元素和它后面的元素进行比较和交换。
最好：O(n²)
最坏：O(n²)
平均：O(n²)
1. function selectSort(nums) { 2. for(let i=0, len=nums.length; i nums[j]) { 5. [nums[i], nums[j]] = [nums[j], nums[i]]; 6. } 7. } 8. } 9. } 插入排序
以第一个元素作为有序数组，其后的元素通过在这个已有序的数组中找到合适的位置并插入。
最好：O(n)，原数组已经是升序的。
最坏：O(n²)
平均：O(n²)
1. function insertSort(nums) { 2. for(let i=1, len=nums.length; i= 0 && temp < nums[j-1]) { 6. nums[j] = nums[j-1]; 7. j--; 8. } 9. nums[j] = temp; 10. } 11. } 快速排序
选择一个元素作为基数（通常是第一个元素），把比基数小的元素放到它左边，比基数大的元素放到它右边（相当于二分），再不断递归基数左右两边的序列。
最好：O(n * logn)，所有数均匀分布在基数的两边，此时的递归就是不断地二分左右序列。
最坏：O(n²)，所有数都分布在基数的一边，此时划分左右序列就相当于是插入排序。
平均：O(n * logn)
快速排序之填坑
从右边向中间推进的时候，遇到小于基数的数就赋给左边（一开始是基数的位置），右边保留原先的值等之后被左边的值填上。
1. function quickSort(nums) { 2. // 递归排序基数左右两边的序列 3. function recursive(arr, left, right) { 4. if(left >= right) return; 5. let index = partition(arr, left, right); 6. recursive(arr, left, index - 1); 7. recursive(arr, index + 1, right); 8. return arr; 9. } 10. // 将小于基数的数放到基数左边，大于基数的数放到基数右边，并返回基数的位置 11. function partition(arr, left, right) { 12. // 取第一个数为基数 13. let temp = arr[left]; 14. while(left < right) { 15. while(left < right && arr[right] >= temp) right--; 16. arr[left] = arr[right]; 17. while(left < right && arr[left] < temp) left++; 18. arr[right] = arr[left]; 19. } 20. // 修改基数的位置 21. arr[left] = temp; 22. return left; 23. } 24. recursive(nums, 0, nums.length-1); 25. }快速排序之交换
从左右两边向中间推进的时候，遇到不符合的数就两边交换值。
1. function quickSort1(nums) { 2. function recursive(arr, left, right) { 3. if(left >= right) return; 4. let index = partition(arr, left, right); 5. recursive(arr, left, index - 1); 6. recursive(arr, index + 1, right); 7. return arr; 8. } 9. function partition(arr, left, right) { 10. let temp = arr[left]; 11. let p = left + 1; 12. let q = right; 13. while(p <= q) { 14. while(p <= q && arr[p] < temp) p++; 15. while(p <= q && arr[q] > temp) q--; 16. if(p <= q) { 17. [arr[p], arr[q]] = [arr[q], arr[p]]; 18. // 交换值后两边各向中间推进一位 19. p++; 20. q--; 21. } 22. } 23. // 修改基数的位置 24. [arr[left], arr[q]] = [arr[q], arr[left]]; 25. return q; 26. } 27. recursive(nums, 0, nums.length-1); 28. }归并排序
递归将数组分为两个序列，有序合并这两个序列。
最好：O(n * logn)
最坏：O(n * logn)
平均：O(n * logn)
1. function mergeSort(nums) { 2. // 有序合并两个数组 3. function merge(l1, r1, l2, r2) { 4. let arr = []; 5. let index = 0; 6. let i = l1, j = l2; 7. while(i <= r1 && j <= r2) { 8. arr[index++] = nums[i] < nums[j] ? nums[i++] : nums[j++]; 9. } 10. while(i <= r1) arr[index++] = nums[i++]; 11. while(j <= r2) arr[index++] = nums[j++]; 12. // 将有序合并后的数组修改回原数组 13. for(let t=0; t= right) return; 20. // 比起(left+right)/2，更推荐下面这种写法，可以避免数溢出 21. let mid = parseInt((right - left) / 2) + left; 22. recursive(left, mid); 23. recursive(mid+1, right); 24. merge(left, mid, mid+1, right); 25. return nums; 26. } 27. recursive(0, nums.length-1); 28. } 桶排序
取 n 个桶，根据数组的最大值和最小值确认每个桶存放的数的区间，将数组元素插入到相应的桶里，最后再合并各个桶。
最好：O(n)，每个数都在分布在一个桶里，这样就不用将数插入排序到桶里了(类似于计数排序以空间换时间)。
最坏：O(n²)，所有的数都分布在一个桶里。
平均：O(n + k)，k表示桶的个数。
1. function bucketSort(nums) { 2. // 桶的个数，只要是正数即可 3. let num = 5; 4. let max = Math.max(...nums); 5. let min = Math.min(...nums); 6. // 计算每个桶存放的数值范围，至少为1， 7. let range = Math.ceil((max - min) / num) || 1; 8. // 创建二维数组，第一维表示第几个桶，第二维表示该桶里存放的数 9. let arr = Array.from(Array(num)).map(() => Array().fill(0)); 10. nums.forEach(val => { 11. // 计算元素应该分布在哪个桶 12. let index = parseInt((val - min) / range); 13. // 防止index越界，例如当[5,1,1,2,0,0]时index会出现5 14. indexindex = index >= num ? num - 1 : index; 15. let temp = arr[index]; 16. // 插入排序，将元素有序插入到桶中 17. let j = temp.length - 1; 18. while(j >= 0 && val < temp[j]) { 19. temp[j+1] = temp[j]; 20. j--; 21. } 22. temp[j+1] = val; 23. }) 24. // 修改回原数组 25. let res = [].concat.apply([], arr); 26. nums.forEach((val, i) => { 27. nums[i] = res[i]; 28. }) 29. }基数排序
使用十个桶 0-9，把每个数从低位到高位根据位数放到相应的桶里，以此循环最大值的位数次。但只能排列正整数，因为遇到负号和小数点无法进行比较。
最好：O(n * k)，k表示最大值的位数。
最坏：O(n * k)
平均：O(n * k)
1. function radixSort(nums) { 2. // 计算位数 3. function getDigits(n) { 4. let sum = 0; 5. while(n) { 6. sum++; 7. n = parseInt(n / 10); 8. } 9. return sum; 10. } 11. // 第一维表示位数即0-9，第二维表示里面存放的值 12. let arr = Array.from(Array(10)).map(() => Array()); 13. let max = Math.max(...nums); 14. let maxDigits = getDigits(max); 15. for(let i=0, len=nums.length; i=0; i--) { 24. // 循环每一个桶 25. for(let j=0; j<=9; j++) { 26. let temp = arr[j] 27. let len = temp.length; 28. // 根据当前的位数i把桶里的数放到相应的桶里 29. while(len--) { 30. let str = temp[0]; 31. temp.shift(); 32. arr[str[i]].push(str); 33. } 34. } 35. } 36. // 修改回原数组 37. let res = [].concat.apply([], arr); 38. nums.forEach((val, index) => { 39. nums[index] = +res[index]; 40. }) 41. } 计数排序
以数组元素值为键，出现次数为值存进一个临时数组，最后再遍历这个临时数组还原回原数组。因为 JavaScript 的数组下标是以字符串形式存储的，所以计数排序可以用来排列负数，但不可以排列小数。
最好：O(n + k)，k是最大值和最小值的差。
最坏：O(n + k)
平均：O(n + k)
1. function countingSort(nums) { 2. let arr = []; 3. let max = Math.max(...nums); 4. let min = Math.min(...nums); 5. // 装桶 6. for(let i=0, len=nums.length; i 0) { 14. nums[index++] = i; 15. arr[i]--; 16. } 17. } 18. } 计数排序优化
把每一个数组元素都加上 min 的相反数，来避免特殊情况下的空间浪费，通过这种优化可以把所开的空间大小从 max+1 降低为 max-min+1，max 和 min 分别为数组中的最大值和最小值。
比如数组 [103, 102, 101, 100]，普通的计数排序需要开一个长度为 104 的数组，而且前面 100 个值都是 undefined，使用该优化方法后可以只开一个长度为 4 的数组。
1. function countingSort(nums) { 2. let arr = []; 3. let max = Math.max(...nums); 4. let min = Math.min(...nums); 5. // 加上最小值的相反数来缩小数组范围 6. let add = -min; 7. for(let i=0, len=nums.length; i 0) { 16. nums[index++] = i; 17. temp--; 18. } 19. } 20. } 堆排序
根据数组建立一个堆（类似完全二叉树），每个结点的值都大于左右结点（最大堆，通常用于升序），或小于左右结点（最小堆，通常用于降序）。对于升序排序，先构建最大堆后，交换堆顶元素（表示最大值）和堆底元素，每一次交换都能得到未有序序列的最大值。重新调整最大堆，再交换堆顶元素和堆底元素，重复 n-1 次后就能得到一个升序的数组。
最好：O(n * logn)，logn是调整最大堆所花的时间。
最坏：O(n * logn)
平均：O(n * logn)
1. function heapSort(nums) { 2. // 调整最大堆，使index的值大于左右节点 3. function adjustHeap(nums, index, size) { 4. // 交换后可能会破坏堆结构，需要循环使得每一个父节点都大于左右结点 5. while(true) { 6. let max = index; 7. let left = index * 2 + 1; // 左节点 8. let right = index * 2 + 2; // 右节点 9. if(left < size && nums[max] < nums[left]) max = left; 10. if(right < size && nums[max] < nums[right]) max = right; 11. // 如果左右结点大于当前的结点则交换，并再循环一遍判断交换后的左右结点位置是否破坏了堆结构（比左右结点小了） 12. if(index !== max) { 13. [nums[index], nums[max]] = [nums[max], nums[index]]; 14. index = max; 15. } 16. else { 17. break; 18. } 19. } 20. } 21. // 建立最大堆 22. function buildHeap(nums) { 23. // 注意这里的头节点是从0开始的，所以最后一个非叶子结点是 parseInt(nums.length/2)-1 24. let start = parseInt(nums.length / 2) - 1; 25. let size = nums.length; 26. // 从最后一个非叶子结点开始调整，直至堆顶。 27. for(let i=start; i>=0; i--) { 28. adjustHeap(nums, i, size); 29. } 30. } 31. buildHeap(nums); 32. // 循环n-1次，每次循环后交换堆顶元素和堆底元素并重新调整堆结构 33. for(let i=nums.length-1; i>0; i--) { 34. [nums[i], nums[0]] = [nums[0], nums[i]]; 35. adjustHeap(nums, 0, i); 36. } 37. }希尔排序
通过某个增量 gap，将整个序列分给若干组，从后往前进行组内成员的比较和交换，随后逐步缩小增量至 1。希尔排序类似于插入排序，只是一开始向前移动的步数从 1 变成了 gap。
最好：O(n * logn)，步长不断二分。
最坏：O(n * logn)
平均：O(n * logn)
1. function shellSort(nums) { 2. let len = nums.length; 3. // 初始步数 4. let gap = parseInt(len / 2); 5. // 逐渐缩小步数 6. while(gap) { 7. // 从第gap个元素开始遍历 8. for(let i=gap; i=0; j-=gap) { 11. if(nums[j] > nums[j+gap]) { 12. [nums[j], nums[j+gap]] = [nums[j+gap], nums[j]]; 13. } 14. else { 15. break; 16. } 17. } 18. } 19. gap = parseInt(gap / 2); 20. } 21. } 感谢各位的阅读，以上就是"JavaScript十大排序的算法是什么"的内容了，经过本文的学习后，相信大家对JavaScript十大排序的算法是什么这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是，小编将为大家推送更多相关知识点的文章，欢迎关注！
