1. 冒泡排序算法实现（JAVAscript）
//冒泡排序算法(JavaScript)
//author：Hengda
//arr数组
//mode false 升序 ture 降序
function bubbleSort( arr, mode ){
var i, j, temp, len = arr.length;
for( i = len - 1 ; i > 0; i-- ){
for( j = 0; j < i; j++ ){
if( mode ? arr[ j + 1 ] < arr[ j ] : arr[ j + 1 ] > arr[ j ] ){
temp = arr[ j + 1 ];
arr[ j + 1 ] = arr[ j ];
arr[ j ] = temp;
}
}
}
return arr;
}
2. 计数排序算法实现（javascript）
//计数排序算法(javascript)
//author：Hengda
//arr数组
//mode false 升序 ture 降序
function countingSort( arr, mode ){
//i,j为控制变量，temp为交换变量，len为数组的长度
var i, j, temp, len = arr.length;
var countArr = [];//用于原始数组中统计各元素出现的次数
var fillPos;//标记下一个回填位置
var countArrLen;//计数数组的长度
//统计
for( i = 0; i < len; i++ ){
if( countArr[ arr[ i ] ] != null ){
countArr[ arr[ i ] ] ++;
}else{
countArr[ arr[ i ] ] = 1;
}
}
//将数据重新排列回填到原始数组中
//统计
var fillPos = 0;//回填起始位置
var countArrLen = countArr.length;
if( mode ){
//
for( i = countArrLen - 1; i >=0; i-- ){
//
if( countArr[ i ] != null ){
//回填countArr[ i ]个当前值i到原始数组，回填起始位置为fillPos
for( j = 0; j < countArr[ i ]; j++ ){
arr[ fillPos++ ] = i;
}
}
}
}else{
//
for( i = 0; i < countArrLen; i++ ){
//
if( countArr[ i ] != null ){
//回填countArr[ i ]个当前值i到原始数组，回填起始位置为fillPos
for( j = 0; j < countArr[ i ]; j++ ){
arr[ fillPos++ ] = i;
}
}
}
}
//排序完成
return arr;
}
3. 堆排序算法实现（javascript）
//功能： 堆排序(javascript)
//author： Hengda
//arr： 待排序数组
//mode： true 从大到小排序，false 从小到大排序
function heapSort( arr, mode ){
var len = arr.length; //数组的长度
var temp; //用于交换节点值
var endHeapNodeNo; //堆末尾节点在数组中的下标
//将数组调整为二叉堆
for( var i = Math.floor( len / 2 ) - 1; i >= 0; i-- ){
heapNodeSink( arr, i, len, mode );
}
for( var heapLen = len; heapLen > 0; heapLen-- ){
endHeapNodeNo = heapLen - 1;//堆的最后一个节点的序号
//交换堆顶和堆尾元素
temp = arr[ endHeapNodeNo ];
arr[ endHeapNodeNo ] = arr[ 0 ];
arr[ 0 ] = temp;
//对除了堆尾元素组成的堆进行堆顶下沉操作
heapNodeSink( arr, 0, heapLen - 1, mode );
}
return arr;
}
//堆中某节点按升序或者降序递归下沉
//author： Hengda
//arr： 待排序数组
//nodeNo： 二叉树中指定节点的序号/堆数组中的下标
//heapLen： 堆的长度
//mode： true 大的下沉，false 小的下沉
function heapNodeSink( arr, nodeNo, heapLen, mode ){
var leftChild = ( nodeNo + 1 ) * 2 - 1; //做孩子
var rightChild = leftChild + 1; //右孩子
var maxminNo = nodeNo; //最大值的序号
var temp; //用户变量值得交换
if( mode ){
//
if( heapLen > leftChild && arr[ maxminNo ] > arr[ leftChild ] ){
maxminNo = leftChild;//更新最大节点序号
}
if( heapLen > rightChild && arr[ maxminNo ] > arr[ rightChild ] ){
maxminNo = rightChild;//更新最大节点序号
}
}else{
if( heapLen > leftChild && arr[ maxminNo ] < arr[ leftChild ] ){
maxminNo = leftChild;//更新最大节点序号
}
if( heapLen > rightChild && arr[ maxminNo ] < arr[ rightChild ] ){
maxminNo = rightChild;//更新最大节点序号
}
}
//最大值所在节点有变化，则交换
if( maxminNo != nodeNo ){
//交换
temp = arr[ maxminNo ];
arr[ maxminNo ] = arr[ nodeNo ];
arr[ nodeNo ] = temp;
//继续下沉操作
heapNodeSink( arr, maxminNo, heapLen, mode );
}
}
4. 插入排序算法实现（javascript）
//插入排序算法(javascript)
//算法原理
//author：Hengda
//2020/1/25
//arr 待排序数组
//mode true 从大到小排列，false 从小到大排列
function insertionSort( arr, mode ){
var i, j, temp, len = arr.length;//len为待排序数组长度 temp为交换变量 i j为控制变量。
//从数组的第二个元素开始逐个往后处理。
for( i = 1; i < len; i++ ){
//将当前被处理元素值记录下来。
temp = arr[ i ];
//以下标倒序逐一比较当前元素位置之前的所有元素，如果比当前元素大，则逐一向后覆盖一个元素。
for( j = i - 1; j >= 0 && ( mode ? arr[ j ] < temp : arr[ j ] > temp ); j-- ){
arr[ j + 1 ] = arr[ j ];
}
//将点前被处理元素的值填入最终空缺的位置即 （j + 1） 注意这个 j 已经被for循环做了-1操作，所以这里需要+1。
arr[ j + 1 ] = temp;
}
//遍历完成后，整个数组即为有序数组。
return arr;
}
5. 归并排序算法实现（javascript）
//归并排序算法(javascript)
//author：Hengda
//arr数组
//start 数组中待排序段落的起止位置，len为数据段的长度
//mode false 升序 ture 降序
function mergeSort( arr, start, len ,mode){
var i, j, temp;
//计算左侧数据段的位置和长度
var lstart = start;
var llen = Math.floor( len / 2 );
//计算右侧数据段的位置和长度
var rstart = lstart + llen;
var rlen = len - llen;
//分别对左右分段进行进行插入排序
if( llen > 4 ) mergeSort( arr, lstart, llen );
if( rlen > 4 ) mergeSort( arr, rstart, rlen );
//对当前数据段进行插入排序
for( i = start + 1; i < len + start; i++ ){
temp = arr[ i ];
for( j = i - 1; j >= start && ( mode ? arr[ j ] < temp : arr[ j ] > temp ); j-- ){
arr[ j + 1 ] = arr[ j ];
}
arr[ j + 1 ] = temp;
}
return arr;
}
6. 选择排序算法实现（javascript）
//选择排序算法(javascript)
//author：Hengda
//arr数组
//mode false 升序 ture 降序
function selectionSort( arr, mode ){
//i,j为控制变量，miniMaxNo为标记发现的最大或者最小元素的下标，temp为交换变量，len为数组的长度
var i, j, minMaxNo, temp, len = arr.length;
//
for( i = 0; i < len; i++ ){
//当前位置初始为最小或最大数的位置
minMaxNo = i;
//遍历后续所有元素与minMaxNo对应的元素做比较，如果比minMaxNo大或者小，则更新minMaxNo的值为新元素的下标
for( j = i; j < len; j++ ){
if( mode ? arr[ j ] > arr[ minMaxNo ] : arr[ j ] < arr[ minMaxNo ] ){
minMaxNo = j;
}
}
//将最终确定的最大或者最小值与当前被处理位置i对应的元素值做交换
temp = arr[ minMaxNo ];
arr[ minMaxNo ] = arr[ i ];
arr[ i ] = temp;
}
//排序完成
return arr;
}
7. 希尔排序算法实现（javascript）
//希尔排序算法(javascript)
//author：Hengda
//arr数组
//mode false 升序 ture 降序
function shellSort( arr, mode ){
//1,j,k为控制变量，gap为分组间隙初始化为1，temp用于交换数据，len数组的长度
var i, j, k, gap = 1, temp, len = arr.length;
//计算合适的分组元素间隙，这里计算得到gap的最大值，这里的5也可以是其他数，值不同，实际排序速度也不同
while( gap< len / 5 ){
gap = gap*5 + 1;
}
//开始排序
while( gap > 0 ){
//以下按分组排序，该排序原理为插入排序，如看不明白，可参考插入排序算法逻辑
for( i = gap; i < len; i++ ){
temp = arr[ i ];
for( j = i - gap; j >= 0 && ( mode ? arr[ j ] < temp : arr[ j ] > temp ); j -= gap ){
arr[ j + gap ] = arr[ j ];
}
arr[ j + gap ] = temp;
}
//缩小分组间隔值
gap = Math.floor( gap / 5 );
}
return arr;
}
8. 快速排序算法实现（javascript）
//快速排序(javascript)
//author：Hengda
//arr数组
//start 待排序数据段的起始下标（含）
//end 待排序数据段终止下标（含）
//mode false 升序 ture 降序
function quickSort( arr, start, end, mode ){
var i,j,temp;
var divValue;
if( start < end ){
//初始化基准值
baseValue = arr[ end ];
j = start;
//遍历整段数据元素，小于等于基准值的放在基准准直左侧（正序），大于等于基准值的放在基准值左侧（倒序）
for( i = start; i <= end ; i++ ){
//与基准值作比较
if( mode ? arr[ i ] >= baseValue : arr[ i ] <= baseValue ){
//从左端开始依次排列放置，当前排列位置为$j，把原位置的元素向后交换
temp = arr[ j ];
arr[ j ] = arr[ i ];
arr[ i ] = temp;
//更新下一个应排列的位置
j++;
}
}
//循环中$j在最后的++操作并未使用，这里需要减去，使$j正确标记左右分界元素
j--;
//分界元素在两端是，则靠近分界元素的一端无需再排序
//分界元素也无需再参与排序，因为左侧的一定小于等于分界元素，右侧的也一定大于等于分界元素
//分别对分界元素左右两侧的数据段继续排序
if( j > start ) quickSort( arr, start, j - 1, mode );
if( j < end ) quickSort( arr, j + 1, end, mode );
}
return arr;
}
9. 测试排序1万个无序数，耗时如下
//测试排序10000个数
testSort( 10000, false );
```
```javascript
jssort.html:388 正在生成 10000个无序数...
jssort.html:392 生成 10000个无序数完成
jssort.html:344 ---------
jssort.html:346 快速排序：
jssort.html:358 -正序耗时：: 22.447265625ms
jssort.html:372 -倒序耗时：: 7.83203125ms
jssort.html:344 ---------
jssort.html:346 希尔排序：
jssort.html:358 -正序耗时：: 7.2939453125ms
jssort.html:372 -倒序耗时：: 5.231689453125ms
jssort.html:344 ---------
jssort.html:346 计数排序：
jssort.html:358 -正序耗时：: 7.36083984375ms
jssort.html:372 -倒序耗时：: 7.77392578125ms
jssort.html:344 ---------
jssort.html:346 插入排序：
jssort.html:358 -正序耗时：: 9.529052734375ms
jssort.html:372 -倒序耗时：: 9.830078125ms
jssort.html:344 ---------
jssort.html:346 堆排序：
jssort.html:358 -正序耗时：: 8.35107421875ms
jssort.html:372 -倒序耗时：: 2.64990234375ms
jssort.html:344 ---------
jssort.html:346 归并排序：
jssort.html:358 -正序耗时：: 82.681884765625ms
jssort.html:372 -倒序耗时：: 114.632080078125ms
jssort.html:344 ---------
jssort.html:346 选择排序：
jssort.html:358 -正序耗时：: 96.762939453125ms
jssort.html:372 -倒序耗时：: 151.841064453125ms
jssort.html:344 ---------
jssort.html:346 冒泡排序：
jssort.html:358 -正序耗时：: 252.561767578125ms
jssort.html:372 -倒序耗时：: 289.15087890625ms
10. 测试排序10万个无序数，耗时结果如下
//测试排序100000个数
testSort( 100000, false );
```
```javascript
testSort(100000)
jssort.html:386 ---------
jssort.html:388 正在生成 100000个无序数...
jssort.html:392 生成 100000个无序数完成
jssort.html:344 ---------
jssort.html:346 快速排序：
jssort.html:358 -正序耗时：: 10.38818359375ms
jssort.html:372 -倒序耗时：: 11.48193359375ms
jssort.html:344 ---------
jssort.html:346 希尔排序：
jssort.html:358 -正序耗时：: 22.110107421875ms
jssort.html:372 -倒序耗时：: 19.762939453125ms
jssort.html:344 ---------
jssort.html:346 计数排序：
jssort.html:358 -正序耗时：: 17.098876953125ms
jssort.html:372 -倒序耗时：: 14.27294921875ms
jssort.html:344 ---------
jssort.html:346 插入排序：
jssort.html:358 -正序耗时：: 25.2509765625ms
jssort.html:372 -倒序耗时：: 27.105712890625ms
jssort.html:344 ---------
jssort.html:346 堆排序：
jssort.html:358 -正序耗时：: 24.9130859375ms
jssort.html:372 -倒序耗时：: 26.115966796875ms
jssort.html:344 ---------
jssort.html:346 归并排序：
jssort.html:358 -正序耗时：: 4676.212158203125ms
jssort.html:372 -倒序耗时：: 7991.64599609375ms
jssort.html:344 ---------
jssort.html:346 选择排序：
jssort.html:358 -正序耗时：: 5662.914794921875ms
jssort.html:372 -倒序耗时：: 12556.882080078125ms
jssort.html:344 ---------
jssort.html:346 冒泡排序：
jssort.html:358 -正序耗时：: 21762.098876953125ms
jssort.html:372 -倒序耗时：: 23281.131103515625ms
以下是测试函数
//测试排序算法函数
//totalNum 测试排序的元素个数
//isPrintArrData 是否打印数组数据
function testSort( totalNum, isPrintArrData ){
//生成测试数据
arr = makeData( totalNum, isPrintArrData );
//1>调用测试函数，对 快速排序 算法进行测试
TestOneSortFunc( arr, 'quickSort', ", 0, arr.length - 1" , "快速排序", isPrintArrData );
//2>调用测试函数，对 希尔排序 算法进行测试
TestOneSortFunc( arr, 'shellSort', "", "希尔排序", isPrintArrData );
//3>调用测试函数，对 计数排序 算法进行测试
TestOneSortFunc( arr, 'countingSort', "", "计数排序", isPrintArrData );
//4>调用测试函数，对 插入排序 算法进行测试
TestOneSortFunc( arr, 'heapSort', "", "插入排序", isPrintArrData );
//5>调用测试函数，对 堆排序 算法进行测试
TestOneSortFunc( arr, 'heapSort', "", "堆排序", isPrintArrData );
//6>调用测试函数，对 归并排序 算法进行测试
TestOneSortFunc( arr, 'mergeSort', ",0, arr.length", "归并排序", isPrintArrData );
//7>调用测试函数，对 选择排序 算法进行测试
TestOneSortFunc( arr, 'selectionSort', "", "选择排序", isPrintArrData );
//8>调用测试函数，对 冒泡排序 算法进行测试
TestOneSortFunc( arr, 'bubbleSort', "", "冒泡排序", isPrintArrData );
}
//测试一个排序算法函数
function TestOneSortFunc( arr, funcName, funcOtherArgv, textName, isPrintArrData ){
console.log( "---------" );
//arr = makeData( totalNum );
console.log( textName + "：" );
//console.log( "原始数据：" );
//console.log( arr );
//正序
arr1 = arr.slice();
console.time( "-正序耗时：" );
//eval( funcName + "(arr1, 0, arr1.length - 1, false)" );
//, 0, arr1.length - 1
eval( funcName + "(arr1"+ funcOtherArgv +", false)" );
console.timeEnd( "-正序耗时：" );
if( isPrintArrData ){
console.log( "正序排序结果：" );
console.log( arr1 );
}
//逆序
arr2 = arr.slice();
console.time( "-倒序耗时：" );
//eval( funcName + "(arr2, 0, arr2.length - 1, true)" );
//, 0, arr2.length - 1
eval( funcName + "(arr2"+ funcOtherArgv +", true)" );
console.timeEnd( "-倒序耗时：" );
if( isPrintArrData ){
console.log( "倒序排序结果：" );
console.log( arr2 );
}
}
//数据生成函数
function makeData( totalNum, isPrintArrData ){
var arr = [];
var i = totalNum;
console.log( "---------" );
console.log( "正在生成 " + totalNum + "个无序数..." );
while( i-- ){
arr.push( Math.floor( Math.random() * totalNum ) );
}
console.log( "生成 " + totalNum + "个无序数完成" );
if( isPrintArrData ){
console.log( "原始无序数据：" );
console.log( arr );
}
return arr;
}
如果需要打印每个算法的排序结果，把 testSort() 的第二个参数设置为true即可
