??本文主要內容：
- 各排序演算法時間復雜度
- js默認sort演算法于各瀏覽器中的實作
- 1.冒泡排序
- 2.選擇排序
- 3.插入排序
- 4.歸并排序（含小影片）
- 5.快速排序（含小影片）
時間復雜度
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2^n) < O(n!) < O(n^n)
js默認sort演算法于各瀏覽器中的實作
冒泡排序O(n^2)
冒泡排序比較任何兩個相鄰的項，如果第一個比第二個大，則交換它們，元素項向上移動至正確的順序，就好像氣泡升至表面一樣，冒泡排序因此得名，
function bubbleSort(array) {
let length = array.length
for (let i = 0; i < length; i++) { //控制了在陣列中經過多少輪排序
for (let j = 0; j < length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
let temp = array[j]
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
return array
}
選擇排序O(n^2)
選擇排序大致的思路是找到資料結構中的最小值并將其放置在第一位，接著找到第二小的值并將其放在第二位，以此類推，
function selectSort(array) {
let length = array.length
let indexMin //記錄每次最小值所在的位置
for (let i = 0; i < length; i++) {
indexMin = i
// 開始查找i以及i之后的最小值
for (let j = i; j < length; j++) {
if (array[indexMin] > array[j]) {
indexMin = j
}
}
if (i != indexMin) {
let temp = array[i]
array[i] = array[indexMin]
array[indexMin] = temp
}
}
return array
}
插入排序O(n^2)
插入排序每次排一個陣列項，以此方式構建最后的排序陣列，假定第一項已經排序了，接著，它和第二項進行比較，第二項是應該待在原位還是插到第一項之前呢？這樣，頭兩項就已正確排序，接著和第三項比較（它是該插入到第一、第二還是第三的位置呢？），以此類推，
function insertSort(array) {
let length = array.length
for (let i = 0; i < length; i++) {
j = i
temp = array[i]
while (j > 0 && array[j - 1] > temp) {
// 交換位置
array[j] = array[j - 1]
j--
}
array[j] = temp
}
return array
}
歸并排序O(nlogn)
歸并排序是第一個可以被實際使用的排序演算法，前三個排序演算法性能不好，但歸并排序性能不錯，其復雜度為O(nlogn)
歸并排序是一種分治演算法，其思想是將原始陣列切分成較小的陣列，直到每個小陣列只有一個位置，接著將小陣列歸并成較大的陣列，直到最后只有一個排序完畢的大陣列，點擊查看歸并排序小影片
// 創建
function Sort() {
this.mergeSort = function (array) {
return mergeSortRec(array);
};
var mergeSortRec = function (item) {
var length = item.length;
if (length === 1) { //遞回停止條件
return item;
}
var mid = Math.floor(length / 2), //將陣列分為左右兩部分
left = item.slice(0, mid),
right = item.slice(mid, length);
return merge(mergeSortRec(left), mergeSortRec(right));
};
// 負責合并和排序小陣列來產生大陣列
var merge = function (left, right) {
// console.log(left,right)
var result = [],
il = 0,
ir = 0;
//例子： [7,8],[5,6]
while (il < left.length && ir < right.length) {
if (left[il] < right[ir]) {
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
while (il < left.length) {
result.push(left[il++]);
}
while (ir < right.length) {
result.push(right[ir++]);
}
// console.log(result)
return result;
};
}
// 使用
let sort = new Sort()
console.log(sort.mergeSort([2,3,4,5,2,1]))
快速排序O(nlogn)
快速排序也許是最常用的排序演算法了，它的復雜度為O(nlogn)，且它的性能通常比其他的復雜度為O(nlogn)的排序演算法要好，和歸并排序一樣，快速排序也使用分治的方法，將原始陣列分為較小的陣列（但它沒有像歸并排序那樣將它們分割開），
(1) 首先，從陣列中選擇中間一項作為主元，
(2) 創建兩個指標，左邊一個指向陣列第一個項，右邊一個指向陣列最后一個項，移動左指標直到我們找到一個比主元大的元素，接著，移動右指標直到找到一個比主元小的元素，然后交換它們，重復這個程序，直到左指標超過了右指標，這個程序將使得比主元小的值都排在主元之前，比主元大的值都排在主元之后，這一步叫作劃分操作，
(3) 接著，演算法對劃分后的小陣列（較主元小的值組成的子陣列，以及較主元大的值組成的子陣列）重復之前的兩個步驟，直至陣列已完全排序，
圖示：點擊可看大圖，或者點擊查看快速排序小影片
// 創建
function Sort() {
this.quickSort = function (array) {
quick(array, 0, array.length - 1);
};
//宣告一個主方法來呼叫遞回函式，傳遞待排序陣列，以及索引0及其最末的位置（因為我們要排整個陣列，而不是一個子陣列）作為引數，
var quick = function (item, left, right) {
var index;
if (item.length > 1) {
index = partition(item, left, right); //index幫助將陣列分離為較小的和較大的陣列
if (left < index - 1) { //如果子陣列存在較小值的元素
quick(item, left, index - 1); //對該陣列重復該程序
}
if (index < right) { //同理
quick(item, index, right);
}
}
};
//劃分程序
var partition = function (item, left, right) {
var pivot = item[Math.floor((right + left) / 2)], //選擇主元（可隨機），這里選擇中間值
i = left,
j = right;
while (i <= j) { //只要左右指標沒有相互交錯，就執行劃分操作
while (item[i] < pivot) { //移動left指標直到找到一個元素比主元大
i++;
}
while (item[j] > pivot) { //移動right指標直到找到一個元素比主元小
j--;
}
if (i <= j) { //左右指標沒有相互交錯
swapQuickStort(item, i, j); //交換值
i++; //繼續往下走
j--;
}
}
return i; //此刻順序 比主元小 主元 比主元大，回傳分界指標到quick()相應陳述句中
};
var swapQuickStort = function (item, index1, index2) {
var aux = item[index1];
item[index1] = item[index2];
item[index2] = aux;
};
}
// 使用
let quickSort = new Sort()
let array = [4, 5, 1, 6, 2, 7, 3, 8]
quickSort.quickSort(array)
console.log(array)
推薦文章
Array.prototype.sort 各瀏覽器的演算法實作
維基百科 - 排序演算法（講解了各種排序演算法，超多超詳）
選擇排序小影片
冒泡排序小影片
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/39158.html
標籤：JavaScript
下一篇：34.冒泡排序