专栏首页Micro_awake webJavaScript实现八大内部排序算法

JavaScript实现八大内部排序算法

注:基数排序中:r是关键字的基数,d是长度,n是关键字的个数

1.插入排序

基本思想:在序号i之前的元素(0到i-1)已经排好序,本趟需要找到i对应的元素x (此时即arr[i]) 的正确位置k,在寻找位置k的过程中与序号i-1到0的元素依次进行比较。如果x小于比较元素,则比较元素向后移动一位;否则,结束移位,将x插入当前位置k

 1 function insertSort(arr) {
 2   for (let i = 1; i < arr.length; i++) {
 3     // 将待插入元素提取出来
 4     let temp = arr[i]
 5     let j
 6     for (j = i - 1; j >= 0; j--) {
 7       if (arr[j] > temp) {
 8         // 插入元素小于比较元素,比较元素则向后移动一位
 9         arr[j + 1] = arr[j]
10       } else {
11         // 否则,结束移位
12         break
13       }
14     }
15     //将插入元素插入正确位置
16     arr[j + 1] = temp
17   }
18   return arr
19 }
20 console.log(insertSort([7, 3, 4, 5, 10, 7, 8, 2]))

1.1插入排序的优化二分排序

与插入排序思想差不多,但是二分排序是在插入第i个元素时,对前面的0~i-1元素进行折半,先跟它们中间的元素进行比较。如果小,那么对前半进行折半;如果打,那么对后半进行折半。依次进行,直到left>right。然后再把第i个元素前一位与目标位置之间的所有元素向后移动一位,再将目标元素放入正确位置上。

 1 function binarySort(arr) {
 2   for (let i = 0; i < arr.length; i++) {
 3     let temp = arr[i]
 4     let left = 0
 5     let right = i - 1
 6     let mid
 7     while (left <= right) {
 8       mid = Math.floor((left + right) / 2)
 9       if (arr[mid] > temp) {
10         right = mid - 1
11       } else {
12         left = mid + 1
13       }
14     }
15     for (let j = i - 1; j >= left; j--) {
16       arr[j + 1] = arr[j]
17     }
18     if (left !== i) {
19       arr[left] = temp
20     }
21   }
22   return arr
23 }
24 console.log(binarySort([7, 3, 4, 5, 10, 7, 8, 2]))

2.希尔排序

基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

 1 function shellSort(arr) {
 2   let d = arr.length
 3   while (true) {
 4     d = Math.floor(d / 2)
 5     for (let x = 0; x < d; x++) {
 6       for (let i = x + d; i < arr.length; i = i + d) {
 7         let temp = arr[i]
 8         let j
 9         for (j = i - d; j >= 0 && arr[j] > temp; j = j - d) {
10           arr[j + d] = arr[j]
11         }
12         arr[j + d] = temp
13       }
14     }
15     if (d == 1) {
16       break
17     }
18   }
19   return arr
20 }
21 console.log(shellSort([7, 3, 4, 5, 10, 7, 8, 2]))

3.直接选择排序

基本思想:每次选择待排序的元素中最小的值,放置在序列的首位

 1 function directSelectSort(arr) {
 2   for (let i = 0; i < arr.length; i++) {
 3     let min = arr[i]
 4     let index = i
 5     for (let j = i + 1; j < arr.length; j++) {
 6       if (arr[j] < min) {
 7         // 找到最小值,并标注最小值索引,方便后续与元素arr[i]交换位置
 8         min = arr[j]
 9         index = j
10       }
11     }
12     arr[index] = arr[i]
13     arr[i] = min
14   }
15   return arr
16 }
17 console.log(directSelectSort([7, 3, 4, 5, 10, 7, 8, 2]))

4.堆排序

堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单

用大根堆排序的基本思想

① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区

② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key

③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。……

直到无序区只有一个元素为止。

 1 let len
 2 
 3 function buildMaxHeap(arr) {
 4   //建立大根堆
 5   len = arr.length
 6   for (let i = Math.floor(len / 2); i >= 0; i--) {
 7     heapify(arr, i)
 8   }
 9 }
10 
11 function heapify(arr, i) {
12   //堆调整
13   let left = 2 * i + 1,
14     right = 2 * i + 2,
15     largest = i
16 
17   if (left < len && arr[left] > arr[largest]) {
18     largest = left
19   }
20 
21   if (right < len && arr[right] > arr[largest]) {
22     largest = right
23   }
24 
25   if (largest !== i) {
26     // 解构赋值,交换变量
27     ;[arr[i], arr[largest]] = [arr[largest], arr[i]]
28     heapify(arr, largest)
29   }
30 }
31 
32 function heapSort(arr) {
33   buildMaxHeap(arr)
34 
35   for (let i = arr.length - 1; i > 0; i--) {
36     ;[arr[0], arr[i]] = [arr[i], arr[0]]
37     len--
38     heapify(arr, 0)
39   }
40   return arr
41 }
42 
43 console.log(heapSort([7, 3, 4, 5, 10, 7, 8, 2]))

5.冒泡排序

基本思想:每次比较两相邻的数,当发现它们的排序与排序要求相反时,就将它们互换。这样小的数往下沉,大的数往上冒

 1 function bubbleSort(arr) {
 2   for (let i = 0; i < arr.length; i++) {
 3     // 因为每次比较时都已经有i个元素沉下去了,所以j<arr.length-1-i
 4     for (let j = 0; j < arr.length - 1 - i; j++) {
 5       if (arr[j] > arr[j + 1]) {
 6         // 这里采用了解构赋值。如果一般做法,借助临时变量,则辅助空间是O(1)
 7         ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
 8       }
 9     }
10   }
11   return arr
12 }
13 console.log(bubbleSort([7, 3, 4, 5, 10, 7, 8, 2]))

6.快速排序

基本思想:选择一个基准元素(通常选择第一个元素),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有元素都比基准元素小,另外一部分的所有元素大于或等于基准元素大。同样方法依次分割;整个排序过程可以递归进行。

 1 let quicksort = function(arr) {
 2   if(arr.length <= 1) return arr;
 3 
 4   let pivot = Math.floor((arr.length -1)/2);
 5   let val = arr[pivot], less = [], more = [];
 6 
 7   arr.splice(pivot, 1);
 8   arr.forEach(function(e,i,a){
 9     e < val ? less.push(e) : more.push(e);
10   });
11 
12   return (quicksort(less)).concat([val],quicksort(more))
13 }
14 console.log(quicksort([7, 3, 4, 5, 10, 7, 8, 2]))

7.归并排序

基本思想:将待排序序列分为若干个子序列,每个子序列是有序的,然后将有序子序列合并为整体有序序列。

 1 function merge(left, right) {
 2   let result = []
 3   while (left.length > 0 && right.length > 0) {
 4     if (left[0] < right[0]) {
 5       /*shift()方法用于把数组的第一个元素从其中删除,并返回第一个元素的值。*/
 6       result.push(left.shift())
 7     } else {
 8       result.push(right.shift())
 9     }
10   }
11   return result.concat(left).concat(right)
12 }
13 function mergeSort(arr) {
14   if (arr.length == 1) {
15     return arr
16   }
17   let middle = Math.floor(arr.length / 2),
18     left = arr.slice(0, middle),
19     right = arr.slice(middle)
20   return merge(mergeSort(left), mergeSort(right))
21 }
22 console.log(mergeSort([7, 3, 4, 5, 10, 7, 8, 2]))

8.基数排序

基本思想:将所有待比较元素(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从个位开始,进行排序;然后十位,进行排序;以此进行!这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

基数排序两种方法:

MSD 从高位开始进行排序

LSD 从低位开始进行排序

 1 // LSD Radix Sort
 2 // helper function to get the last nth digit of a number
 3 var getDigit = function(num,nth){
 4   // get last nth digit of a number
 5   var ret = 0;
 6   while(nth--){
 7     ret = num % 10
 8     num = Math.floor((num - ret) / 10)
 9   }
10   return ret
11 }
12 
13 // radixSort
14 function radixSort(arr){
15   var max = Math.floor(Math.log10(Math.max.apply(Math,arr))),  
16       // get the length of digits of the max value in this array
17       digitBuckets = [],
18       idx = 0;
19 
20   for(var i = 0;i<max+1;i++){
21 
22     // rebuild the digit buckets according to this digit
23     digitBuckets = []
24     for(var j = 0;j<arr.length;j++){
25       var digit = getDigit(arr[j],i+1);
26 
27       digitBuckets[digit] = digitBuckets[digit] || [];
28       digitBuckets[digit].push(arr[j]);
29     }
30 
31     // rebuild the arr according to this digit
32     idx = 0
33     for(var t = 0; t< digitBuckets.length;t++){
34       if(digitBuckets[t] && digitBuckets[t].length > 0){
35         for(j = 0;j<digitBuckets[t].length;j++){
36           arr[idx++] = digitBuckets[t][j];
37         }
38       }
39     }
40   }
41   return arr
42 }
43 console.log(radixSort([7, 3, 4, 5, 10, 7, 8, 2]))

注:网上有很多javascript实现的基数排序代码时错误的

当搜索一些问题时,尽量使用英文进行搜索!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JQuery基础

    学习jQuery的时候,很快过了一遍,发现好多知识点不清晰。看来还是要写出来加深印象,平时多练习! jQuery是一个Javascript函数库,轻量级,“写得...

    用户1149564
  • vue的计算属性computed和监听器watch

    用户1149564
  • es6(四):Symbol,Set,Map

    1.Symbol: Symbol中文意思“象征” Symbol:这是一种新的原始类型的值,表示独一无二的值(可以保证不与其它属性名冲突) Symbol()函数前...

    用户1149564
  • [PHP] 算法-把数组排成最小的数的PHP实现

    陶士涵
  • 常用算法比较,js实现

    <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> <style>...

    前朝楚水
  • 冒泡排序

    生活中,好奇的人们靠近池塘发现,鱼儿冒气泡,越往上气泡越大,似乎扔一块石头下去,也能有类似的效果。我们总结出一个规律就是从池塘底部到池塘表面它的气泡是由小到大排...

    丰臣正一
  • Python实现6种排序算法,快排只有6行?

    小萌哥
  • LeetCode 1243. 数组变换

    首先,给你一个初始数组 arr。然后,每天你都要根据前一天的数组生成一个新的数组。

    Michael阿明
  • LeetCode 1228. 等差数列中缺失的数字

    我们会从该数组中删除一个 既不是第一个 也 不是最后一个的值,得到一个新的数组 arr。

    Michael阿明
  • LeetCode 1346. 检查整数及其两倍数是否存在(哈希)

    给你一个整数数组 arr,请你检查是否存在两个整数 N 和 M,满足 N 是 M 的两倍(即,N = 2 * M)。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券