您好,登錄后才能下訂單哦!
這篇文章主要介紹JavaScript中基本排序算法定義與效率比較的示例分析,文中介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們一定要看完!
一、數(shù)組測(cè)試平臺(tái)
javascript數(shù)據(jù)結(jié)構(gòu)與算法--基本排序(封裝基本數(shù)組的操作),封裝常規(guī)數(shù)組操作的函數(shù),比如:插入新數(shù)據(jù),顯示數(shù)組數(shù)據(jù),還有交換數(shù)組元素等操作來調(diào)用不同的排序算法
function CArray(numElements) { this.dataStore = []; this.pos = 0;//是一個(gè)索引值,默認(rèn)為0,從第一個(gè)開始 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
二、冒泡排序算法
我們先來了解一下冒泡排序算法,它是最慢的排序算法之一,但也是一種最容易實(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è)開始 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("原來的數(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ù)組的開頭開始,將第一個(gè)元素和其他元素進(jìn)行比較。
檢查完所有元素后,最小的元素會(huì)被放到數(shù)組的第一個(gè)位置,然后算法會(huì)從第二個(gè)位置繼續(xù)。
這個(gè)過程一直進(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è)開始 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("原來的數(shù)組:"+myNums.toString()); myNums.selectionSort(); console.log("排序后的數(shù)組:"+myNums.toString());
原來的數(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è)開始 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("原來的數(shù)組:"+myNums.toString()); myNums.insertionSort(); console.log("排序后的數(shù)組:"+myNums.toString());
原來的數(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è)開始 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é)果:
選擇排序和插入排序要比冒泡排序快,插入排序是這三種算法中最快的。
以上是“JavaScript中基本排序算法定義與效率比較的示例分析”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對(duì)大家有幫助,更多相關(guān)知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。