javascript常见排序算法总结
算法是程序的灵魂。虽然在前端的开发环境中排序算法不是很经常用到,但常见的排序算法还是应该要掌握的。我在这里从网上整理了一下常见排序算法的javascript实现,方便以后查阅。
归并排序:
function merge(left, right){
var result = [],
il = 0,
ir = 0;
while (il < left.length && ir < right.length){
if (left[il] < right[ir]){
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
return result.concat(left.slice(il)).concat(right.slice(ir));
}
function mergeSort(items){
// 结束条件: 数组元素少于2个
if (items.length < 2) {
return items;
}
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function mergeSort2(items){
if (items.length < 2) {
return items;
}
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle),
params = merge(mergeSort(left), mergeSort(right));
params.unshift(0, items.length);
items.splice.apply(items, params);
return items;
}
插入排序:
function insertionSort(items) {
var len = items.length,
value,
i,
j;
for (i=0; i < len; i++) {
value = items[i];
for (j=i-1; j > -1 && items[j] > value; j--) {
items[j+1] = items[j];
}
items[j+1] = value;
}
return items;
}
选择排序:
function swap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}
function selectionSort(items){
var len = items.length,
min;
for (i=0; i < len; i++){
min = i;
for (j=i+1; j < len; j++){
if (items[j] < items[min]){
min = j;
}
}
if (i != min){
swap(items, i, min);
}
}
return items;
}
冒泡排序:
function swap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}
function bubbleSort(items){
var len = items.length,
i, j, stop;
for (i=0; i < len; i++){
for (j=0, stop=len-i; j < stop; j++){
if (items[j] > items[j+1]){
swap(items, j, j+1);
}
}
}
return items;
}
快速排序:
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
二分法查找:
function binarySearch(items, value){
var startIndex = 0,
stopIndex = items.length - 1,
middle = Math.floor((stopIndex + startIndex)/2);
while(items[middle] != value && startIndex < stopIndex){
if (value < items[middle]){
stopIndex = middle - 1;
} else if (value > items[middle]){
startIndex = middle + 1;
}
middle = Math.floor((stopIndex + startIndex)/2);
}
return (items[middle] != value) ? -1 : middle;
}
基数排序:
var countSort = function(array) {
var i, z = 0, count = [],
min = Math.min.apply({}, array),
max = Math.max.apply({}, array),
size = array.length;
//给新数组预填为零
for (i = min; i <= max; i++) {
count[i] = 0;
}
for (i=0; i < size; i++) {
count[array[i]]++;
}
for (i = min; i <= max; i++) {
while (count[i]-- > 0) {//循环新数组,如果不为零,则把i返回array
array[z++] = i;
}
}
return array;
}
希尔排序:
function shellSort(array) {
var j, i, v, h=1, s=3, k,n = array.length;
var result = "";
var count = 0;
while(h < n)
h=s*h+1;
while(h > 1) {
h=(h-1)/s;
for (k=0; k<h; k++)
for (i=k+h,j=i; i<n; i+=h, j=i) {
v=array[i];
while(true)
if ((j-=h) >= 0 && array[j] > v)
array[j+h]=array[j];
else
break;
array[j+h]=v;
}
count++;
result += "<br />第" + count + "遍排序的结果是:";
for (var n = 0; n < array.length; n++) {
result += array[n] + ",";
}
}
return result;
}
组合排序:
var combSort = function(array){
var gap = array.length;
do{
gap = gap * 10 / 13
if(gap === 9 || gap === 10)
gap = 11
if(gap < 1){
gap = 1
}
var swapped = false;
for(var i=0;i<array.length-gap;i++){
var j = i + gap
if(array[i]>array[j]){
var temp = array[i];
array[i] = array[j];
array[j] = temp;
test(array)
swapped = true
}
}
if(gap == 1 && !swapped){
break;
}
}while(1);
}
鸡尾酒排序:
var cocktailSort= function(array) {
var top = array.length - 1, bottom = 0,flag = true,i, j;
while (flag) {
flag = false;
//从左到右到大,把最大的放到每次范围的最右边
for (i = bottom; i < top; i++) {
if (array[i] > array[i + 1]) {
swap(array, i, i + 1);
flag = true;
}
}
top--;
//从右到到左,把最小的放到每次范围的最小边
for (j = top; j > bottom; j--) {
if (array[j] < array[j - 1]) {
swap(array, j, j - 1);
flag = true;
}
}
bottom++;
}
}
var swap = function(array,a,b){
var tmp = array[a];
array[a] = array[b]
array[b] = tmp;
}
转自:http://www.cnblogs.com/chenguangyin/archive/2012/11/19/2777757.html
分享到:
相关推荐
JavaScript 中常见排序算法详解
JavaScript中常见排序算法详解共19页.pdf.zip
JavaScript中常见排序算法详解共19页.pdf.zip
【项目资源】: 包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发、大数据、课程资源、音视频、网站开发等各种技术项目的源码。 ... 【项目质量】: 所有源码都经过严格测试,...
常见排序算法(JS版)
十大经典排序算法 (1)多种编程语言,JavaScript,python,go,php等语言。 (2)排序算法可以分为内部排序...常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序
开发中,遇到数组排序的需求很频繁,这篇文章会介绍几个常见排序思路。 一、希尔排序(性能最好) 如果要从大到小排列,则 while(arr[n] > arr[n – interval] && n > 0) 。 // 希尔排序算法 function xier(arr){ ...
用JavaScript实现的常见排序算法:冒泡排序,选择排序,插入排序,谢尔排序,快速排序(递归),快速排序(堆栈),归并排序,堆排序。
JavaScript实现的常见排序算法有:冒泡排序,选择排序,插入排序,谢尔排序,快速排序(递归),快速排序(堆栈),归并排序,堆排序。今天我们来详细分析下快速排序算法
本文实例讲述了基于JavaScript实现的插入排序算法。分享给大家供大家参考,具体如下: 根据排序过程中使用的存储器不同,可以将排序方法分为两大类:内部排序和外部排序。 内部排序是指待排序记录存放在计算机随机...
因为javascript array 之sort 经过脚本引擎优化,性能往往比自己写的好。
用JavaScript实现的常见排序算法和数据结构的交互式概述。 还包括其他一些算法挑战,类似于编程采访中提出的挑战。 这旨在帮助您在准备面试时掌握计算机科学的基础知识,算法和解决问题的技能! 这仅作为参考/评论-...
JavaScript中几种常见排序算法小结,学习js的朋友可以参考下,下面对多种方法进行了简单的小结。
我决定为一些常见的排序算法实现一个可视化工具,同时还学习Web应用程序编程。 我允许用户通过不同的提示和速度控制来可视化算法如何执行排序,同时还可以方便地计算每个算法进行的比较和交换次数,以此作为性能的...
不同的排序算法,执行效率有着天壤之别,本脚本用JavaScript演示了各种常见的排序算法,包括:冒泡排序、选择排序、插入排序、谢尔排序、快速排序(递归)、快速排序(堆栈)、归并排序、堆排序
9-1 排序链表-原理讲解 9-2 排序链表-代码实操 9-3 环形链表-原理讲解 9-4 环形链表-代码实操第10章 数据结构之“矩阵”矩阵虽不常见,若见既是霹雳。看似和数组无异,操作起来如同嚼蜡。别怕,同样是数组API、递归...