JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之基本排序算法定義與效率比較【冒泡、選擇、插入排序】
本文實(shí)例講述了JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之基本排序算法定義與效率比較。分享給大家供大家參考，具體如下：
javascript數(shù)據(jù)結(jié)構(gòu)與算法--基本排序算法（冒泡、選擇、排序）及效率比較
一、數(shù)組測(cè)試平臺(tái)
javascript數(shù)據(jù)結(jié)構(gòu)與算法--基本排序（封裝基本數(shù)組的操作），封裝常規(guī)數(shù)組操作的函數(shù)，比如：插入新數(shù)據(jù)，顯示數(shù)組數(shù)據(jù)，還有交換數(shù)組元素等操作來(lái)調(diào)用不同的排序算法
function CArray(numElements) {
this.dataStore = [];
this.pos = 0;//是一個(gè)索引值，默認(rèn)為0，從第一個(gè)開(kāi)始
this.numElements = numElements;//是保存所有的數(shù)組元素
this.insert = insert;//向數(shù)組中插入一個(gè)元素的方法
this.toString = toString;//顯示數(shù)組中所有元素
this.clear = clear;//清空數(shù)組數(shù)據(jù)
this.setData = setData;//生成了存儲(chǔ)在數(shù)組中的隨機(jī)數(shù)字
this.swap = swap;//交換數(shù)組中兩個(gè)元素的位置
this.bubbleSort = bubbleSort;
/*將傳入的數(shù)組，存儲(chǔ)在datastore中*/
for (var i = 0; i < numElements.length; ++i) {
this.dataStore[i] = numElements[i];
}
}
function setData() {
for (var i = 0; i < this.numElements; ++i) {
this.dataStore[i] = Math.floor(Math.random() *
(this.numElements+1));
}
}
function clear() {
for (var i = 0; i < this.dataStore.length; ++i) {
this.dataStore[i] = 0;
}
}
function insert(element) {
this.dataStore[this.pos++] = element;
}
function toString() {
var retstr = "";
for (var i = 0; i < this.dataStore.length; ++i) {
retstr += this.dataStore[i] + " ";
if (i > 0 && i % 10 == 0) {
retstr += "\n";
}
}
return retstr;
}
function swap(arr, index1, index2) {
var temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
//測(cè)試生成一組數(shù)組數(shù)據(jù)（隨機(jī)數(shù)）
var numElements = 100;
var myNums = new CArray(numElements);
myNums.setData();
console.log(myNums.toString());
17 94 81 80 25 24 73 76 24 35 81
63 81 59 4 76 30 47 73 98 18
54 36 53 47 22 60 88 41 66 24
73 94 40 45 72 74 14 61 92 48
36 12 42 11 12 82 24 84 60 1
17 98 63 36 84 13 18 50 89 26
98 1 6 54 52 69 6 52 98 14
79 28 19 69 76 99 97 100 10 7
24 54 81 73 18 21 45 73 66 30
28 56 54 21 88 31 20 86 48
二、冒泡排序算法
我們先來(lái)了解一下冒泡排序算法，它是最慢的排序算法之一，但也是一種最容易實(shí)現(xiàn)的排序算法。
之所以叫冒泡排序是因?yàn)槭褂眠@種排序算法排序時(shí)，數(shù)據(jù)值會(huì)像氣泡一樣從數(shù)組的一端漂浮到另一端。
假設(shè)正在將一組數(shù)字按照升序排列，較大的值會(huì)浮動(dòng)到數(shù)組的右側(cè)，而較小的值則會(huì)浮動(dòng)到數(shù)組的左側(cè)。
之所以會(huì)產(chǎn)生這種現(xiàn)象是因?yàn)樗惴〞?huì)多次在數(shù)組中移動(dòng)，比較相鄰的數(shù)據(jù)，當(dāng)左側(cè)值大于右側(cè)值時(shí)將它們進(jìn)行互換。
JS代碼如下：
function CArray(numElements) {
this.dataStore = [];
this.pos = 0;//是一個(gè)索引值，默認(rèn)為0，從第一個(gè)開(kāi)始
this.numElements = numElements;//是保存所有的數(shù)組元素
this.insert = insert;//向數(shù)組中插入一個(gè)元素的方法
this.toString = toString;//顯示數(shù)組中所有元素
this.clear = clear;//清空數(shù)組數(shù)據(jù)
this.setData = setData;//生成了存儲(chǔ)在數(shù)組中的隨機(jī)數(shù)字
this.swap = swap;//交換數(shù)組中兩個(gè)元素的位置
this.bubbleSort = bubbleSort;//冒泡算法
/*將傳入的數(shù)組，存儲(chǔ)在datastore中*/
for (var i = 0; i < numElements.length; ++i) {
this.dataStore[i] = numElements[i];
}
}
function setData() {
for (var i = 0; i < this.numElements; ++i) {
this.dataStore[i] = Math.floor(Math.random() *
(this.numElements+1));
}
}
function clear() {
for (var i = 0; i < this.dataStore.length; ++i) {
this.dataStore[i] = 0;
}
}
function insert(element) {
this.dataStore[this.pos++] = element;
}
function toString() {
var retstr = "";
for (var i = 0; i < this.dataStore.length; ++i) {
retstr += this.dataStore[i] + " ";
if (i > 0 && i % 10 == 0) {
retstr += "\n";
}
}
return retstr;
}
function swap(arr, index1, index2) {
var temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
function bubbleSort() {
var numElements = this.dataStore.length;
for (var outer = numElements; outer >= 2; --outer) {
for (var inner = 0; inner <= outer-1; ++inner) {
if (this.dataStore[inner] > this.dataStore[inner+1]) {
swap(this.dataStore, inner, inner+1);
}
}
console.log("outer為" + outer + ": " + this.toString());
}
}
//測(cè)試冒泡排序算法
var numElements = [2,4,1,3];
var myNums = new CArray(numElements);
console.log("原來(lái)的數(shù)組："+myNums.toString());
myNums.bubbleSort();
console.log("排序后的數(shù)組："+myNums.toString());
冒泡算法代碼分析如下：
原先數(shù)組為 [2,4,1,3];
1. outer為4的時(shí)候
1. inner為0，值為2，inner+1為1，值為4，不符合，不交換。
2. inner為1，值為4，inner+1為2，值為1，交換，數(shù)組變?yōu)閇2,1,4,3]
3. inner為2，值為4，inner+1為3，值為3，交換 數(shù)組變?yōu)閇2,1,3,4]
4. inner為3，值為4，inner+1為4，不符合 不交換。
2. outer為3的時(shí)候
1. inner為0，值為2，inner+1為1，值為1,交換 數(shù)組變?yōu)閇1,2,3,4]
2. inner為1, 值為2，inner+1為2，值為3 不符合 不交換。
3. inner為2, 值為3，inner+1為3，值為4，不符合 不交換。
再下面繼續(xù)循環(huán)都不符合條件，所以如上就是最后一步了。這就是冒泡排序。
三、選擇排序算法
選擇排序從數(shù)組的開(kāi)頭開(kāi)始，將第一個(gè)元素和其他元素進(jìn)行比較。
檢查完所有元素后，最小的元素會(huì)被放到數(shù)組的第一個(gè)位置，然后算法會(huì)從第二個(gè)位置繼續(xù)。
這個(gè)過(guò)程一直進(jìn)行，當(dāng)進(jìn)行到數(shù)組的倒數(shù)第二個(gè)位置時(shí)，所有的數(shù)據(jù)便完成了排序。
選擇排序會(huì)用到嵌套循環(huán)。
外循環(huán)從數(shù)組的第一個(gè)元素移動(dòng)到倒數(shù)第二個(gè)元素；
內(nèi)循環(huán)從第二個(gè)數(shù)組元素移動(dòng)到最后一個(gè)元素，查找比當(dāng)前外循環(huán)所指向的元素小的元素。
每次內(nèi)循環(huán)迭代后，數(shù)組中最小的值都會(huì)被賦值到合適的位置。
JS代碼如下：
function CArray(numElements) {
this.dataStore = [];
this.pos = 0;//是一個(gè)索引值，默認(rèn)為0，從第一個(gè)開(kāi)始
this.numElements = numElements;//是保存所有的數(shù)組元素
this.insert = insert;//向數(shù)組中插入一個(gè)元素的方法
this.toString = toString;//顯示數(shù)組中所有元素
this.clear = clear;//清空數(shù)組數(shù)據(jù)
this.setData = setData;//生成了存儲(chǔ)在數(shù)組中的隨機(jī)數(shù)字
this.swap = swap;//交換數(shù)組中兩個(gè)元素的位置
this.selectionSort = selectionSort;//選擇排序算法
/*將傳入的數(shù)組，存儲(chǔ)在datastore中*/
for (var i = 0; i < numElements.length; ++i) {
this.dataStore[i] = numElements[i];
}
}
function setData() {
for (var i = 0; i < this.numElements; ++i) {
this.dataStore[i] = Math.floor(Math.random() *
(this.numElements+1));
}
}
function clear() {
for (var i = 0; i < this.dataStore.length; ++i) {
this.dataStore[i] = 0;
}
}
function insert(element) {
this.dataStore[this.pos++] = element;
}
function toString() {
var retstr = "";
for (var i = 0; i < this.dataStore.length; ++i) {
retstr += this.dataStore[i] + " ";
if (i > 0 && i % 10 == 0) {
retstr += "\n";
}
}
return retstr;
}
function swap(arr, index1, index2) {
var temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
function selectionSort() {
var min, temp;
for (var outer = 0; outer <= this.dataStore.length-2; ++outer) {
min = outer;
for (var inner = outer + 1;inner <= this.dataStore.length-1; ++inner) {
if (this.dataStore[inner] < this.dataStore[min]) {
min = inner;
}
}
swap(this.dataStore, outer, min);
console.log("第"+outer +"次："+myNums.toString());
}
}
//測(cè)試排序算法
var numElements = [2,4,1,3];
var myNums = new CArray(numElements);
console.log("原來(lái)的數(shù)組："+myNums.toString());
myNums.selectionSort();
console.log("排序后的數(shù)組："+myNums.toString());
原來(lái)的數(shù)組：2 4 1 3
第0次：1 4 2 3
第1次：1 2 4 3
第2次：1 2 3 4
排序后的數(shù)組：1 2 3 4
四、插入排序算法
插入排序有兩個(gè)循環(huán)。
外循環(huán)將數(shù)組元素挨個(gè)移動(dòng)，而內(nèi)循環(huán)則對(duì)外循環(huán)中選中的元素及它前面的那個(gè)元素進(jìn)行比較。
如果外循環(huán)中選中的元素比內(nèi)循環(huán)中選中的元素小，那么數(shù)組元素會(huì)向右移動(dòng)，為外循環(huán)中的這個(gè)元素騰出位置
function CArray(numElements) {
this.dataStore = [];
this.pos = 0;//是一個(gè)索引值，默認(rèn)為0，從第一個(gè)開(kāi)始
this.numElements = numElements;//是保存所有的數(shù)組元素
this.insert = insert;//向數(shù)組中插入一個(gè)元素的方法
this.toString = toString;//顯示數(shù)組中所有元素
this.clear = clear;//清空數(shù)組數(shù)據(jù)
this.setData = setData;//生成了存儲(chǔ)在數(shù)組中的隨機(jī)數(shù)字
this.swap = swap;//交換數(shù)組中兩個(gè)元素的位置
this.insertionSort = insertionSort;//插入排序算法
/*將傳入的數(shù)組，存儲(chǔ)在datastore中*/
for (var i = 0; i < numElements.length; ++i) {
this.dataStore[i] = numElements[i];
}
}
function setData() {
for (var i = 0; i < this.numElements; ++i) {
this.dataStore[i] = Math.floor(Math.random() *
(this.numElements+1));
}
}
function clear() {
for (var i = 0; i < this.dataStore.length; ++i) {
this.dataStore[i] = 0;
}
}
function insert(element) {
this.dataStore[this.pos++] = element;
}
function toString() {
var retstr = "";
for (var i = 0; i < this.dataStore.length; ++i) {
retstr += this.dataStore[i] + " ";
if (i > 0 && i % 10 == 0) {
retstr += "\n";
}
}
return retstr;
}
function swap(arr, index1, index2) {
var temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
function insertionSort() {
var temp, inner;
//外循環(huán)將數(shù)組元素挨個(gè)移動(dòng)
for (var outer = 1; outer <= this.dataStore.length-1; ++outer) {
temp = this.dataStore[outer];//外循環(huán)選中的元素temp
inner = outer;
//內(nèi)循環(huán)對(duì)外循環(huán)中選中的元素temp與temp前面的元素一個(gè)個(gè)進(jìn)行比較。
//如果外循環(huán)中選中的元素temp比內(nèi)循環(huán)中選中的元素小，那么數(shù)組元素會(huì)向右移動(dòng)，為外循環(huán)中的這個(gè)元素騰出位置
while (inner > 0 && (this.dataStore[inner-1] >= temp)) {
this.dataStore[inner] = this.dataStore[inner-1];
--inner;
}
this.dataStore[inner] = temp;
console.log("第"+outer+"次："+myNums.toString());
}
}
//測(cè)試排序算法
var numElements = [9,1,8,6,2,3,5,4];
var myNums = new CArray(numElements);
console.log("原來(lái)的數(shù)組："+myNums.toString());
myNums.insertionSort();
console.log("排序后的數(shù)組："+myNums.toString());
原來(lái)的數(shù)組：9 1 8 6 2 3 5 4 //先用1和1前面的對(duì)比，9比1大，所以9向右移動(dòng)一個(gè)位置，給1騰位置
第1次：1 9 8 6 2 3 5 4 //用8與8前面的對(duì)比，9比8大，所以9向右移動(dòng)一個(gè)位置，給8騰位置
第2次：1 8 9 6 2 3 5 4 //用6與6前面的對(duì)比,8，9比6大，所以8、9向右移動(dòng)一個(gè)位置，給6騰位置
第3次：1 6 8 9 2 3 5 4
第4次：1 2 6 8 9 3 5 4
第5次：1 2 3 6 8 9 5 4
第6次：1 2 3 5 6 8 9 4
第7次：1 2 3 4 5 6 8 9
排序后的數(shù)組：1 2 3 4 5 6 8 9
五、基本排序算法的效率比較
function CArray(numElements) {
this.dataStore = [];
this.pos = 0;//是一個(gè)索引值，默認(rèn)為0，從第一個(gè)開(kāi)始
this.numElements = numElements;//是保存所有的數(shù)組元素
this.insert = insert;//向數(shù)組中插入一個(gè)元素的方法
this.toString = toString;//顯示數(shù)組中所有元素
this.clear = clear;//清空數(shù)組數(shù)據(jù)
this.setData = setData;//生成了存儲(chǔ)在數(shù)組中的隨機(jī)數(shù)字
this.swap = swap;//交換數(shù)組中兩個(gè)元素的位置
this.bubbleSort = bubbleSort;//冒泡排序算法
this.selectionSort = selectionSort;//選擇排序算法
this.insertionSort = insertionSort;//插入排序算法
/*將傳入的數(shù)組，存儲(chǔ)在datastore中*/
for (var i = 0; i < numElements.length; ++i) {
this.dataStore[i] = numElements[i];
}
}
function setData() {
for (var i = 0; i < this.numElements; ++i) {
this.dataStore[i] = Math.floor(Math.random() *
(this.numElements+1));
}
}
function clear() {
for (var i = 0; i < this.dataStore.length; ++i) {
this.dataStore[i] = 0;
}
}
function insert(element) {
this.dataStore[this.pos++] = element;
}
function toString() {
var retstr = "";
for (var i = 0; i < this.dataStore.length; ++i) {
retstr += this.dataStore[i] + " ";
if (i > 0 && i % 10 == 0) {
retstr += "\n";
}
}
return retstr;
}
function swap(arr, index1, index2) {
var temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
function bubbleSort() {
var numElements = this.dataStore.length;
for (var outer = numElements; outer >= 2; --outer) {
for (var inner = 0; inner <= outer-1; ++inner) {
if (this.dataStore[inner] > this.dataStore[inner+1]) {
swap(this.dataStore, inner, inner+1);
}
}
// console.log("outer為" + outer + ": " + this.toString());
}
}
function selectionSort() {
var min, temp;
for (var outer = 0; outer <= this.dataStore.length-2; ++outer) {
min = outer;
for (var inner = outer + 1;inner <= this.dataStore.length-1; ++inner) {
if (this.dataStore[inner] < this.dataStore[min]) {
min = inner;
}
}
swap(this.dataStore, outer, min);
// console.log("第"+outer +"次："+this.toString());
}
}
function insertionSort() {
var temp, inner;
//外循環(huán)將數(shù)組元素挨個(gè)移動(dòng)
for (var outer = 1; outer <= this.dataStore.length-1; ++outer) {
temp = this.dataStore[outer];//外循環(huán)選中的元素
inner = outer;
//內(nèi)循環(huán)則對(duì)外循環(huán)中選中的元素與它前面的那個(gè)元素進(jìn)行比較。
//如果外循環(huán)中選中的元素比內(nèi)循環(huán)中選中的元素小，那么數(shù)組元素會(huì)向右移動(dòng)，為外循環(huán)中的這個(gè)元素騰出位置
while (inner > 0 && (this.dataStore[inner-1] >= temp)) {
this.dataStore[inner] = this.dataStore[inner-1];
--inner;
}
this.dataStore[inner] = temp;
// console.log("第"+outer+"次："+this.toString());
}
}
/*測(cè)試冒泡、選擇、插入算法的效率*/
var numElements = 10000;
var nums = new CArray(numElements);
nums.setData();
var start = new Date().getTime();
nums.bubbleSort();
var stop = new Date().getTime();
var elapsed = stop - start;
console.log("用冒泡算法，排序 " + numElements + " 個(gè)元素耗時(shí) : " + elapsed + " milliseconds.");
start = new Date().getTime();
nums.selectionSort();
stop = new Date().getTime();
elapsed = stop - start;
console.log("用選擇算法，排序 " + numElements + " 個(gè)元素耗時(shí): " + elapsed + " milliseconds.");
start = new Date().getTime();
nums.insertionSort();
stop = new Date().getTime();
elapsed = stop - start;
console.log("用插入算法，排序 " + numElements + " 個(gè)元素耗時(shí): " + elapsed + " milliseconds.");
運(yùn)行結(jié)果：
選擇排序和插入排序要比冒泡排序快，插入排序是這三種算法中最快的。
感興趣的朋友可以使用在線(xiàn)HTML/CSS/JavaScript代碼運(yùn)行工具：http://tools.jb51.net/code/HtmlJsRun測(cè)試上述代碼運(yùn)行效果。
PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：
在線(xiàn)動(dòng)畫(huà)演示插入/選擇/冒泡/歸并/希爾/快速排序算法過(guò)程工具：
http://tools.jb51.net/aideddesign/paixu_ys
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》
希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。
相關(guān)文章
這篇文章主要介紹了javascript實(shí)現(xiàn)微信分享，非常的實(shí)用，小伙伴們參考下吧2014-12-12
JS模擬實(shí)現(xiàn)Excel條件格式中的色階效果
這篇文章主要為大家詳細(xì)介紹了如何利用JavaScript模擬實(shí)現(xiàn)Excel條件格式中的色階效果，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以嘗試一下2023-05-05
這篇文章主要針對(duì)微信jssdk用法進(jìn)行匯總，通過(guò)ready接口處理成功驗(yàn)證、通過(guò)error接口處理失敗驗(yàn)證等內(nèi)容介紹，感興趣的小伙伴們可以參考一下2016-07-07
Javascript setInterval的兩種調(diào)用方法(實(shí)例講解)
這篇文章主要是對(duì)Javascript setInterval的兩種調(diào)用方法解析了詳細(xì)的分析介紹，需要的朋友可以過(guò)來(lái)參考下，希望對(duì)大家有所幫助2013-11-11
如果你不能向一個(gè)六歲的孩子解釋清楚，那么其實(shí)你自己根本就沒(méi)弄懂。好吧，我試著向一個(gè)27歲的朋友就是JS閉包(JavaScript closure)卻徹底失敗了2011-10-10
當(dāng)代碼在一個(gè)環(huán)境中執(zhí)行時(shí),會(huì)創(chuàng)建變量對(duì)象的一個(gè)作用域鏈,作用域鏈的用途是保證對(duì)執(zhí)行環(huán)境有權(quán)訪問(wèn)的所有變量和函數(shù)的有序訪問(wèn),下面這篇文章主要給大家介紹了關(guān)于JavaScript作用域鏈底層原理的相關(guān)資料,需要的朋友可以參考下2021-11-11
在JavaScript中,幾乎每一個(gè)值都是某種特定類(lèi)型的對(duì)象,于是ES6也著重提升了對(duì)象的功能性,下面這篇文章主要給大家介紹了關(guān)于es6新增對(duì)象實(shí)用方法的相關(guān)資料,需要的朋友可以參考下2022-05-05
promise處理多個(gè)相互依賴(lài)的異步請(qǐng)求(實(shí)例講解)
下面小編就為大家?guī)?lái)一篇promise處理多個(gè)相互依賴(lài)的異步請(qǐng)求(實(shí)例講解)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-08-08
本文介紹了JavaScript中的this關(guān)鍵詞指向，this是JavaScript的一個(gè)關(guān)鍵字，他是函數(shù)執(zhí)行過(guò)程中，自動(dòng)生成的一個(gè)內(nèi)部對(duì)象，指當(dāng)前的對(duì)象，只在當(dāng)前函數(shù)內(nèi)部使用，更多相關(guān)資料需要的小伙伴可以參考下面文章內(nèi)容2022-05-05
javascript中的變量作用域以及變量提升詳細(xì)介紹
在javascript中， 理解變量的作用域以及變量提升是非常有必要的。這個(gè)看起來(lái)是否很簡(jiǎn)單，但其實(shí)并不是你想的那樣，還要一些重要的細(xì)節(jié)你需要理解2013-10-10