Javascript中的常见排序算法_javascript技巧-js教程-PHP中文網

首頁

web前端

js教程

Javascript中的常见排序算法_javascript技巧

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

May 16, 2016 pm 07:16 PM

排序演算法

具体代码及比较如下所示：

复制代码代码如下:

nbsp;html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

常见排序算法之 JavaScript版

<script> Array.prototype.swap = function(i, j) { var temp = this[i]; this[i] = this[j]; this[j] = temp; } Array.prototype.bubbleSort = function() { for (var i = this.length - 1; i > 0; --i) { for (var j = 0; j < i; ++j) { if (this[j] > this[j + 1]) this.swap(j, j + 1); } } } Array.prototype.selectionSort = function() { for (var i = 0; i < this.length; ++i) { var index = i; for (var j = i + 1; j < this.length; ++j) { if (this[j] < this[index]) index = j; } this.swap(i, index); } } Array.prototype.insertionSort = function() { for (var i = 1; i < this.length; ++i) { var j = i, value = this[i]; while (j > 0 && this[j - 1] > value) { this[j] = this[j - 1]; --j; } this[j] = value; } } Array.prototype.shellSort = function() { for (var step = this.length >> 1; step > 0; step >>= 1) { for (var i = 0; i < step; ++i) { for (var j = i + step; j < this.length; j += step) { var k = j, value = this[j]; while (k >= step && this[k - step] > value) { this[k] = this[k - step]; k -= step; } this[k] = value; } } } } Array.prototype.quickSort = function(s, e) { if (s == null) s = 0; if (e == null) e = this.length - 1; if (s >= e) return; this.swap((s + e) >> 1, e); var index = s - 1; for (var i = s; i <= e; ++i) { if (this[i] <= this[e]) this.swap(i, ++index); } this.quickSort(s, index - 1); this.quickSort(index + 1, e); } Array.prototype.stackQuickSort = function() { var stack = [0, this.length - 1]; while (stack.length > 0) { var e = stack.pop(), s = stack.pop(); if (s >= e) continue; this.swap((s + e) >> 1, e); var index = s - 1; for (var i = s; i <= e; ++i) { if (this[i] <= this[e]) this.swap(i, ++index); } stack.push(s, index - 1, index + 1, e); } } Array.prototype.mergeSort = function(s, e, b) { if (s == null) s = 0; if (e == null) e = this.length - 1; if (b == null) b = new Array(this.length); if (s >= e) return; var m = (s + e) >> 1; this.mergeSort(s, m, b); this.mergeSort(m + 1, e, b); for (var i = s, j = s, k = m + 1; i <= e; ++i) { b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++]; } for (var i = s; i <= e; ++i) this[i] = b[i]; } Array.prototype.heapSort = function() { for (var i = 1; i < this.length; ++i) { for (var j = i, k = (j - 1) >> 1; k >= 0; j = k, k = (k - 1) >> 1) { if (this[k] >= this[j]) break; this.swap(j, k); } } for (var i = this.length - 1; i > 0; --i) { this.swap(0, i); for (var j = 0, k = (j + 1) << 1; k <= i; j = k, k = (k + 1) << 1) { if (k == i || this[k] < this[k - 1]) --k; if (this[k] <= this[j]) break; this.swap(j, k); } } } function generate() { var max = parseInt(txtMax.value), count = parseInt(txtCount.value); if (isNaN(max) || isNaN(count)) { alert("个数和最大值必须是一个整数"); return; } var array = []; for (var i = 0; i < count; ++i) array.push(Math.round(Math.random() * max)); txtInput.value = array.join("\n"); txtOutput.value = ""; } function demo(type) { var array = txtInput.value == "" ? [] : txtInput.value.replace().split("\n"); for (var i = 0; i < array.length; ++i) array[i] = parseInt(array[i]); var t1 = new Date(); eval("array." + type + "Sort()"); var t2 = new Date(); lblTime.innerText = t2.valueOf() - t1.valueOf(); txtOutput.value = array.join("\n"); } </script>

随机数个数

最大随机数

耗时(毫秒)：

快速排序, 插入排序, 希尔排序, 冒泡排序, quickSort, insertSort, shellSort, bubbleSort, javascript排序
说明
写这个主要是为了锻炼自己，并无实际意义。
每个浏览器测试得出的数据会不一样。比如我用chrome 测试一般快速排序都会最快，IE 则根据数组长度有可能希尔最快。
不要用太大数据去测试冒泡排序(浏览器崩溃了我不管)
如果有兴趣可以下载测试页面

个人理解

冒泡排序：最简单，也最慢，貌似长度小于7最优
插入排序：比冒泡快，比快速排序和希尔排序慢，较小数据有优势
快速排序：这是一个非常快的排序方式，V8的sort方法就使用快速排序和插入排序的结合
希尔排序：在非chrome下数组长度小于1000，希尔排序比快速更快
系统方法：在forfox下系统的这个方法非常快

算法源码

复制代码代码如下:

 
// ---------- 一些排序算法 
// js 利用sort进行排序 
systemSort:function(array){ 
return array.sort(function(a, b){ 
return a - b; 
}); 
}, 
// 冒泡排序 
bubbleSort:function(array){ 
var i = 0, len = array.length, 
j, d; 
for(; ifor(j=0; jif(array[i] d = array[j]; 
array[j] = array[i]; 
array[i] = d; 
} 
} 
} 
return array; 
}, 
// 快速排序 
quickSort:function(array){ 
//var array = [8,4,6,2,7,9,3,5,74,5]; 
//var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7]; 
var i = 0; 
var j = array.length - 1; 
var Sort = function(i, j){ 
// 结束条件 
if(i == j ){ return }; 
var key = array[i]; 
var stepi = i; // 记录开始位置 
var stepj = j; // 记录结束位置 
while(j > i){ 
// j if(array[j] >= key){ 
j--; 
}else{ 
array[i] = array[j] 
//i++ ------------>>向后查找 
while(j > ++i){ 
if(array[i] > key){ 
array[j] = array[i]; 
break; 
} 
} 
} 
} 
// 如果第一个取出的 key 是最小的数 
if(stepi == i){ 
Sort(++i, stepj); 
return ; 
} 
// 最后一个空位留给 key 
array[i] = key; 
// 递归 
Sort(stepi, i); 
Sort(j, stepj); 
} 
Sort(i, j); 
return array; 
}, 
// 插入排序 
insertSort:function(array){ 
// http://baike.baidu.com/image/d57e99942da24e5dd21b7080 
// http://baike.baidu.com/view/396887.htm 
//var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7]; 
var i = 1, j, step, key, 
len = array.length; 
for(; i step = j = i; 
key = array[j]; 
while(--j > -1){ 
if(array[j] > key){ 
array[j+1] = array[j]; 
}else{ 
break; 
} 
} 
array[j+1] = key; 
} 
return array; 
}, 
// 希尔排序 
//Jun.array.shellSort(Jun.array.df(10000)); 
shellSort:function(array){ 
// http://zh.wikipedia.org/zh/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F 
// var array = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10]; 
var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse() 在维基上看到这个最优的步长 较小数组 
//var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1]//针对大数组的步长选择 
var i = 0; 
var stepArrLength = stepArr.length; 
var len = array.length; 
var len2 = parseInt(len/2); 
for(;i if(stepArr[i] > len2){ 
continue; 
} 
stepSort(stepArr[i]); 
} 
// 排序一个步长 
function stepSort(step){ 
//console.log(step) 使用的步长统计 
var i = 0, j = 0, f, tem, key; 
var stepLen = len%step > 0 ? parseInt(len/step) + 1 : len/step; 

for(;i for(j=1;/*j tem = f = step * j + i; 
key = array[f]; 
while((tem-=step) >= 0){// 依次向上查找 
if(array[tem] > key){ 
array[tem+step] = array[tem]; 
}else{ 
break; 
} 
} 
array[tem + step ] = key; 
} 
} 
} 
return array; 
} 

测试代码打包下载

陳述

本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn

快手双边市场的复杂实验设计问题Apr 15, 2023 pm 07:40 PM

一、问题背景1、双边市场实验介绍双边市场，即平台，包含生产者与消费者两方参与者，双方相互促进。比如快手有视频的生产者，视频的消费者，两种身份可能存在一定程度重合。双边实验是在生产者和消费者端组合分组的实验方式。双边实验具有以下优点：（1）可以同时检测新策略对两方面的影响，例如产品DAU和上传作品人数变化。双边平台往往有跨边网络效应，读者越多，作者越活跃，作者越活跃，读者也会跟着增加。（2）可以检测效果溢出和转移。（3）帮助我们更好得理解作用的机制，AB实验本身不能告诉我们原因和结果之间的关系，只

谷歌借AI打破十年排序算法封印，每天被执行数万亿次，网友却说是最不切实际的研究？Jun 22, 2023 pm 09:18 PM

整理|核子可乐，褚杏娟接触过基础计算机科学课程的朋友们，肯定都曾亲自动手设计排序算法——也就是借助代码将无序列表中的各个条目按升序或降序方式重新排列。这是个有趣的挑战，可行的操作方法也多种多样。人们曾投入大量时间探索如何更高效地完成排序任务。作为一项基础操作，大多数编程语言的标准库中都内置有排序算法。世界各地的代码库中使用了许多不同的排序技术和算法来在线组织大量数据，但至少就与LLVM编译器配套使用的C++库而言，排序代码已经有十多年没有任何变化了。近日，谷歌DeepMindAI小组如今开发出一

Vue技术开发中如何进行数据筛选和排序Oct 09, 2023 pm 01:25 PM

Vue技术开发中如何进行数据筛选和排序在Vue技术开发中，数据筛选和排序是非常常见和重要的功能。通过数据筛选和排序，我们可以快速查询和展示我们需要的信息，提高用户体验。本文将介绍在Vue中如何进行数据筛选和排序，并提供具体的代码示例，帮助读者更好地理解和运用这些功能。一、数据筛选数据筛选是指根据特定的条件筛选出符合要求的数据。在Vue中，我们可以通过comp

数组的排序算法有哪些？Jun 02, 2024 pm 10:33 PM

数组排序算法用于按特定顺序排列元素。常见的算法类型包括：冒泡排序：通过比较相邻元素交换位置。选择排序：找出最小元素交换到当前位置。插入排序：逐个插入元素到正确位置。快速排序：分治法，选择枢纽元素划分数组。合并排序：分治法，递归排序和合并子数组。

Swoole进阶：如何使用多线程实现高速排序算法Jun 14, 2023 pm 09:16 PM

Swoole是一款基于PHP语言的高性能网络通信框架，它支持多种异步IO模式和多种高级网络协议的实现。在Swoole的基础上，我们可以利用其多线程功能实现高效的算法运算，例如高速排序算法。高速排序算法（QuickSort）是一种常见的排序算法，通过定位一个基准元素，将元素分为两个子序列，小于基准元素的放在左侧，大于等于基准元素的放在右侧，再对左右子序列递归

如何实现C#中的选择排序算法Sep 20, 2023 pm 01:33 PM

如何实现C#中的选择排序算法选择排序（SelectionSort）是一种简单直观的排序算法，其基本思想是每次从待排序元素中选择最小（或最大）的元素，放到已排序的序列末尾。通过重复这个过程，直到所有元素都排序完成。下面我们来详细了解如何在C#中实现选择排序算法，同时附上具体的代码示例。创建选择排序方法首先，我们需要创建一个用于实现选择排序的方法。该方法接受一

如何使用MySQL和Java实现一个简单的排序算法功能Sep 20, 2023 am 09:45 AM

如何使用MySQL和Java实现一个简单的排序算法功能导言：在软件开发中，排序算法是非常基础且常用的功能之一。本文将介绍如何使用MySQL和Java实现一个简单的排序算法功能，并提供具体代码示例。一、排序算法概述排序算法是将一组数据按照特定规则进行排列的算法，常用的排序算法有冒泡排序、插入排序、选择排序、快速排序等。本文将以冒泡排序为例进行讲解及实现。二、M

如何使用C++中的基数排序算法Sep 19, 2023 pm 12:15 PM

如何使用C++中的基数排序算法基数排序算法是一种非比较性的排序算法，它通过将待排序的元素分割成一组有限的数字位来完成排序。在C++中，我们可以使用基数排序算法来对一组整数进行排序。下面我们将详细讨论如何实现基数排序算法，并附上具体的代码示例。算法思想基数排序算法的思想是将待排序的元素分割成一组有限的数字位，然后依次对每个位上的元素进行排序。在每个位上的排序完

See all articles