希爾排序原理：
1.選定一個(gè)增長(zhǎng)量h，按照增長(zhǎng)量h作為數(shù)據(jù)分組的依據(jù)赂苗，對(duì)數(shù)據(jù)進(jìn)行分組愉耙。
2.對(duì)分好的每一組進(jìn)行插入排序。
3.減小增長(zhǎng)量拌滋，最小減為1朴沿，重復(fù)2操作。
//希爾排序：O(log(n))
let arr = [4, 3, 2, 1, 6, 5, 7, 9, 8, 5]
//1.首先根據(jù)數(shù)組的長(zhǎng)度，確定增長(zhǎng)量h的值
let h = 1
while (h < arr.length / 2) {
h = 2 * h + 1
}
//2.開始排序
while (h >= 1) {
for (let i = h; i < arr.length; i++) {
for (let j = i; j >= h; j -= h) {
if (arr[j] > arr[j - h]) {
let temp = arr[j]
arr[j] = arr[j - h]
arr[j - h] = temp
} else {
break
}
}
}
//取整
h = parseInt(h / 2)
}
歸并排序原理：
1.盡可能的一組數(shù)據(jù)拆分成兩個(gè)元素相等的子組赌渣，并對(duì)每一個(gè)子組繼續(xù)拆分魏铅，直到拆分后的每個(gè)子組的元素個(gè)數(shù)是1為止。
2.將相鄰的兩個(gè)子組進(jìn)行合并成一個(gè)有序的大組坚芜。
3.不斷的重復(fù)步驟2览芳，直到最終只有一個(gè)組為止。
//歸并排序：O(nlogn)
//輔助數(shù)組
let assist = null
function sort(arr) {
//初始化輔助數(shù)組
assist = new Array(arr.length)
//定義一個(gè)lo變量和hi變量鸿竖，分別記錄數(shù)組中最小索引和最大索引
let lo = 0
let hi = arr.length - 1
sortGroup(arr, lo, hi)
document.getElementById("div1").innerText = arr
}
//分組排序
function sortGroup(arr, lo, hi) {
if (lo >= hi) {
return
}
//拆分
//對(duì)lo和hi之間的數(shù)組分為兩組
let mid = parseInt(lo + (hi - lo) / 2)
sortGroup(arr, lo, mid)
sortGroup(arr, mid + 1, hi)
console.log("lo:"+lo+"||"+"mid:"+mid+"||"+"hi:"+hi);
//再把兩個(gè)組中的數(shù)據(jù)進(jìn)行歸并
merge(arr, lo, mid, hi)
}
//歸并
function merge(arr, lo, mid, hi) {
//定義三個(gè)指針
let i = lo
let p1 = lo
let p2 = mid + 1
//遍歷沧竟，移動(dòng)p1,p2指針，比較對(duì)應(yīng)索引處的值缚忧，找出小的那個(gè)悟泵，放到輔助數(shù)組對(duì)應(yīng)的索引處
while (p1 <= mid && p2 <= hi) {
if (arr[p1] < arr[p2]) {
assist[i++] = arr[p1++]
} else {
assist[i++] = arr[p2++]
}
}
//遍歷走完p1還沒(méi)走完的索引
while (p1 <= mid) {
assist[i++] = arr[p1++]
}
//遍歷走完p2還沒(méi)走完的索引
while (p2 <= hi) {
assist[i++] = arr[p2++]
}
//將輔助數(shù)組中的數(shù)據(jù)拷貝到原數(shù)組
for (let index = lo; index <= hi; index++) {
arr[index] = assist[index]
}
}
//待排序數(shù)組
let arr = [8, 4, 5, 7, 1, 3, 6, 2]
//調(diào)用排序方法
sort(arr)
快速排序原理：
1.首先設(shè)定一個(gè)分界值，通過(guò)該分界值將數(shù)組分成左右兩部分闪水。
2.將大于或等于分界值的數(shù)據(jù)放到到數(shù)組右邊糕非，小于分界值的數(shù)據(jù)放到數(shù)組的左邊。此時(shí)左邊部分中各元素都小于
或等于分界值敦第，而右邊部分中各元素都大于或等于分界值峰弹。
3.然后，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序芜果。對(duì)于左側(cè)的數(shù)組數(shù)據(jù)鞠呈，又可以取一個(gè)分界值，將該部分?jǐn)?shù)據(jù)分成左右兩
部分右钾，同樣在左邊放置較小值蚁吝，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理舀射。
4.重復(fù)上述過(guò)程窘茁，可以看出，這是一個(gè)遞歸定義脆烟。通過(guò)遞歸將左側(cè)部分排好序后山林，再遞歸排好右側(cè)部分的順序。當(dāng)
左側(cè)和右側(cè)兩個(gè)部分的數(shù)據(jù)排完序后邢羔，整個(gè)數(shù)組的排序也就完成了驼抹。
//快速排序
function sort(arr) {
//初始化輔助數(shù)組
assist = new Array(arr.length)
//定義一個(gè)lo變量和hi變量，分別記錄數(shù)組中最小索引和最大索引
let lo = 0
let hi = arr.length - 1
sortGroup(arr, lo, hi)
document.getElementById("div1").innerText = arr
}
function sortGroup(arr, lo, hi) {
if (hi <= lo) {
return
}
//需要對(duì)數(shù)組中l(wèi)o索引到hi索引處的元素進(jìn)行分組
let partition = partition(arr, lo, hi)
//讓左子樹有序
sortGroup(arr, lo, partition - 1)
//讓右子樹有序
sortGroup(arr, partition + 1, hi)
}
//對(duì)數(shù)組a中拜鹤，從索引lo到索引hi之間的元素進(jìn)行分組框冀，并返回分組界限對(duì)應(yīng)的索引
function partition(arr, lo, hi) {
//確定分界值
let key = a[lo]
//定義兩個(gè)指針，分別指向帶切分元素的最小索引處和最大索引處的下一個(gè)位置
let right = hi + 1
let left = lo
//切分
while (true) {
//先從右往左掃描敏簿，移動(dòng)right指針明也，找到一個(gè)比分界值小的元素宣虾，停止
while (key < a[--right]) {
if (right == lo) {
break
}
}
//在從左往右掃描，移動(dòng)left指針温数，找到一個(gè)比分界值大的元素绣硝，停止
while (a[++left] < key) {
if (left == hi) {
break
}
}
//判斷 left >=right，如果是帆吻，掃描完畢域那，否，交換元素
if (left >= right) {
break
} else {
let temp = arr[left]
arr[left] = arr[right]
arr[right] = temp
}
}
let temp = arr[right]
arr[right] = arr[lo]
arr[lo] = temp
return right
}
注：以上均由JS代碼編寫猜煮。
