數(shù)據(jù)結構中的各種排序方法小結(JS實現(xiàn))
更新時間：2016年07月23日 10:16:04 投稿：jingxian
下面小編就為大家?guī)硪黄獢?shù)據(jù)結構中的各種排序方法小結(JS實現(xiàn))。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
新技術一直在不斷變化，掌握一些基礎是未來學習不斷更新的技術的堅實基礎。近來閑來無事,為了溫習一下從前學的數(shù)據(jù)結構，將數(shù)據(jù)結構中的排序算法用JS實現(xiàn)了一遍，并在本文末尾處嵌入了DEMO。
簡單排序
冒泡排序
冒泡排序是最簡單排序算法,時間復雜度為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;
}
}
/* 輸出結果 */
document.write("這是第 + (i + 1) + "次循環(huán)·，結果為:");
for (var k = 0; k < array.length; k++) {
document.write(array[k] + ",");
}
document.write("<br />");
/* 輸出結果結束 */
}
}
直接插入排序
直接插入排序也屬于簡單排序算法,時間復雜度也為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
/* 輸出結果 */
document.write("第? + i + "遍排序的結果是:")
for (var n = 0; n < array.length; n++) {
document.write(array[n] + ",");
}
document.write("<br />")
/* 輸出結果結束 */
}
}
選擇排序
選擇排序也屬于簡單排序算法，時間復雜度也為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;
}
/* 輸出結果 */
document.write("第 + i + "遍排序的結果是:")
for (var n = 0; n < array.length; n++) {
document.write(array[n] + ",");
}
document.write("<br />")
/* 輸出結果結束 */
}
}
復雜排序
希爾排序
希爾排序是插入排序的升級，1959年希爾通過將簡單排序中兩兩比較改為設置步長跳躍式比較而突破了n的平方的時間復雜度,希爾排序根據(jù)步長的不同時間復雜度由最好的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;
/* 輸出結果 */
count++;
document.write("<br />第 + count + "遍排序的結果是:")
for (var n = 0; n < array.length; n++) {
document.write(array[n] + ",");
}
/* 輸出結果結束 */
}
}
}
while (increment > 1)
}
堆排序
堆排序是選擇排序的升級，通過不斷構建大頂堆或者小頂堆來選擇最大或者最小的值放入隊列前端進行排序，堆排序任何情況下的時間復雜度都為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構建成一個大頂堆
}
for (i = array.length - 1; i >= 0; i--) {
/*把根節(jié)點交換出去*/
temp = array[i];
array[i] = array[0];
array[0] = temp;
/*余下的數(shù)組繼續(xù)構建成大頂堆*/
heapAdjust(array, 0, i - 1);
/* 輸出結果 */
document.write("<br />第 + (array.length - i).toString() + "遍排序的結果是:")
for (var n = 0; n < array.length; n++) {
document.write(array[n] + ",");
}
/* 輸出結果結束 */
}
}
//要調(diào)整的子樹
//start為數(shù)組開始下標
//max是數(shù)組結束下標
function heapAdjust(array, start, max) {
var temp, j;
temp = array[start];//temp是根節(jié)點的值
for (j = 2 * start; j < max; j *= 2) {
if (j < max && array[j] < array[j + 1]) { //取得較大孩子的下標
++j;
}
if (temp >= array[j])
break;
array[start] = array[j];
start = j;
}
array[start] = temp;
}
歸并排序
歸并排序是復雜排序中唯一一個穩(wěn)定排序，通過將待排序數(shù)組進行分拆再合并來進行排序，歸并排序時間復雜度為n的平方，代碼如下：
//source源數(shù)組 //dest目標數(shù)組
//s起始下標
//t目標下標
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);
/* 輸出結果 */
document.write("<br />第 + ++count + "遍排序的結果是:")
for (var n = 0; n < dest.length; n++) {
document.write(array[n] + ",");
}
/* 輸出結果結束 */
}
}
//將兩個數(shù)組按照從小到大的順序融合
//source原數(shù)組
//dest排序后的數(shù)組
//s第一個下標
//m第二個數(shù)組下標
//總長度
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];
}
}
}
快速排序
快速排序是目前已知的速度最快的排序，時間復雜度為nlogn,代碼如下：
var count = 0;
function quickSort(array, low, high) {
var temp;
if (low < high) {
var keypoint = QuickSortHelp(array, low, high);
count++;
document.write("<br />第臺? + count + "遍括?排?序ò的?結á果?是?:")
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ù)結構中的各種排序方法小結(JS實現(xiàn))就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關文章
SpringMVC返回json數(shù)據(jù)的三種方式
這篇文章主要介紹了SpringMVC返回json數(shù)據(jù)的三種方式的相關資料,需要的朋友可以參考下2015-12-12
js + css實現(xiàn)標簽內(nèi)容切換功能(實例講解)
下面小編就為大家?guī)硪黄猨s + css實現(xiàn)標簽內(nèi)容切換功能(實例講解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-10-10
這篇文章主要介紹了JCrop+ajaxUpload 圖像切割上傳的實例代碼的相關資料,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2016-07-07
這篇文章主要為大家詳細介紹了javascript實現(xiàn)掃雷簡易版，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-08-08
JavaScript實現(xiàn)構造json數(shù)組的方法分析
這篇文章主要介紹了JavaScript實現(xiàn)構造json數(shù)組的方法,結合實例形式對比分析了javascript構造json數(shù)組的實現(xiàn)方法及相關操作注意事項,需要的朋友可以參考下2018-08-08
這篇文章主要為大家詳細介紹了Javascript中的async函數(shù)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要介紹了js定義類的方法,結合實例形式分析了javascript ES5與ES6標準下類的定義方法,需要的朋友可以參考下2019-07-07
Bootstrap select實現(xiàn)下拉框多選效果
這篇文章主要為大家詳細介紹了Bootstrap select實現(xiàn)下拉框多選效果，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-12-12
這篇文章主要介紹了JavaScript通過事件代理高亮顯示表格行的方法,涉及javascript事件代理及頁面元素的操作技巧,需要的朋友可以參考下2015-05-05
這篇文章主要為大家詳細介紹了JS實現(xiàn)網(wǎng)頁時鐘特效，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03