摘要：本文簡單介紹幾個常見的排序算法答毫，包括：冒泡排序褥民、選擇排序、插入排序洗搂、快速排序消返、歸并排序、希爾排序耘拇。列出的代碼為 JavaScript 實現(xiàn)撵颊，標(biāo)題后表示的是該排序算法的時間復(fù)雜度。
冒泡排序 —— O(n^2)
function bubbleSort (array) {
for(let i = 0; i < array.length; i++){
for(let j = 1; j < array.length; j++){
if(array[i] > array[j]){
[array[i], array[j]] = [array[j], array[i]]
}
}
}
return array
}
選擇排序 —— O(n^2)
function selectionSort (array) {
let min = null
for(let i = 0; i < array.length; i++){
min = i
for(let j = i + 1; j < array.length; j++){
if(array[min] > array[j]){
min = j
}
}
[array[i],array[min]] = [array[min],array[i]]
}
return array
}
插入排序 —— O(n^2)
- 普通版
function insertionSort (array) {
let temp = null
for(let i = 1; i < array.length; i++){
temp = array[i]
for(var j = i; j >=0 && temp < array[j-1]; j--){
array[j] = array[j-1]
}
array[j] = temp
}
return array
}
- JS版( 使用
splice)
function insertionSort (array) {
for(let i = 1; i < array.length; i++){
for(var j = 0; j < i; j++){
if(array[i] < array[j]){
array.splice(j,0,array[i])
array.splice(i+1,1)
break
}
}
}
return array
}
快速排序 —— O(nlogn)
- 遞歸版（存在空間浪費）
function quickSort (array) {
if(array.length <= 1) {
return array
}
let leftArray = []
let rightArray = []
for(let i = 1; i < array.length; i++){
if(array[i] >= array[0]) {
rightArray.push(array[i])
} else {
leftArray.push(array[i])
}
}
return quickSort(leftArray).concat(array[0]).concat(quickSort(rightArray))
}
- 遞歸的進階版（在原數(shù)組上操作惫叛，最典型的快排寫法）
該方法大致流程如下：- 對于一個數(shù)組倡勇，挑選最后一個值作為參考值(key)
- 從數(shù)組的頭部開始掃描，如果值比參考值小挣棕，繼續(xù)往后掃描译隘，直到掃描到的值(左值)比參考值大
- 從數(shù)組的尾部(參考值的前一個)開始掃描亲桥，如果值比參考值大，繼續(xù)往前掃描固耘，直到掃描到的值(右值)比參考值小
- 此時交換掃描停止時的這兩個值
- 繼續(xù)上面的邏輯题篷，直到左值和右值相遇
- 如果相遇時的值大于等于參考值，讓參考值和相遇值調(diào)換位置(一般情況)
- 如果相遇時的值小于參考值厅目，不調(diào)換番枚，但 left 后移以為 (特殊情況，如 [2, 1, 3, 4, 5])
- 經(jīng)過上面的處理后损敷，就會把數(shù)組變成以原數(shù)組末尾數(shù)字為分割（左邊都比它小葫笼，右邊都比它大）的數(shù)組。然后分別對參考值左側(cè)和右側(cè)通過類似的邏輯繼續(xù)處理拗馒。
function quickSort(arr) {
function _quickSort(arr, start, end) {
if(start >= end) return
let key = arr[end]
let left = start, right = end - 1
while(left < right) {
while(arr[left] < key && left < right) left++
while(arr[right] >= key && left < right) right--
[arr[left], arr[right]] = [arr[right], arr[left]]
}
if(arr[left] >= arr[end]) {
[arr[left], arr[end]] = [arr[end], arr[left]]
} else { // 如 [2, 1, 3, 4]
left++
}
_quickSort(arr, start, left - 1)
_quickSort(arr, left + 1, end)
}
_quickSort(arr, 0, arr.length - 1)
return arr
}
歸并排序 —— O(nlogn)
- 大致流程：
- 申請空間路星，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
- 設(shè)定兩個指針诱桂，最初位置分別為兩個已經(jīng)排序序列的起始位置
- 比較兩個指針?biāo)赶虻脑匮筘ぃx擇相對小的元素放入到合并空間，并移動指針到下一位置
- 重復(fù)步驟3直到某一指針到達序列尾
- 將另一序列剩下的所有元素直接復(fù)制到合并序列尾
/*
left : [1, 3, 4, 7]
right: [2, 5, 6, 9]
result: [1, 2, 3, 4, 5, 6, 7, 9]
*/
function mergeSort(arr) {
var merge = function(left, right) {
var result = []
while(left.length && right.length) {
result.push(left[0] <= right[0] ? left.shift() : right.shift())
}
return result.concat(left.concat(right))
}
if(arr.length < 2) return arr
var mid = arr.length >> 1
return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}
希爾排序 —— O(nlog2n)
原理：先將整個待排數(shù)組分割成若干個子數(shù)組（由相隔某個“增量”的元素組成的）分別進行直接插入排序挥等，然后依次縮減增量再進行排序友绝，待整個數(shù)組中的元素基本有序（增量足夠小）時肝劲，再對全體元素進行一次直接插入排序迁客。因為直接插入排序在元素基本有序的情況下效率是很高的，因此希爾排序在時間效率上較大提高辞槐。
function shellSort(arr) {
var temp
var len = arr.length
for (var gap = len >> 1; gap > 0; gap = gap >>=1) {
for (var i = gap; i < len; i++) {
temp = arr[i]
for( j = i - gap; j >=0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j]
}
arr[j + gap] = temp
}
console.log(arr)
}
}
var arr = [3, 1, 7, 2, 5, 0, 4, 6]
shellSort(arr)
console.log(arr)
