德哥盛世网络科技

 找回密码
 立即注册
查看: 1161|回复: 0

js实现各种常用排序算法

[复制链接]

716

主题

1112

帖子

8807

积分

管理员

CEO

Rank: 9Rank: 9Rank: 9

积分
8807

最佳新人活跃会员热心会员推广达人宣传达人

QQ
发表于 2018-5-28 23:51:45 | 显示全部楼层 |阅读模式
1.冒泡排序var bubbleSort = function (arr) { var flag = true; var len = arr.length; for (var i = 0; i < len - 1; i++) { flag = true; for (var j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j + 1]) { var temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; flag = false; } } if (flag) { break; } }};2.选择排序var selectSort = function (arr) {a var min; for (var i = 0; i < arr.length-1; i++) { min = i; for (var j = i + 1; j < arr.length; j++) { if (arr[min] > arr[j]) { min = j; } } if (i != min) { swap(arr, i, min); } console.log(i+1, ": " + arr); }};function swap(arr, index1, index2) { var temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp;};3.插入排序var insertSort = function (arr) { var len = arr.length, key; for (var i = 1; i < len; i++) { var j = i; key = arr[j]; while (--j > -1) { if (arr[j] > key) { arr[j + 1] = arr[j]; } else { break; } } arr[j + 1] = key; }};4.希尔排序var shellSort = function (arr) { var gaps = [5, 3, 1]; for (var g = 0; g < gaps.length; ++g) { for (var i = gaps[g]; i < arr.length; ++i) { vartemp = arr; for (var j = i; j >= gaps[g] && arr[j - gaps[g]] > temp; j -= gaps[g]) { arr[j] = arr[j - gaps[g]]; } arr[j] = temp; } }};5.归并排序function mergeSort(arr) { if (arr.length < 2) { return; } var step = 1; var left, right; while (step < arr.length) { left = 0; right = step; while(right + step <= arr.length) { mergeArrays(arr, left, left + step, right, right + step); left = right + step; right = left + step; } if (right < arr.length) { mergeArrays(arr, left, left + step, right, arr.length); } step *= 2; }}function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) { var rightArr = new Array(stopRight - startRight + 1); var leftArr = new Array(stopLeft - startLeft + 1); k = startRight; for (var i = 0; i < (rightArr.length - 1); ++i) { rightArr = arr[k]; ++k; } k = startLeft; for (var i = 0; i < (leftArr.length - 1); ++i) { leftArr = arr[k]; ++k; } rightArr[rightArr.length - 1] = Infinity; // 哨兵值 leftArr[leftArr.length - 1] = Infinity; // 哨兵值 var m = 0; var n = 0; for (var k = startLeft; k < stopRight; ++k) { if (leftArr[m] <= rightArr[n]) { arr[k] = leftArr[m]; m++; } else { arr[k] = rightArr[n]; n++; } }}6.快速排序var quickSort = function(arr, left, right) { var i, j, t, pivot; if (left >= right) { return; } pivot = arr[left]; i = left; j = right; while (i != j) { while (arr[j] >= pivot && i < j) { j--; } while (arr <= pivot && i < j) { i++; } if (i < j) { t = arr; arr = arr[j]; arr[j] = t; } } arr[left] = arr[j]; arr[j] = pivot; quickSort(arr, left, i - 1); quickSort(arr, i + 1, right);}总结:算法效率比较:
排序方法
平均情况
最好情况
最坏情况

冒泡排序O(n2)O(n)O(n2)
选择排序O(n2)O(n2)O(n2)
插入排序O(n2)O(n)O(n2)
希尔排序O(nlogn)~O(n2)O(n^1.5)O(n2)
归并排序O(nlogn)O(nlogn)O(nlogn)
快速排序O(nlogn)O(nlogn)O(n2)
不抛弃不放弃
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|小黑屋|德哥数据中心|德哥盛世花园|德哥盛世安防|德哥盛世影视|德哥盛世网络科技 ( 鄂ICP备15011170号-4 )

GMT+8, 2021-2-28 15:26 , Processed in 1.132762 second(s), 23 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表