新技術(shù)一直在不斷變化，掌握一些基礎(chǔ)是未來(lái)學(xué)習(xí)不斷更新的技術(shù)的堅(jiān)實(shí)基礎(chǔ)。近來(lái)閑來(lái)無(wú)事,為了溫習(xí)一下從前學(xué)的數(shù)據(jù)結(jié)構(gòu)，將數(shù)據(jù)結(jié)構(gòu)中的排序算法用JS實(shí)現(xiàn)了一遍，并在本文末尾處嵌入了DEMO。
簡(jiǎn)單排序
冒泡排序
冒泡排序是最簡(jiǎn)單排序算法,時(shí)間復(fù)雜度為n的平方,代碼如下:
function bubbleSort(array) { for (var i = 0; i < array.length; i++) { for (var j = array.length; j > 0; j--) { if (array[j] < array[j - 1]) { var temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; } } /* 輸出結(jié)果 */ document.write("這是第 + (i + 1) + "次循環(huán)?，結(jié)果為:"); for (var k = 0; k < array.length; k++) { document.write(array[k] + ","); } document.write("<br />"); /* 輸出結(jié)果結(jié)束 */ } }直接插入排序
直接插入排序也屬于簡(jiǎn)單排序算法,時(shí)間復(fù)雜度也為n的平方，但性能略好于冒泡排序，代碼如下:
function insertSort(array) { var temp; for (var i = 1; i < array.length; i++) { var temp = array[i]; for (var j = i; j > 0 && temp < array[j - 1]; j--) { array[j] = array[j - 1]; } array[j] = temp /* 輸出結(jié)果 */ document.write("第? + i + "遍排序的結(jié)果是:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } document.write("<br />") /* 輸出結(jié)果結(jié)束 */ } }選擇排序
選擇排序也屬于簡(jiǎn)單排序算法，時(shí)間復(fù)雜度也為n的平方，性能同樣略微好于冒泡排序，代碼如下:
function selectSort(array) { var min, temp; ; for (var i = 0; i < array.length; i++) { min = i; for (var j = i + 1; j < array.length; j++) { if (array[min] > array[j]) min = j; } if (min != i) { temp = array[i]; array[i] = array[min]; array[min] = temp; } /* 輸出結(jié)果 */ document.write("第 + i + "遍排序的結(jié)果是:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } document.write("<br />") /* 輸出結(jié)果結(jié)束 */ } }復(fù)雜排序
希爾排序
希爾排序是插入排序的升級(jí)，1959年希爾通過(guò)將簡(jiǎn)單排序中兩兩比較改為設(shè)置步長(zhǎng)跳躍式比較而突破了n的平方的時(shí)間復(fù)雜度,希爾排序根據(jù)步長(zhǎng)的不同時(shí)間復(fù)雜度由最好的nlogn到最壞的n的平方。代碼如下:
function shallSort(array) { var increment = array.length; var i var temp; //暫存 var count = 0; do { increment = Math.floor(increment / 3) + 1; for (i = increment; i < array.length; i++) { if (array[i] < array[i - increment]) { temp = array[i]; for (var j = i - increment; j > 0 && temp < array[j]; j -= increment) { array[j + increment] = array[j]; } array[j + increment] = temp; /* 輸出結(jié)果 */ count++; document.write("<br />第 + count + "遍排序的結(jié)果是:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } /* 輸出結(jié)果結(jié)束 */ } } } while (increment > 1) }堆排序
堆排序是選擇排序的升級(jí)，通過(guò)不斷構(gòu)建大頂堆或者小頂堆來(lái)選擇最大或者最小的值放入隊(duì)列前端進(jìn)行排序，堆排序任何情況下的時(shí)間復(fù)雜度都為nlogn，代碼如下：
function heapSort(array) { var temp; var i; for (i = Math.floor(array.length / 2); i >= 0; i--) { heapAdjust(array, i, array.length - 1); //將數(shù)組array構(gòu)建成一個(gè)大頂堆 } for (i = array.length - 1; i >= 0; i--) { /*把根節(jié)點(diǎn)交換出去*/ temp = array[i]; array[i] = array[0]; array[0] = temp; /*余下的數(shù)組繼續(xù)構(gòu)建成大頂堆*/ heapAdjust(array, 0, i - 1); /* 輸出結(jié)果 */ document.write("<br />第 + (array.length - i).toString() + "遍排序的結(jié)果是:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } /* 輸出結(jié)果結(jié)束 */ } } //要調(diào)整的子樹 //start為數(shù)組開始下標(biāo) //max是數(shù)組結(jié)束下標(biāo) function heapAdjust(array, start, max) { var temp, j; temp = array[start];//temp是根節(jié)點(diǎn)的值 for (j = 2 * start; j < max; j *= 2) { if (j < max && array[j] < array[j + 1]) { //取得較大孩子的下標(biāo) ++j; } if (temp >= array[j]) break; array[start] = array[j]; start = j; } array[start] = temp; }歸并排序
歸并排序是復(fù)雜排序中唯一一個(gè)穩(wěn)定排序，通過(guò)將待排序數(shù)組進(jìn)行分拆再合并來(lái)進(jìn)行排序，歸并排序時(shí)間復(fù)雜度為n的平方，代碼如下：
//source源數(shù)組 //dest目標(biāo)數(shù)組 //s起始下標(biāo) //t目標(biāo)下標(biāo) function mSort(source, dest, s, t) { var m; //取中間值 var dest2 = new Array(); if (s == t) { dest[s] = source[s]; } else { m = Math.floor((s + t) / 2); mSort(source, dest2, s, m); mSort(source, dest2, m+1 , t); merge(dest2, dest, s, m, t); /* 輸出結(jié)果 */ document.write("<br />第 + ++count + "遍排序的結(jié)果是:") for (var n = 0; n < dest.length; n++) { document.write(array[n] + ","); } /* 輸出結(jié)果結(jié)束 */ } } //將兩個(gè)數(shù)組按照從小到大的順序融合 //source原數(shù)組 //dest排序后的數(shù)組 //s第一個(gè)下標(biāo) //m第二個(gè)數(shù)組下標(biāo) //總長(zhǎng)度 function merge(source, dest, s, m, n) { for (var j = m+1, k = s; j <= n && s <= m; k++) { if (source[s] < source[j]) { dest[k] = source[s++]; } else { dest[k] = source[j++]; } } //將剩余排不完的有序數(shù)組加入到dest的末端 if (s <= m) { for (var l = 0; l <= m - s; l++) { dest[k + l] = source[s+l]; } } if (j <= n) { for (var l = 0; l <= n - j; l++) { dest[k + l] = source[j+l]; } } }快速排序
快速排序是目前已知的速度最快的排序，時(shí)間復(fù)雜度為nlogn,代碼如下：
var count = 0; function quickSort(array, low, high) { var temp; if (low < high) { var keypoint = QuickSortHelp(array, low, high); count++; document.write("<br />第臺(tái)? + count + "遍括?排?序ò的?結(jié)á果?是?:") for (var l = 0; l < array.length; l++) { document.write(array[l] + ","); } quickSort(array, low, keypoint - 1); quickSort(array, keypoint + 1, high); } } function QuickSortHelp(array, low, high) { while (low < high) { while (low < high && array[low] <= array[high]) { high--; } temp = array[low]; array[low] = array[high]; array[high] = temp; while (low < high && array[low] <= array[high]) { low++ } temp = array[low]; array[low] = array[high]; array[high] = temp; } return low; }以上這篇數(shù)據(jù)結(jié)構(gòu)中的各種排序方法小結(jié)(JS實(shí)現(xiàn))就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持武林網(wǎng)。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
