JS排序演算法之快排和歸并
目錄- JS排序演算法之快排和歸并
- 快速排序
- 歸并排序
快速排序
原理: 選擇一個key(一般是第一個元素), 將陣列劃分為兩個區域. 左邊全部區域小于等于key, 右邊全部大于key. 然后在通過這種方法將每個區域劃分為兩個區域. 整個程序可以遞回實作,以此實作整個資料有序
- 時間復雜度: O(n*log(n))
- 最壞時間復雜度: O(n^2)
- 最壞情況: 原陣列是升序(降序), 需要排成降序(升序)
- 不穩定的排序
- 特性: 陣列分塊,且左邊區域小于右邊(升序)
- 不穩定原因: 元素交換是跨元素直接交換, 相鄰相同元素可能發生位置交換
- 性能: 最好的的快速排序方法
示例程序:
function quickSort(ary) {
let n = ary.length;
function sort(ary, start, end) {
if(end <= start) return;
let i = start,
j = end,
key = ary[start]; // 設定第一個元素為key
while(true) {
// 從左向右找到大于key的元素位置(大于key回圈停止, i就是該元素位置)
while(ary[++i] < key) {
// 到達末尾退出回圈
if(i === end) break;
}
// 從右向左找到小于key的元素位置
while(ary[--j] > key) {
// 到達頭部退出回圈
if(j === start) break;
}
// 如果 i和j相交, 直接退出回圈
if(i>=j) break;
// 交換左右兩邊元素
let temp = ary[i];
ary[i] = ary[j];
ary[j] = temp;
}
// 交換key和最后一個小于key值的元素(就是arr[j])
let temp = ary[start];
ary[start] = ary[j];
ary[j] = temp;
sort(ary, start, j);
sort(ary, j+1, end);
}
sort(ary, 0, n);
return ary;
}
效果演示:
歸并排序
原理: 先將陣列不斷折分為左右兩個小陣列, 然后再對小陣列排序并合并起來
- 時間復雜度: O(n*log(n))
- 穩定的排序演算法
- 穩定原因: 排序是兩兩元素值之間的互換, 相鄰相同元素位置不會被改變
- 性能: 速度僅次與快排(如果使用遞回方法,在處理龐大資料時可能出現記憶體不足情況), 比快排穩定,任何時候時間復雜度都是O(n*long(n));
- 特點: 陣列會不斷對半平分, 然后再排序合并. 先小區間有序,再大區間, 區間間隔相等.
- 優化: TimeSort排序
示例程序:
function mergeSort(items) {
if (items.length == 1) {
return items;
}
//將陣列對半平分為左右兩個陣列
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle);
function merge(left, right) {
var result = [];
// 通過這個回圈來排序
while (left.length > 0 && right.length > 0) {
if (left[0] < right[0]) {
/*shift()方法用于把陣列的第一個元素從其中洗掉，并回傳第一個元素的值，*/
result.push(left.shift());
} else {
result.push(right.shift());
}
}
//合并兩個陣列
return result.concat(left).concat(right);
}
// 遞回呼叫
return merge(mergeSort(left), mergeSort(right));
}
效果示例
gif來源: 排序演算法-散點可視化
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/140908.html
標籤：JavaScript
上一篇：JS實作滾動區域觸底事件
下一篇：JS--排序演算法之堆排序