幾種經(jīng)典排序算法的JS實(shí)現(xiàn)方法
更新時(shí)間：2016年03月25日 14:17:14 投稿：jingxian
下面小編就為大家?guī)?lái)一篇幾種經(jīng)典排序算法的JS實(shí)現(xiàn)方法。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
一.冒泡排序
function BubbleSort(array) {
var length = array.length;
for (var i = length - 1; i > 0; i--) { //用于縮小范圍
for (var j = 0; j < i; j++) { //在范圍內(nèi)進(jìn)行冒泡，在此范圍內(nèi)最大的一個(gè)將冒到最后面
if (array[j] > array[j+1]) {
var temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
console.log(array);
console.log("-----------------------------");
}
return array;
}
var arr = [10,9,8,7,7,6,5,11,3];
var result = BubbleSort(arr);
console.log(result);
/*
[ 9, 8, 7, 7, 6, 5, 10, 3, 11 ]
-----------------------------
[ 8, 7, 7, 6, 5, 9, 3, 10, 11 ]
-----------------------------
[ 7, 7, 6, 5, 8, 3, 9, 10, 11 ]
-----------------------------
[ 7, 6, 5, 7, 3, 8, 9, 10, 11 ]
-----------------------------
[ 6, 5, 7, 3, 7, 8, 9, 10, 11 ]
-----------------------------
[ 5, 6, 3, 7, 7, 8, 9, 10, 11 ]
-----------------------------
[ 5, 3, 6, 7, 7, 8, 9, 10, 11 ]
-----------------------------
[ 3, 5, 6, 7, 7, 8, 9, 10, 11 ]
-----------------------------
[ 3, 5, 6, 7, 7, 8, 9, 10, 11 ]
*/
二.選擇排序
function SelectionSort(array) {
var length = array.length;
for (var i = 0; i < length; i++) { //縮小選擇的范圍
var min = array[i]; //假定范圍內(nèi)第一個(gè)為最小值
var index = i; //記錄最小值的下標(biāo)
for (var j = i + 1; j < length; j++) { //在范圍內(nèi)選取最小值
if (array[j] < min) {
min = array[j];
index = j;
}
}
if (index != i) { //把范圍內(nèi)最小值交換到范圍內(nèi)第一個(gè)
var temp = array[i];
array[i] = array[index];
array[index] = temp;
}
console.log(array);
console.log("---------------------");
}
return array;
}
var arr = [ 1, 10, 100, 90, 65, 5, 4, 10, 2, 4 ];
var result = SelectionSort(arr);
console.log(result);
/*
[ 1, 10, 100, 90, 65, 5, 4, 10, 2, 4 ]
---------------------
[ 1, 2, 100, 90, 65, 5, 4, 10, 10, 4 ]
---------------------
[ 1, 2, 4, 90, 65, 5, 100, 10, 10, 4 ]
---------------------
[ 1, 2, 4, 4, 65, 5, 100, 10, 10, 90 ]
---------------------
[ 1, 2, 4, 4, 5, 65, 100, 10, 10, 90 ]
---------------------
[ 1, 2, 4, 4, 5, 10, 100, 65, 10, 90 ]
---------------------
[ 1, 2, 4, 4, 5, 10, 10, 65, 100, 90 ]
---------------------
[ 1, 2, 4, 4, 5, 10, 10, 65, 100, 90 ]
---------------------
[ 1, 2, 4, 4, 5, 10, 10, 65, 90, 100 ]
---------------------
[ 1, 2, 4, 4, 5, 10, 10, 65, 90, 100 ]
---------------------
[ 1, 2, 4, 4, 5, 10, 10, 65, 90, 100 ]
*/
三.插入排序
function InsertionSort(array) {
var length = array.length;
for (var i = 0; i < length - 1; i++) {
//i代表已經(jīng)排序好的序列最后一項(xiàng)下標(biāo)
var insert = array[i+1];
var index = i + 1;//記錄要被插入的下標(biāo)
for (var j = i; j >= 0; j--) {
if (insert < array[j]) {
//要插入的項(xiàng)比它小，往后移動(dòng)
array[j+1] = array[j];
index = j;
}
}
array[index] = insert;
console.log(array);
console.log("-----------------------");
}
return array;
}
var arr = [100,90,80,62,80,8,1,2,39];
var result = InsertionSort(arr);
console.log(result);
/*
[ 90, 100, 80, 62, 80, 8, 1, 2, 39 ]
-----------------------
[ 80, 90, 100, 62, 80, 8, 1, 2, 39 ]
-----------------------
[ 62, 80, 90, 100, 80, 8, 1, 2, 39 ]
-----------------------
[ 62, 80, 80, 90, 100, 8, 1, 2, 39 ]
-----------------------
[ 8, 62, 80, 80, 90, 100, 1, 2, 39 ]
-----------------------
[ 1, 8, 62, 80, 80, 90, 100, 2, 39 ]
-----------------------
[ 1, 2, 8, 62, 80, 80, 90, 100, 39 ]
-----------------------
[ 1, 2, 8, 39, 62, 80, 80, 90, 100 ]
-----------------------
[ 1, 2, 8, 39, 62, 80, 80, 90, 100 ]
*/
四.希爾排序
function ShellSort(array) {
var length = array.length;
var gap = Math.round(length / 2);
while (gap > 0) {
for (var i = gap; i < length; i++) {
var insert = array[i];
var index = i;
for (var j = i; j >= 0; j-=gap) {
if (insert < array[j]) {
array[j+gap] = array[j];
index = j;
}
}
array[index] = insert;
}
console.log(array);
console.log("-----------------------");
gap = Math.round(gap/2 - 0.1);
}
return array;
}
var arr = [ 13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10 ];
var result = ShellSort(arr);
console.log(result);
/*
[ 13, 14, 45, 27, 73, 25, 39, 10, 65, 23, 94, 33, 82, 25, 59, 94 ]
-----------------------
[ 13, 14, 39, 10, 65, 23, 45, 27, 73, 25, 59, 33, 82, 25, 94, 94 ]
-----------------------
[ 13, 10, 39, 14, 45, 23, 59, 25, 65, 25, 73, 27, 82, 33, 94, 94 ]
-----------------------
[ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
-----------------------
[ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
*/
五.歸并排序
function MergeSort(array) {
var length = array.length;
if (length <= 1) {
return array;
} else {
var num = Math.ceil(length/2);
var left = MergeSort(array.slice(0, num));
var right = MergeSort(array.slice(num, length));
return merge(left, right);
}
}
function merge(left, right) {
console.log(left);
console.log(right);
var a = new Array();
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
var temp = left.shift();
a.push(temp);
} else {
var temp = right.shift();
a.push(temp);
}
}
if (left.length > 0) {
a = a.concat(left);
}
if (right.length > 0) {
a = a.concat(right);
}
console.log(a);
console.log("-----------------------------");
return a;
}
var arr = [ 13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10 ];
var result = MergeSort(arr);
console.log(result);
/*
[ 13 ]
[ 14 ]
[ 13, 14 ]
-----------------------------
[ 94 ]
[ 33 ]
[ 33, 94 ]
-----------------------------
[ 13, 14 ]
[ 33, 94 ]
[ 13, 14, 33, 94 ]
-----------------------------
[ 82 ]
[ 25 ]
[ 25, 82 ]
-----------------------------
[ 59 ]
[ 94 ]
[ 59, 94 ]
-----------------------------
[ 25, 82 ]
[ 59, 94 ]
[ 25, 59, 82, 94 ]
-----------------------------
[ 13, 14, 33, 94 ]
[ 25, 59, 82, 94 ]
[ 13, 14, 25, 33, 59, 82, 94, 94 ]
-----------------------------
[ 65 ]
[ 23 ]
[ 23, 65 ]
-----------------------------
[ 45 ]
[ 27 ]
[ 27, 45 ]
-----------------------------
[ 23, 65 ]
[ 27, 45 ]
[ 23, 27, 45, 65 ]
-----------------------------
[ 73 ]
[ 25 ]
[ 25, 73 ]
-----------------------------
[ 39 ]
[ 10 ]
[ 10, 39 ]
-----------------------------
[ 25, 73 ]
[ 10, 39 ]
[ 10, 25, 39, 73 ]
-----------------------------
[ 23, 27, 45, 65 ]
[ 10, 25, 39, 73 ]
[ 10, 23, 25, 27, 39, 45, 65, 73 ]
-----------------------------
[ 13, 14, 25, 33, 59, 82, 94, 94 ]
[ 10, 23, 25, 27, 39, 45, 65, 73 ]
[ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
-----------------------------
[ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
*/
六.快速排序
function QuickSort(array) {
var length = array.length;
if (length <= 1) {
return array;
} else {
var smaller = [];
var bigger = [];
var base = [array[0]];
for (var i = 1; i < length; i++) {
if (array[i] <= base[0]) {
smaller.push(array[i]);
} else {
bigger.push(array[i]);
}
}
console.log(smaller.concat(base.concat(bigger)));
console.log("-----------------------");
return QuickSort(smaller).concat(base.concat(QuickSort(bigger)));
}
}
var arr = [ 8, 10, 100, 90, 65, 5, 4, 10, 2, 4 ];
var result = QuickSort(arr);
console.log(result);
/*
[ 5, 4, 2, 4, 8, 10, 100, 90, 65, 10 ]
-----------------------
[ 4, 2, 4, 5 ]
-----------------------
[ 2, 4, 4 ]
-----------------------
[ 2, 4 ]
-----------------------
[ 10, 10, 100, 90, 65 ]
-----------------------
[ 90, 65, 100 ]
-----------------------
[ 65, 90 ]
-----------------------
[ 2, 4, 4, 5, 8, 10, 10, 65, 90, 100 ]
*/
以上這篇幾種經(jīng)典排序算法的JS實(shí)現(xiàn)方法就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
您可能感興趣的文章:
相關(guān)文章
這篇文章主要介紹了JavaScript中var關(guān)鍵字的使用,是JavaScript入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-08-08
JavaScript中匿名、命名函數(shù)的性能測(cè)試
這篇文章主要介紹了JavaScript中匿名、命名函數(shù)的性能測(cè)試,簡(jiǎn)單來(lái)講匿名即沒(méi)有名字的函數(shù),它和命名函數(shù)相比性能如何呢,本文即是對(duì)它們性能的測(cè)試,需要的朋友可以參考下2014-09-09
這篇文章主要介紹了理解javascript回調(diào)函數(shù)的相關(guān)資料,需要的朋友可以參考下2014-12-12
JavaScript字符串處理(String對(duì)象)詳解
這篇文章主要介紹了JavaScript字符串處理(String對(duì)象)詳解,本文列出并詳細(xì)講解了String對(duì)象的一些方法,需要的朋友可以參考下2014-10-10
基于JavaScript自定義構(gòu)造函數(shù)的詳解說(shuō)明
本篇文章小編為大家介紹，基于JavaScript自定義構(gòu)造函數(shù)的詳解說(shuō)明。需要的朋友參考下2013-04-04
這篇文章主要介紹了JavaScript中pop()方法的使用教程,是JS入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-06-06
這篇文章主要介紹了javascript工廠方式定義對(duì)象,以及另外3中創(chuàng)建對(duì)象的方式，需要的朋友可以參考下2014-12-12
JavaScript中window、doucment、body的解釋
JavaScript中window、doucment、body是什么意思呢，下面為大家做個(gè)介紹，不知道的朋友可以參考下2013-08-08
javascript 構(gòu)造函數(shù)方式定義對(duì)象
這篇文章主要介紹了javascript 構(gòu)造函數(shù)方式定義對(duì)象的方法及示例,需要的朋友可以參考下2015-01-01
貼一個(gè)在Mozilla中常用的Javascript代碼
貼一個(gè)在Mozilla中常用的Javascript代碼...2007-01-01