博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
js排序方法
阅读量:4648 次
发布时间:2019-06-09

本文共 5674 字,大约阅读时间需要 18 分钟。

function swap(ary, x, y) {    if (x === y) return    let temp = ary[x]    ary[x] = ary[y]    ary[y] = temp}//生成随机数:function random(n) {    let ary = new Array(n)    return ary.fill(0).map(_ => Math.random() * n | 0)}//选择排序( 不稳定):function selectSort(ary) {    for (var i = 0; i < ary.length - 1; i++) {        let min = i        let change        for (var j = i + 1; j < ary.length; j++) {            if (ary[j] < ary[min]) {                min = j            }        }        swap(ary, min, i)        //     change = ary[min]        //     ary[min] = ary[i]        //     ary[i] = change    }    return ary}//冒泡排序:function bubbleSort(ary, comparator) {    let flag    let l = ary.length    for (let i = l - 1; i >= 0; i--) {        flag = false        for (let j = 0; j < i; j++) {            //if (ary[j + 1] < ary[j]) {
if (comparator(ary[j], ary[j + 1]) > 0) { flag = true swap(ary, j, j + 1) } } if (!flag) { break } } return ary}function comparator(a, b) { if (a > b) { return 1 } else { return -1 }}//归并排序 稳定的function mergeSort(ary) { if (ary.length < 2) { return ary.slice() } var mid = Math.floor(ary.length / 2) var left = mergeSort(ary.slice(0, mid)) var right = mergeSort(ary.slice(mid)) var result = [] while (left.length && right.length) { if (left[0] <= right[0]) { result.push(left.shift()) } else { result.push(right.shift()) } } result.push(...left, ...right) return result}//快速排序:function partition(ary, comparator, start = 0, end = ary.length - 1, ) { if (start >= end) { return } var pivotIndex = Math.floor(Math.random() * (end - start + 1) + start) var pivot = ary[pivotIndex] swap(ary, pivotIndex, end) for (var i = start - 1, j = start; j < end; j++) { if (comparator(ary[j], pivot) < 0) { i++ swap(ary, i, j) } } swap(ary, i + 1, end) partition(ary, comparator, start, i) partition(ary, comparator, i + 2, end) return ary}function quickSort(ary, comparator = (a, b) => a - b) { return partition(ary, comparator)}//堆排序// function reheap(ary, topIndex, endIndex = ary.length - 1) {// if (topIndex > endIndex) {// return// }// var largestIndex = topIndex// var leftIndex = topIndex * 2 + 1// var rightIndex = topIndex * 2 + 1// if (leftIndex <= endIndex && ary[leftIndex] > ary[largestIndex]) {// largestIndex = leftIndex// }// if (rightIndex <= endIndex && ary[rightIndex] > ary[largestIndex]) {// largestIndex = rightIndex// }// if (largestIndex !== topIndex) {// swap(ary, largestIndex, topIndex)// reheap(ary, largestIndex, endIndex)// }// }// function heapify(ary) {// for (var i = ary.length - 1; i >= 0; i--) {// reheap(ary, i)// }// return ary// }// function heapSort(ary) {// heapify(ary)// for (var i = ary.length - 1; i >= 1; i--) {// swap(ary, 0, i)// reheap(ary, 0, i - 1)// }// return ary// }function reheap(ary, topIndex, endIndex = ary.length - 1) { if (topIndex > endIndex) { return } var largestIndex = topIndex var leftIndex = topIndex * 2 + 1 var rightIndex = topIndex * 2 + 2 if (leftIndex <= endIndex && ary[leftIndex] > ary[largestIndex]) { largestIndex = leftIndex } if (rightIndex <= endIndex && ary[rightIndex] > ary[largestIndex]) { largestIndex = rightIndex } if (largestIndex != topIndex) { swap(ary, largestIndex, topIndex) reheap(ary, largestIndex, endIndex) }}//把一个数组调整成一个堆function heapify(ary) { for (var i = ary.length - 1; i >= 0; i--) { reheap(ary, i) } return ary}// 堆排序function heapSort(ary) { heapify(ary) for (var i = ary.length - 1; i >= 1; i--) { swap(ary, 0, i) reheap(ary, 0, i - 1) } return ary}class PriorityQueue { constructor(comparator = (a, b) => a - b) { this.heap = [] this.comparator = comparator } _show() { return showTree(el, this.heap) } _swap(i, j) { if (i !== j) { var temp = this.heap[i] this.heap[i] = this.heap[j] this.heap[j] = temp } this._show() return this } _reverseReheap(pos) { var parentPos = (pos - 1) / 2 | 0 if (parentPos >= 0 && this.comparator(this.heap[pos], this.heap[parentPos]) < 0) { this._swap(pos, parentPos) this._reverseReheap(parentPos) } } push(val) { this.heap.push(val) this._reverseReheap(this.heap.length - 1) } _reheap(topIndex, endIndex = this.heap.length - 1) { if (topIndex > endIndex) { return } var ary = this.heap var largestIndex = topIndex var leftIndex = topIndex * 2 + 1 var rightIndex = topIndex * 2 + 2 if (leftIndex <= endIndex && this.comparator(ary[leftIndex], ary[largestIndex]) < 0) { largestIndex = leftIndex } if (rightIndex <= endIndex && this.comparator(ary[rightIndex], ary[largestIndex]) < 0) { largestIndex = rightIndex } if (largestIndex != topIndex) { swap(ary, largestIndex, topIndex) this._reheap(largestIndex, endIndex) } } pop() { if (heap.length === 1) { return this.heap.pop() } var result = this.heap[0] this.heap[0] = this.heap.pop() this._reheap(0) return result }}

请给你自己加油!

转载于:https://www.cnblogs.com/l8l8/p/8697847.html

你可能感兴趣的文章
ubuntu 重启命令,ubuntu 重启网卡方法
查看>>
Linux的学习:
查看>>
JavaScript中的原型继承原理
查看>>
Python logger模块
查看>>
jquery控制css的display(控制元素的显示与隐藏)
查看>>
关于python做人工智能的一个网页(很牛逼)
查看>>
判断控件的CGRect是否重合,获取控件的最大XY值
查看>>
POJ-1128 Frame Stacking
查看>>
浏览器调试淘宝首页看到有趣的招聘信息
查看>>
ASP.NET Identity “角色-权限”管理 4
查看>>
[转][译]ASP.NET MVC 4 移动特性
查看>>
SOC CPU
查看>>
get_result --perl
查看>>
163镜像地址
查看>>
ehcache memcache redis 三大缓存男高音
查看>>
eclipse 快捷键Open Implementation 直接退出
查看>>
minix中管道文件和设备文件的读写
查看>>
JAXB - Annotations, Annotations for Enums: XmlEnum, XmlEnumValue
查看>>
context 插图
查看>>
文件管理器中不支持的wma歌曲也显示可以播放的音乐图标
查看>>