點擊下載
本文文檔

當前位置：首頁 - 科技 - 知識百科 - 正文

JavaScript數據結構與算法之基本排序算法定義與效率比較【冒泡、選擇、插入排序】

來源：懂視網責編：小采時間：2020-11-27 22:00:45

JavaScript數據結構與算法之基本排序算法定義與效率比較【冒泡、選擇、插入排序】

JavaScript數據結構與算法之基本排序算法定義與效率比較【冒泡、選擇、插入排序】:本文實例講述了JavaScript數據結構與算法之基本排序算法定義與效率比較。分享給大家供大家參考，具體如下： javascript數據結構與算法--基本排序算法（冒泡、選擇、排序）及效率比較一、數組測試平臺 javascript數據結構與算法--基本排序（封裝基本數組的

推薦度：

點擊下載本文 文檔為doc格式

導讀JavaScript數據結構與算法之基本排序算法定義與效率比較【冒泡、選擇、插入排序】:本文實例講述了JavaScript數據結構與算法之基本排序算法定義與效率比較。分享給大家供大家參考，具體如下： javascript數據結構與算法--基本排序算法（冒泡、選擇、排序）及效率比較一、數組測試平臺 javascript數據結構與算法--基本排序（封裝基本數組的

二、冒泡排序算法

我們先來了解一下冒泡排序算法，它是最慢的排序算法之一，但也是一種最容易實現的排序算法。

之所以叫冒泡排序是因為使用這種排序算法排序時，數據值會像氣泡一樣從數組的一端漂浮到另一端。

假設正在將一組數字按照升序排列，較大的值會浮動到數組的右側，而較小的值則會浮動到數組的左側。

之所以會產生這種現象是因為算法會多次在數組中移動，比較相鄰的數據，當左側值大于右側值時將它們進行互換。

JS代碼如下：

function CArray(numElements) {
 this.dataStore = [];
 this.pos = 0;//是一個索引值，默認為0，從第一個開始
 this.numElements = numElements;//是保存所有的數組元素
 this.insert = insert;//向數組中插入一個元素的方法
 this.toString = toString;//顯示數組中所有元素
 this.clear = clear;//清空數組數據
 this.setData = setData;//生成了存儲在數組中的隨機數字
 this.swap = swap;//交換數組中兩個元素的位置
 this.bubbleSort = bubbleSort;//冒泡算法
 /*將傳入的數組，存儲在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());
 }
}
//測試冒泡排序算法
var numElements = [2,4,1,3];
var myNums = new CArray(numElements);
console.log("原來的數組："+myNums.toString());
myNums.bubbleSort();
console.log("排序后的數組："+myNums.toString());

冒泡算法代碼分析如下：

原先數組為 [2,4,1,3];

1. outer為4的時候

    1. inner為0，值為2，inner+1為1，值為4，不符合，不交換。
    2. inner為1，值為4，inner+1為2，值為1，交換，數組變為[2,1,4,3]
    3. inner為2，值為4，inner+1為3，值為3，交換數組變為[2,1,3,4]
    4. inner為3，值為4，inner+1為4，不符合不交換。

2. outer為3的時候

    1. inner為0，值為2，inner+1為1，值為1,交換數組變為[1,2,3,4]
    2. inner為1, 值為2，inner+1為2，值為3 不符合不交換。
    3. inner為2, 值為3，inner+1為3，值為4，不符合不交換。

再下面繼續循環都不符合條件，所以如上就是最后一步了。這就是冒泡排序。

三、選擇排序算法

選擇排序從數組的開頭開始，將第一個元素和其他元素進行比較。

檢查完所有元素后，最小的元素會被放到數組的第一個位置，然后算法會從第二個位置繼續。

這個過程一直進行，當進行到數組的倒數第二個位置時，所有的數據便完成了排序。
選擇排序會用到嵌套循環。

外循環從數組的第一個元素移動到倒數第二個元素；

內循環從第二個數組元素移動到最后一個元素，查找比當前外循環所指向的元素小的元素。

每次內循環迭代后，數組中最小的值都會被賦值到合適的位置。

JS代碼如下：

function CArray(numElements) {
 this.dataStore = [];
 this.pos = 0;//是一個索引值，默認為0，從第一個開始
 this.numElements = numElements;//是保存所有的數組元素
 this.insert = insert;//向數組中插入一個元素的方法
 this.toString = toString;//顯示數組中所有元素
 this.clear = clear;//清空數組數據
 this.setData = setData;//生成了存儲在數組中的隨機數字
 this.swap = swap;//交換數組中兩個元素的位置
 this.selectionSort = selectionSort;//選擇排序算法
 /*將傳入的數組，存儲在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());
 }
}
//測試排序算法
var numElements = [2,4,1,3];
var myNums = new CArray(numElements);
console.log("原來的數組："+myNums.toString());
myNums.selectionSort();
console.log("排序后的數組："+myNums.toString());

原來的數組：2 4 1 3
第0次：1 4 2 3
第1次：1 2 4 3
第2次：1 2 3 4
排序后的數組：1 2 3 4

四、插入排序算法

插入排序有兩個循環。

外循環將數組元素挨個移動，而內循環則對外循環中選中的元素及它前面的那個元素進行比較。

如果外循環中選中的元素比內循環中選中的元素小，那么數組元素會向右移動，為外循環中的這個元素騰出位置

function CArray(numElements) {
 this.dataStore = [];
 this.pos = 0;//是一個索引值，默認為0，從第一個開始
 this.numElements = numElements;//是保存所有的數組元素
 this.insert = insert;//向數組中插入一個元素的方法
 this.toString = toString;//顯示數組中所有元素
 this.clear = clear;//清空數組數據
 this.setData = setData;//生成了存儲在數組中的隨機數字
 this.swap = swap;//交換數組中兩個元素的位置
 this.insertionSort = insertionSort;//插入排序算法
 /*將傳入的數組，存儲在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;
 //外循環將數組元素挨個移動
 for (var outer = 1; outer <= this.dataStore.length-1; ++outer) {
 temp = this.dataStore[outer];//外循環選中的元素temp
 inner = outer;
 //內循環對外循環中選中的元素temp與temp前面的元素一個個進行比較。
 //如果外循環中選中的元素temp比內循環中選中的元素小，那么數組元素會向右移動，為外循環中的這個元素騰出位置
 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());
 }
}
//測試排序算法
var numElements = [9,1,8,6,2,3,5,4];
var myNums = new CArray(numElements);
console.log("原來的數組："+myNums.toString());
myNums.insertionSort();
console.log("排序后的數組："+myNums.toString());

原來的數組：9 1 8 6 2 3 5 4 //先用1和1前面的對比，9比1大，所以9向右移動一個位置，給1騰位置
      第1次：1 9 8 6 2 3 5 4 //用8與8前面的對比，9比8大，所以9向右移動一個位置，給8騰位置
      第2次：1 8 9 6 2 3 5 4 //用6與6前面的對比,8，9比6大，所以8、9向右移動一個位置，給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
排序后的數組：1 2 3 4 5 6 8 9

五、基本排序算法的效率比較

function CArray(numElements) {
 this.dataStore = [];
 this.pos = 0;//是一個索引值，默認為0，從第一個開始
 this.numElements = numElements;//是保存所有的數組元素
 this.insert = insert;//向數組中插入一個元素的方法
 this.toString = toString;//顯示數組中所有元素
 this.clear = clear;//清空數組數據
 this.setData = setData;//生成了存儲在數組中的隨機數字
 this.swap = swap;//交換數組中兩個元素的位置
 this.bubbleSort = bubbleSort;//冒泡排序算法
 this.selectionSort = selectionSort;//選擇排序算法
 this.insertionSort = insertionSort;//插入排序算法
 /*將傳入的數組，存儲在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;
 //外循環將數組元素挨個移動
 for (var outer = 1; outer <= this.dataStore.length-1; ++outer) {
 temp = this.dataStore[outer];//外循環選中的元素
 inner = outer;
 //內循環則對外循環中選中的元素與它前面的那個元素進行比較。
 //如果外循環中選中的元素比內循環中選中的元素小，那么數組元素會向右移動，為外循環中的這個元素騰出位置
 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());
 }
}
/*測試冒泡、選擇、插入算法的效率*/
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 + " 個元素耗時 : " + elapsed + " milliseconds.");
start = new Date().getTime();
nums.selectionSort();
stop = new Date().getTime();
elapsed = stop - start;
console.log("用選擇算法，排序 " + numElements + " 個元素耗時: " + elapsed + " milliseconds.");
start = new Date().getTime();
nums.insertionSort();
stop = new Date().getTime();
elapsed = stop - start;
console.log("用插入算法，排序 " + numElements + " 個元素耗時: " + elapsed + " milliseconds.");

運行結果：

選擇排序和插入排序要比冒泡排序快，插入排序是這三種算法中最快的。

感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運行工具：http://tools.jb51.net/code/HtmlJsRun測試上述代碼運行效果。

PS：這里再為大家推薦一款關于排序的演示工具供大家參考：

在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數學運算用法總結》、《JavaScript數據結構與算法技巧總結》、《JavaScript數組操作技巧總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》

希望本文所述對大家JavaScript程序設計有所幫助。

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com

JavaScript數據結構與算法之基本排序算法定義與效率比較【冒泡、選擇、插入排序】

推薦度：

點擊下載本文 文檔為doc格式

標簽：選擇冒泡排序

熱門焦點

JavaScript數據結構與算法之基本排序算法定義與效率比較【冒泡、選擇、插入排序】

JavaScript數據結構與算法之基本排序算法定義與效率比較【冒泡、選擇、插入排序】

JavaScript數據結構與算法之基本排序算法定義與效率比較【冒泡、選擇、插入排序】

最新推薦

猜你喜歡

熱門推薦