javascript排序算法实现：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序

你的名字 2022-11-19 07:54 288阅读 0赞

javascript语言实现各排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序（原创内容，禁止转载）

1. 冒泡排序算法实现（javascript）

  1. //冒泡排序算法(javascript)
  2. //author：Hengda
  3. //arr数组
  4. //mode false 升序 ture 降序
  5. function bubbleSort( arr, mode ){ 
  7.     var i, j, temp, len = arr.length;
  8.     for( i = len - 1 ; i > 0; i-- ){ 
  9.         for( j = 0; j < i; j++ ){ 
  10.             if( mode ? arr[ j + 1 ] < arr[ j ] : arr[ j + 1 ] > arr[ j ] ){ 
  11.                 temp = arr[ j + 1 ];
  12.                 arr[ j + 1 ] = arr[ j ];
  13.                 arr[ j ] = temp;
  14.             }
  15.         }
  16.     }
  17.     return arr;
  18. }

2. 计数排序算法实现（javascript）

  1. //计数排序算法(javascript)
  2. //author：Hengda
  3. //arr数组
  4. //mode false 升序 ture 降序
  5. function countingSort( arr, mode ){ 
  6.     //i,j为控制变量，temp为交换变量，len为数组的长度
  7.     var i, j, temp, len = arr.length;
  8.     var countArr = [];//用于原始数组中统计各元素出现的次数
  9.     var fillPos;//标记下一个回填位置
  10.     var countArrLen;//计数数组的长度
  11.     //统计
  12.     for( i = 0; i < len; i++ ){ 
  13.         if( countArr[ arr[ i ] ] != null ){ 
  14.             countArr[ arr[ i ] ] ++;
  15.         }else{ 
  16.             countArr[ arr[ i ] ] = 1;
  17.         }
  18.     }
  20.     //将数据重新排列回填到原始数组中
  21.     //统计
  22.     var fillPos = 0;//回填起始位置
  23.     var countArrLen = countArr.length;
  25.     if( mode ){ 
  26.         //
  27.         for( i = countArrLen - 1; i >=0; i-- ){ 
  28.             //
  29.             if( countArr[ i ] != null ){ 
  30.                 //回填countArr[ i ]个当前值i到原始数组，回填起始位置为fillPos
  31.                 for( j = 0; j < countArr[ i ]; j++ ){ 
  32.                     arr[ fillPos++ ] = i;
  33.                 }
  34.             }
  35.         }
  37.     }else{ 
  38.         //
  39.         for( i = 0; i < countArrLen; i++ ){ 
  40.             //
  41.             if( countArr[ i ] != null ){ 
  42.                 //回填countArr[ i ]个当前值i到原始数组，回填起始位置为fillPos
  43.                 for( j = 0; j < countArr[ i ]; j++ ){ 
  44.                     arr[ fillPos++ ] = i;
  45.                 }
  46.             }
  47.         }
  48.     }
  50.     //排序完成
  51.     return arr;
  52. }

3. 堆排序算法实现（javascript）

  1. //堆中某节点按升序或者降序递归下沉
  2. //author： Hengda
  3. //arr： 待排序数组
  4. //nodeNo： 二叉树中指定节点的序号/堆数组中的下标
  5. //heapLen： 堆的长度
  6. //mode： true 大的下沉，false 小的下沉
  7. function heapNodeSink( arr, nodeNo, heapLen, mode ){ 
  9.     var leftChild = ( nodeNo + 1 ) * 2 - 1; //做孩子
  10.     var rightChild = leftChild + 1;         //右孩子
  11.     var maxminNo = nodeNo;                  //最大值的序号
  12.     var temp;                               //用户变量值得交换
  14.     if( mode ){ 
  15.         //
  16.         if( heapLen > leftChild && arr[ maxminNo ] > arr[ leftChild ] ){ 
  17.             maxminNo = leftChild;//更新最大节点序号
  18.         }
  19.         if( heapLen > rightChild && arr[ maxminNo ] > arr[ rightChild ] ){ 
  20.             maxminNo = rightChild;//更新最大节点序号
  21.         }
  22.     }else{ 
  23.         if( heapLen > leftChild && arr[ maxminNo ] < arr[ leftChild ] ){ 
  24.             maxminNo = leftChild;//更新最大节点序号
  25.         }
  26.         if( heapLen > rightChild && arr[ maxminNo ] < arr[ rightChild ] ){ 
  27.             maxminNo = rightChild;//更新最大节点序号
  28.         }
  29.     }
  31.     //最大值所在节点有变化，则交换
  32.     if( maxminNo != nodeNo ){ 
  34.         //交换
  35.         temp = arr[ maxminNo ];
  36.         arr[ maxminNo ] = arr[ nodeNo ];
  37.         arr[ nodeNo ] = temp;
  39.         //继续下沉操作
  40.         heapNodeSink( arr, maxminNo, heapLen, mode );
  41.     }
  42. }
  44. //功能： 堆排序(javascript)
  45. //author： Hengda
  46. //arr： 待排序数组
  47. //mode： true 从大到小排序，false 从小到大排序
  48. function heapSort( arr, mode ){ 
  49.     var len = arr.length;   //数组的长度
  50.     var temp;               //用于交换节点值
  51.     var endHeapNodeNo;      //堆末尾节点在数组中的下标
  53.     //将数组调整为二叉堆
  54.     for( var i = Math.floor( len / 2 ) - 1; i >= 0; i-- ){ 
  55.         heapNodeSink( arr, i, len, mode );
  56.     }
  58.     for( var heapLen = len; heapLen > 0; heapLen-- ){ 
  59.         endHeapNodeNo = heapLen - 1;//堆的最后一个节点的序号
  61.         //交换堆顶和堆尾元素
  62.         temp = arr[ endHeapNodeNo ];
  63.         arr[ endHeapNodeNo ] = arr[ 0 ];
  64.         arr[ 0 ] = temp;
  66.         //对除了堆尾元素组成的堆进行堆顶下沉操作
  67.         heapNodeSink( arr, 0,  heapLen - 1, mode );
  68.     }
  69.     return arr;
  70. }

4. 插入排序算法实现（javascript）

  1. //插入排序算法(javascript)
  2. //算法原理
  3. //author：Hengda
  4. //2020/1/25
  5. //arr 待排序数组
  6. //mode true 从大到小排列，false 从小到大排列
  7. function insertionSort( arr, mode ){ 
  9.     var i, j, temp, len = arr.length;//len为待排序数组长度 temp为交换变量 i j为控制变量。
  11.     //从数组的第二个元素开始逐个往后处理。
  12.     for( i = 1; i < len; i++ ){ 
  13.         //将当前被处理元素值记录下来。
  14.         temp = arr[ i ];
  15.         //以下标倒序逐一比较当前元素位置之前的所有元素，如果比当前元素大，则逐一向后覆盖一个元素。
  16.         for( j = i - 1; j >= 0 && ( mode ? arr[ j ] < temp : arr[ j ] > temp ); j-- ){ 
  17.             arr[ j + 1 ] = arr[ j ];
  18.         }
  19.         //将点前被处理元素的值填入最终空缺的位置即 （j + 1） 注意这个 j 已经被for循环做了-1操作，所以这里需要+1。
  20.         arr[ j + 1 ] = temp;
  21.     }
  23.     //遍历完成后，整个数组即为有序数组。
  24.     return arr;
  25. }

5. 归并排序算法实现（javascript）

  1. //归并排序算法(javascript)
  2. //author：Hengda
  3. //arr数组
  4. //start 数组中待排序段落的起止位置，len为数据段的长度
  5. //mode false 升序 ture 降序
  6. function mergeSort( arr, start, len ,mode){ 
  8.     var i, j, temp;
  10.     //计算左侧数据段的位置和长度
  11.     var lstart = start;
  12.     var llen = Math.floor( len / 2 );
  14.     //计算右侧数据段的位置和长度
  15.     var rstart = lstart + llen;
  16.     var rlen = len - llen;
  18.     //分别对左右分段进行进行插入排序
  19.     if( llen > 4 ) mergeSort( arr, lstart, llen );
  20.     if( rlen > 4 ) mergeSort( arr, rstart, rlen );
  22.     //对当前数据段进行插入排序
  23.     for( i = start + 1; i < len + start; i++ ){ 
  24.         temp = arr[ i ];
  25.         for( j = i - 1; j >= start && ( mode ? arr[ j ] < temp : arr[ j ] > temp  ); j-- ){ 
  26.             arr[ j + 1 ] = arr[ j ];
  27.         }
  28.         arr[ j + 1 ] = temp;
  29.     }
  30.     return arr;
  31. }

6. 选择排序算法实现（javascript）

  1. //选择排序算法(javascript)
  2. //author：Hengda
  3. //arr数组
  4. //mode false 升序 ture 降序
  5. function selectionSort( arr, mode ){ 
  6.     //i,j为控制变量，miniMaxNo为标记发现的最大或者最小元素的下标，temp为交换变量，len为数组的长度
  7.     var i, j, minMaxNo, temp, len = arr.length;
  8.     //
  9.     for( i = 0; i < len; i++ ){ 
  10.         //当前位置初始为最小或最大数的位置
  11.         minMaxNo = i;
  12.         //遍历后续所有元素与minMaxNo对应的元素做比较，如果比minMaxNo大或者小，则更新minMaxNo的值为新元素的下标
  13.         for( j = i; j < len; j++ ){ 
  14.             if( mode ? arr[ j ] > arr[ minMaxNo ] : arr[ j ] < arr[ minMaxNo ] ){ 
  15.                 minMaxNo = j;
  16.             }
  17.         }
  18.         //将最终确定的最大或者最小值与当前被处理位置i对应的元素值做交换
  19.         temp = arr[ minMaxNo ];
  20.         arr[ minMaxNo ] = arr[ i ];
  21.         arr[ i ] = temp;
  22.     }
  23.     //排序完成
  24.     return arr;
  25. }

7. 希尔排序算法实现（javascript）

  1. //希尔排序算法(javascript)
  2. //author：Hengda
  3. //arr数组 
  4. //mode false 升序 ture 降序
  5. function shellSort( arr, mode ){ 
  6.     //1,j,k为控制变量，gap为分组间隙初始化为1，temp用于交换数据，len数组的长度
  7.     var i, j, k, gap = 1, temp, len = arr.length;
  8.     //计算合适的分组元素间隙，这里计算得到gap的最大值，这里的5也可以是其他数，值不同，实际排序速度也不同
  9.     while( gap< len / 5 ){ 
  10.         gap = gap*5 + 1;
  11.     }
  13.     //开始排序
  14.     while( gap > 0 ){ 
  16.         //以下按分组排序，该排序原理为插入排序，如看不明白，可参考插入排序算法逻辑
  17.         for( i = gap; i < len; i++ ){ 
  18.             temp = arr[ i ];
  19.             for( j = i - gap; j >= 0 && ( mode ? arr[ j ] < temp : arr[ j ] > temp ); j -= gap ){ 
  20.                 arr[ j + gap ] = arr[ j ];
  21.             }
  22.             arr[ j + gap ] = temp; 
  23.         }
  25.         //缩小分组间隔值
  26.         gap = Math.floor( gap / 5 );
  27.     }
  29.     return arr;
  30. }

8. 快速排序算法实现（javascript）

  1. //快速排序(javascript)
  2. //author：Hengda
  3. //arr数组
  4. //start 待排序数据段的起始下标（含）
  5. //end 待排序数据段终止下标（含） 
  6. //mode false 升序 ture 降序
  7. function quickSort( arr, start, end, mode ){ 
  9.     var i,j,temp;
  10.     var divValue;
  12.     if( start < end ){ 
  14.         //初始化基准值
  15.         baseValue = arr[ end ];
  16.         j = start;
  18.         //遍历整段数据元素，小于等于基准值的放在基准准直左侧（正序），大于等于基准值的放在基准值左侧（倒序）
  19.         for( i = start; i <= end ; i++ ){ 
  21.             //与基准值作比较
  22.             if( mode ? arr[ i ] >= baseValue : arr[ i ] <= baseValue ){ 
  24.                 //从左端开始依次排列放置，当前排列位置为$j，把原位置的元素向后交换
  25.                 temp = arr[ j ];
  26.                 arr[ j ] = arr[ i ];
  27.                 arr[ i ] = temp;
  28.                 //更新下一个应排列的位置
  29.                 j++;
  30.             }
  31.         }
  32.         //循环中$j在最后的++操作并未使用，这里需要减去，使$j正确标记左右分界元素
  33.         j--;
  35.         //分界元素在两端是，则靠近分界元素的一端无需再排序
  36.         //分界元素也无需再参与排序，因为左侧的一定小于等于分界元素，右侧的也一定大于等于分界元素
  37.         //分别对分界元素左右两侧的数据段继续排序
  38.         if( j > start ) quickSort( arr, start, j - 1, mode );
  39.         if( j < end ) quickSort( arr, j + 1, end, mode );
  40.     }
  41.     return arr;
  42. }

9. 测试排序1万个无序数，耗时结果如下

  1. //测试排序10000个数
  2. testSort( 10000, false );
  4. jssort.html:388 正在生成 10000个无序数...
  5. jssort.html:392 生成 10000个无序数完成
  6. jssort.html:344 ---------
  7. jssort.html:346 快速排序：
  8. jssort.html:358 -正序耗时：: 22.447265625ms
  9. jssort.html:372 -倒序耗时：: 7.83203125ms
  10. jssort.html:344 ---------
  11. jssort.html:346 希尔排序：
  12. jssort.html:358 -正序耗时：: 7.2939453125ms
  13. jssort.html:372 -倒序耗时：: 5.231689453125ms
  14. jssort.html:344 ---------
  15. jssort.html:346 计数排序：
  16. jssort.html:358 -正序耗时：: 7.36083984375ms
  17. jssort.html:372 -倒序耗时：: 7.77392578125ms
  18. jssort.html:344 ---------
  19. jssort.html:346 插入排序：
  20. jssort.html:358 -正序耗时：: 9.529052734375ms
  21. jssort.html:372 -倒序耗时：: 9.830078125ms
  22. jssort.html:344 ---------
  23. jssort.html:346 堆排序：
  24. jssort.html:358 -正序耗时：: 8.35107421875ms
  25. jssort.html:372 -倒序耗时：: 2.64990234375ms
  26. jssort.html:344 ---------
  27. jssort.html:346 归并排序：
  28. jssort.html:358 -正序耗时：: 82.681884765625ms
  29. jssort.html:372 -倒序耗时：: 114.632080078125ms
  30. jssort.html:344 ---------
  31. jssort.html:346 选择排序：
  32. jssort.html:358 -正序耗时：: 96.762939453125ms
  33. jssort.html:372 -倒序耗时：: 151.841064453125ms
  34. jssort.html:344 ---------
  35. jssort.html:346 冒泡排序：
  36. jssort.html:358 -正序耗时：: 252.561767578125ms
  37. jssort.html:372 -倒序耗时：: 289.15087890625ms

在这里插入图片描述

10. 测试排序10万个无序数，耗时结果如下

  1. //测试排序100000个数
  2. testSort( 100000, false );
  4. testSort(100000)
  5. jssort.html:386 ---------
  6. jssort.html:388 正在生成 100000个无序数...
  7. jssort.html:392 生成 100000个无序数完成
  8. jssort.html:344 ---------
  9. jssort.html:346 快速排序：
  10. jssort.html:358 -正序耗时：: 10.38818359375ms
  11. jssort.html:372 -倒序耗时：: 11.48193359375ms
  12. jssort.html:344 ---------
  13. jssort.html:346 希尔排序：
  14. jssort.html:358 -正序耗时：: 22.110107421875ms
  15. jssort.html:372 -倒序耗时：: 19.762939453125ms
  16. jssort.html:344 ---------
  17. jssort.html:346 计数排序：
  18. jssort.html:358 -正序耗时：: 17.098876953125ms
  19. jssort.html:372 -倒序耗时：: 14.27294921875ms
  20. jssort.html:344 ---------
  21. jssort.html:346 插入排序：
  22. jssort.html:358 -正序耗时：: 25.2509765625ms
  23. jssort.html:372 -倒序耗时：: 27.105712890625ms
  24. jssort.html:344 ---------
  25. jssort.html:346 堆排序：
  26. jssort.html:358 -正序耗时：: 24.9130859375ms
  27. jssort.html:372 -倒序耗时：: 26.115966796875ms
  28. jssort.html:344 ---------
  29. jssort.html:346 归并排序：
  30. jssort.html:358 -正序耗时：: 4676.212158203125ms
  31. jssort.html:372 -倒序耗时：: 7991.64599609375ms
  32. jssort.html:344 ---------
  33. jssort.html:346 选择排序：
  34. jssort.html:358 -正序耗时：: 5662.914794921875ms
  35. jssort.html:372 -倒序耗时：: 12556.882080078125ms
  36. jssort.html:344 ---------
  37. jssort.html:346 冒泡排序：
  38. jssort.html:358 -正序耗时：: 21762.098876953125ms
  39. jssort.html:372 -倒序耗时：: 23281.131103515625ms

在这里插入图片描述

以下是测试函数

  1. //测试排序算法函数
  2. //totalNum 测试排序的元素个数
  3. //isPrintArrData 是否打印数组数据
  4. function testSort( totalNum, isPrintArrData ){ 
  6.     //生成测试数据
  7.     arr = makeData( totalNum, isPrintArrData );
  9.     //1>调用测试函数，对 快速排序 算法进行测试
  10.     TestOneSortFunc( arr, 'quickSort', ", 0, arr.length - 1" , "快速排序", isPrintArrData );
  12.     //2>调用测试函数，对 希尔排序 算法进行测试
  13.     TestOneSortFunc( arr, 'shellSort', "", "希尔排序", isPrintArrData );
  15.     //3>调用测试函数，对 计数排序 算法进行测试
  16.     TestOneSortFunc( arr, 'countingSort', "", "计数排序", isPrintArrData );
  18.     //4>调用测试函数，对 插入排序 算法进行测试
  19.     TestOneSortFunc( arr, 'heapSort', "", "插入排序", isPrintArrData );
  21.     //5>调用测试函数，对 堆排序 算法进行测试
  22.     TestOneSortFunc( arr, 'heapSort', "", "堆排序", isPrintArrData );
  24.     //6>调用测试函数，对 归并排序 算法进行测试
  25.     TestOneSortFunc( arr, 'mergeSort', ",0, arr.length", "归并排序", isPrintArrData );
  27.     //7>调用测试函数，对 选择排序 算法进行测试
  28.     TestOneSortFunc( arr, 'selectionSort', "", "选择排序", isPrintArrData );
  30.     //8>调用测试函数，对 冒泡排序 算法进行测试
  31.     TestOneSortFunc( arr, 'bubbleSort', "", "冒泡排序", isPrintArrData );
  33. }
  35. //测试一个排序算法函数
  36. function TestOneSortFunc( arr, funcName, funcOtherArgv, textName, isPrintArrData ){ 
  37.     console.log( "---------" );
  38.     //arr = makeData( totalNum );
  39.     console.log( textName + "：" );
  40.     //console.log( "原始数据：" );
  41.     //console.log( arr );
  43.     //正序
  44.     arr1 = arr.slice();
  45.     console.time( "-正序耗时：" );
  47.     //eval( funcName + "(arr1, 0, arr1.length - 1, false)" );
  48.     //, 0, arr1.length - 1
  49.     eval( funcName + "(arr1"+ funcOtherArgv +", false)" );
  51.     console.timeEnd( "-正序耗时：" );
  52.     if( isPrintArrData ){ 
  53.         console.log( "正序排序结果：" );
  54.         console.log( arr1 );
  55.     }
  57.     //逆序
  58.     arr2 = arr.slice();
  59.     console.time( "-倒序耗时：" );
  61.     //eval( funcName + "(arr2, 0, arr2.length - 1, true)" );
  62.     //, 0, arr2.length - 1
  63.     eval( funcName + "(arr2"+ funcOtherArgv +", true)" );
  65.     console.timeEnd( "-倒序耗时：" );
  67.     if( isPrintArrData ){ 
  68.         console.log( "倒序排序结果：" );
  69.         console.log( arr2 );
  70.     }
  71. }
  73. //数据生成函数
  74. function makeData( totalNum, isPrintArrData ){ 
  76.     var arr = [];
  77.     var i = totalNum;
  79.     console.log( "---------" );
  81.     console.log( "正在生成 " + totalNum + "个无序数..." );
  82.     while( i-- ){ 
  83.         arr.push( Math.floor( Math.random() * totalNum ) );
  84.     }
  85.     console.log( "生成 " + totalNum + "个无序数完成" );
  86.     if( isPrintArrData ){ 
  87.         console.log( "原始无序数据：" );
  88.         console.log( arr );
  89.     }
  91.     return arr;
  92. }

如果需要打印每个算法的排序结果，把 testSort() 的第二个参数设置为true即可

详细原理解释请参考：

1、十大经典算法总结
2、二叉堆的性质
3、堆排序原理

发表评论

表情：
评论列表 （有 0 条评论，288人围观）

还没有评论，来说两句吧...

相关阅读