作者：神奇的程序員K
轉(zhuǎn)發(fā)鏈接：https://mp.weixin.qq.com/s/3B8dZRfbIuktSBeArXlmcQ
前言
我們?cè)陧?yè)面上渲染數(shù)據(jù)時(shí)，通常會(huì)根據(jù)特定規(guī)則來(lái)對(duì)數(shù)據(jù)進(jìn)行一個(gè)排序，然后再將其渲染到頁(yè)面展示給用戶。哪么對(duì)數(shù)據(jù)進(jìn)行排序有很多種方式，哪一種效率高？哪一種穩(wěn)定性好？那一種占用內(nèi)存小？本文將詳解經(jīng)典的八大排序算法以及三種搜索算法，并用TypeScript將其實(shí)現(xiàn)，歡迎各位對(duì)上述問(wèn)題迷惑的開(kāi)發(fā)者閱讀本文。
排序算法
我們先來(lái)學(xué)習(xí)下排序算法，八大排序包括：冒泡排序、選擇排序、插入排序、歸并排序、快速排序、計(jì)數(shù)排序、同排序、基數(shù)排序其中有幾個(gè)排序我在之前的文章中已經(jīng)講解了其圖解實(shí)現(xiàn)，本文將注重講解其實(shí)現(xiàn)，另外幾篇文章鏈接如下:
- 排序算法:冒泡排序
- 排序算法:選擇排序
- 排序算法:插入排序
- 排序算法:歸并排序
- 排序算法:快速排序
冒泡排序
冒泡排序是排序算法中最簡(jiǎn)單、最好理解的一個(gè)排序算法，但是從運(yùn)行時(shí)間的角度來(lái)看，它的效率是最低的。本文中所有函數(shù)實(shí)現(xiàn)的代碼地址: Sort.ts
實(shí)現(xiàn)思路
它會(huì)比較相鄰的兩個(gè)項(xiàng)，如果第一個(gè)比第二個(gè)大，則交換它們。元素項(xiàng)向上移動(dòng)至正確的順序。為了讓排序算法更靈活，不僅僅只是用于數(shù)字的排序，因此本文中講解的排序算法都會(huì)有一個(gè)比對(duì)函數(shù)作為參數(shù)傳進(jìn)來(lái)，用于定義兩個(gè)值的比較方式。
- 聲明一個(gè)函數(shù)其接受兩個(gè)參數(shù)：待排序數(shù)組 & 比對(duì)函數(shù)
- 第一層循環(huán)i：從待排序數(shù)組的0號(hào)元素開(kāi)始遍歷數(shù)組，遍歷到最后一位，用于控制數(shù)組需要經(jīng)過(guò)多少輪排序
- 第二層循環(huán)j：從數(shù)組的0號(hào)元素開(kāi)始遍歷，遍歷至數(shù)組的倒數(shù)第二位元素再減去第一層循環(huán)i。
- 比較大小，在第二層循環(huán)中，將當(dāng)前遍歷到的元素和其下一個(gè)元素比較大小，如果 j > j + 1就交換兩個(gè)元素的位置。
我們通過(guò)一個(gè)例子來(lái)描述下上述思路，如下圖所示，將一個(gè)亂序數(shù)組執(zhí)行冒泡排序后，將其從小到大排列。
實(shí)現(xiàn)代碼
為了讓函數(shù)便于維護(hù)，我們新建一個(gè)類(lèi)名為Sort，本文中實(shí)現(xiàn)的所有函數(shù)都為這個(gè)類(lèi)內(nèi)部的方法。
- 為了函數(shù)的可擴(kuò)展性，我們需要實(shí)現(xiàn)一個(gè)默認(rèn)的比對(duì)函數(shù)，此比對(duì)函數(shù)作用于本文中的所有排序方法
export function defaultCompare<T>(a: T, b: T): number {
if (a === b) {
return Compare.EQUALS;
} else if (a > b) {
return Compare.BIGGER_THAN;
} else {
return Compare.LESS_THAN;
}
}
// 枚舉類(lèi)：定義比對(duì)返回值
export enum Compare {
LESS_THAN = -1,
BIGGER_THAN = 1,
EQUALS = 0
}
- 在類(lèi)中聲明需要的變量，并在構(gòu)造器中聲明需要傳的參數(shù)類(lèi)型，此處適用于本文實(shí)現(xiàn)的所有函數(shù)
/**
* 排序算法
* @param array 需要進(jìn)行排序的數(shù)組
* @param compareFn 比對(duì)函數(shù)
*/
constructor(private array: T[] = [], private compareFn: ICompareFunction<T> = defaultCompare) {}
- 實(shí)現(xiàn)冒泡排序
// 冒泡排序
bubbleSort(): void {
// 獲取數(shù)組長(zhǎng)度
const { length } = this.array;
for (let i = 0; i < length; i++) {
// 從數(shù)組的0號(hào)元素遍歷到數(shù)組的倒數(shù)第2號(hào)元素，然后減去外層已經(jīng)遍歷的輪數(shù)
for (let j = 0; j < length - 1 - i; j++) {
// 如果j > j + 1位置的元素就交換他們兩個(gè)元素的位置
if (this.compareFn(this.array[j], this.array[j + 1]) === Compare.BIGGER_THAN) {
this.swap(this.array, j, j + 1);
}
}
}
}
編寫(xiě)測(cè)試代碼
我們將上圖中的例子放在代碼中，測(cè)試下執(zhí)行結(jié)果是否正確。
const array = [12, 6, 3, 4, 1, 7];
const sort = new Sort(array);
sort.bubbleSort();
console.log(array.join());
選擇排序
選擇排序是一種原址比較排序算法，它的大致思路是找到數(shù)據(jù)結(jié)構(gòu)中的最小值并將其放置在第一位，接著找到第二小的值將其放在第二位，依次類(lèi)推。
實(shí)現(xiàn)思路
- 聲明一個(gè)輔助變量:indexMin用于存儲(chǔ)數(shù)組中的最小值
- 第一層循環(huán)i，從數(shù)組的0號(hào)元素遍歷到數(shù)組的倒數(shù)第二位。indexMin默認(rèn)賦值為i，用于控制輪數(shù)
- 第二層循環(huán)j，從數(shù)組的i號(hào)元素遍歷到數(shù)組的末尾，用于尋找數(shù)組的最小值，如果indexMin位置的元素大于j號(hào)位置的元素就覆蓋indxMin的值為j
- 在第二層循環(huán)結(jié)束后，比較i與indexMin是否相等，如果不相等就交換兩個(gè)元素的位置。
下圖中的示例描述了上述思路
實(shí)現(xiàn)代碼
// 選擇排序
selectionSort(): void {
const { length } = this.array;
// 聲明一個(gè)變量用于存儲(chǔ)最小元素的位置
let indexMin = 0;
for (let i = 0; i < length; i++) {
// 初始值為外層循環(huán)當(dāng)前遍歷到的位置i
indexMin = i;
for (let j = i; j < length; j++) {
// 如果當(dāng)前遍歷到元素小于indexMin位置的元素，就將當(dāng)前遍歷到的位置j賦值給indexMin
if (this.compareFn(this.array[indexMin], this.array[j]) === Compare.BIGGER_THAN) {
indexMin = j;
}
}
if (i !== indexMin) {
this.swap(this.array, i, indexMin);
}
}
}
編寫(xiě)測(cè)試代碼
我們將圖中的示例，放在代碼中，測(cè)試排序函數(shù)是否都正確執(zhí)行。
const array = [12, 6, 3, 4, 1, 7];
const sort = new Sort(array);
// const result = sort.radixSort(array);
// console.log(result.join());
sort.selectionSort();
console.log(array.join());
插入排序
插入排序會(huì)將數(shù)組分為已排序區(qū)域和未排序區(qū)域，將未排序區(qū)域的數(shù)組項(xiàng)和已排序區(qū)域的數(shù)組進(jìn)行大小比較，確立要插入的位置，然后將其插入到對(duì)應(yīng)的位置。
實(shí)現(xiàn)思路
- 第一層循環(huán)i：從數(shù)組的1號(hào)元素開(kāi)始，遍歷到數(shù)組末尾，因?yàn)槲覀儠?huì)先假設(shè)0號(hào)元素已經(jīng)排好序，所以從1號(hào)元素開(kāi)始。
- 用一個(gè)臨時(shí)變量temp存儲(chǔ)當(dāng)前i號(hào)位置的元素，用一個(gè)變量j存儲(chǔ)i
- while循環(huán): j > 0且j - 1位置的元素大于temp，就把j位置的值設(shè)置為j - 1 位置的值，最后j--，繼續(xù)下一輪遍歷。
- while循環(huán)結(jié)束后，將temp放到正確的位置array[ j ]
如下圖所示，我們通過(guò)一個(gè)例子描述了上述插入排序的過(guò)程
實(shí)現(xiàn)代碼
接下來(lái)我們將上述思路轉(zhuǎn)換為代碼。
// 插入排序
insertionSort(array: T[] = this.array): void {
const { length } = array;
let temp;
// 假設(shè)0號(hào)元素已經(jīng)排好序，從1號(hào)元素開(kāi)始遍歷數(shù)組
for (let i = 1; i < length; i++) {
// 聲明輔助變量存儲(chǔ)當(dāng)前i的位置以及其對(duì)應(yīng)的值
let j = i;
temp = array[i];
// j大于0且j-1位置的元素大于i號(hào)位置的元素就把j-1處的值移動(dòng)到j(luò)處，最后j--
while (j > 0 && this.compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) {
array[j] = array[j - 1];
j--;
}
// 將temp放到正確的位置
array[j] = temp;
}
}
編寫(xiě)測(cè)試代碼
我們將圖中的例子放在代碼里，執(zhí)行下查看排序函數(shù)是否正常運(yùn)行。
const array = [12, 6, 3, 4, 1, 7];
const sort = new Sort(array);
sort.insertionSort(array);
console.log(array.join());
歸并排序
歸并排序是一個(gè)可以實(shí)際使用的排序算法，在JAVAScript中Array類(lèi)定義了一個(gè)Sort函數(shù)，用以排序JavaScript數(shù)組。ECMScript沒(méi)有定義用哪個(gè)排序算法，所以瀏覽器廠商可以自己去實(shí)現(xiàn)算法。谷歌瀏覽器的V8引擎使用快速排序?qū)崿F(xiàn)，火狐瀏覽器使用歸并排序?qū)崿F(xiàn)。
實(shí)現(xiàn)思路
歸并排序是一個(gè)分而治之算法，就是將原始數(shù)組切分成比較小的數(shù)組，直到每個(gè)小數(shù)組只有一個(gè)位置，接著將小數(shù)組歸并成比較大的數(shù)組，直到最后只有一個(gè)排序完畢的大數(shù)組。由于是分治法，歸并排序也是遞歸的。我們要將算法分為兩個(gè)函數(shù)：一個(gè)用于將函數(shù)分割成小數(shù)組，一個(gè)用于將小數(shù)組合并成大數(shù)組。我們先來(lái)看看主函數(shù)，將數(shù)組分割成小數(shù)組。
- 遞歸終止條件：由于是遞歸，所以我們需要先設(shè)立遞歸終止條件，當(dāng)數(shù)組的長(zhǎng)度大于1時(shí)就進(jìn)行歸并排序。
- 獲取數(shù)組的中間值: 我們通過(guò)數(shù)組的中間值來(lái)切割數(shù)組，將其分成左、右兩部分。對(duì)左右兩部分繼續(xù)執(zhí)行分割
- 合并數(shù)組: 我們將數(shù)組分割完后，對(duì)小數(shù)組進(jìn)行排序，然后將其合并成大數(shù)組并返回。
接下來(lái)，我們?cè)賮?lái)看下合并函數(shù)的實(shí)現(xiàn)
- 合并函數(shù)接收兩個(gè)參數(shù)：左、右數(shù)組
- 聲明三個(gè)輔助變量: i, j, result，分別表示左、右數(shù)組的指針以及存儲(chǔ)合并后的數(shù)組
- 如果i < left.length && j < right.length，代表指針數(shù)組尚未排序完，因此執(zhí)行下述邏輯
- 如果lef[i] < right[j]，就往result中放left[i]的值隨后i++，否則就放right[j]的值隨后j++
- 最后，將left或right數(shù)組的剩余項(xiàng)添加進(jìn)result中
下圖用一個(gè)例子描述了上述歸并排序的過(guò)程
實(shí)現(xiàn)代碼
接下來(lái)，我們將上述思路轉(zhuǎn)換為代碼。
// 歸并排序
mergeSort(array: T[] = this.array): T[] {
if (array.length > 1) {
const { length } = array;
// 獲取中間值
const middle = Math.floor(length / 2);
// 遞歸填充左右數(shù)組
const left = this.mergeSort(array.slice(0, middle));
const right = this.mergeSort(array.slice(middle, length));
// 合并左右數(shù)組
array = this.merge(left, right);
}
return array;
}
private merge(left: T[], right: T[]) {
let i = 0;
let j = 0;
const result: T[] = [];
while (i < left.length && j < right.length) {
// 如果left[i] < right[j]將left[i]加進(jìn)result中，隨后i自增，否則把right[j]加進(jìn)result中，隨后j自增
result.push(this.compareFn(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);
}
// 將left或right數(shù)組的剩余項(xiàng)添加進(jìn)result中
return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}
編寫(xiě)測(cè)試代碼
我們將上圖中的例子放到代碼中執(zhí)行用以驗(yàn)證我們的函數(shù)是否正確執(zhí)行
const array = [12, 6, 3, 4, 1, 7];
const sort = new Sort(array);
const result = sort.mergeSort();
console.log(result.join());
快速排序
快速排序與歸并排序一樣都是可用作實(shí)際應(yīng)用的算法，它也是使用分而治之的方法，將原始數(shù)組分為較小的數(shù)組，但它沒(méi)有像歸并排序那樣將他們分割開(kāi)。
實(shí)現(xiàn)思路
我們需要三個(gè)函數(shù)：主函數(shù)、排序函數(shù)、切分函數(shù)。
- 主函數(shù)（quickSort），調(diào)用排序函數(shù)，返回排序函數(shù)最終排好的數(shù)組。
- 排序函數(shù)（quick），接收3個(gè)參數(shù): 待排序數(shù)組（array）、數(shù)組的左邊界（left）、數(shù)組的右邊界（right）
- 聲明一個(gè)輔助變量index，用于存儲(chǔ)分割子數(shù)組的的位置。
- 確立遞歸終止條件：array < 1 ，如果array.length > 1，就執(zhí)行下述操作：
執(zhí)行劃分函數(shù)，計(jì)算劃分點(diǎn)，將得到的值賦值給index；
如果left > index - 1，代表子數(shù)組中存在較小值的元素，從數(shù)組的left邊界到index-1邊界遞歸執(zhí)行排序函數(shù)；
如果index < right，代表子數(shù)組存在較大值的元素，從數(shù)組的index到right邊界遞歸執(zhí)行排序函數(shù)；
- 劃分函數(shù)（partition），與排序函數(shù)一樣，它也接收3個(gè)參數(shù)。
- 從數(shù)組中選擇一個(gè)主元pivot，選擇數(shù)組的中間值
- 聲明兩個(gè)指針：i, j，分別指向左邊數(shù)組的第一個(gè)值和右邊數(shù)組的第一個(gè)值。
- 如果i <= j，則代表left指針和right指針沒(méi)有相互交錯(cuò)，則執(zhí)行下述劃分操作：
移動(dòng)left指針直至找到一個(gè)比主元大的元素，即array[i] > pivot；
移動(dòng)right指針直至找到一個(gè)比主元小的元素，即array[j] < pivot；
當(dāng)左指針指向的元素比主元大且右指針指向的元素比主元小，并且左指針?biāo)饕龥](méi)有右指針?biāo)饕髸r(shí)就交換i號(hào)和j號(hào)元素的位置，隨后移動(dòng)兩個(gè)指針；
最后，劃分結(jié)束，返回i的值；
實(shí)現(xiàn)代碼
接下來(lái)我們將上述思路轉(zhuǎn)換為代碼:
/**
*
* @param array 待排序數(shù)組
* @param left 左邊界
* @param right 右邊界
* @private
*/
private quick(array: T[], left: number, right: number) {
// 該變量用于將子數(shù)組分離為較小值數(shù)組和較大值數(shù)組
let index;
if (array.length > 1) {
// 對(duì)給定子數(shù)組執(zhí)行劃分操作，得到正確的index
index = this.partition(array, left, right);
// 如果子數(shù)組存在較小值的元素，則對(duì)該數(shù)組重復(fù)這個(gè)過(guò)程
if (left < index - 1) {
this.quick(array, left, index - 1);
}
// 如果子數(shù)組存在較大值的元素，也對(duì)該數(shù)組重復(fù)這個(gè)過(guò)程
if (index < right) {
this.quick(array, index, right);
}
}
return array;
}
// 劃分函數(shù)
private partition(array: T[], left: number, right: number): number {
// 從數(shù)組中選擇一個(gè)值做主元，此處選擇數(shù)組的中間值
const pivot = array[Math.floor((right + left) / 2)];
// 創(chuàng)建數(shù)組引用，分別指向左邊數(shù)組的第一個(gè)值和右邊數(shù)組的第一個(gè)值
let i = left;
let j = right;
// left指針和right指針沒(méi)有相互交錯(cuò)，就執(zhí)行劃分操作
while (i <= j) {
// 移動(dòng)left指針直至找到一個(gè)比主元大的元素
while (this.compareFn(array[i], pivot) === Compare.LESS_THAN) {
i++;
}
// 移動(dòng)right指針直至找到一個(gè)比主元小的元素
while (this.compareFn(array[j], pivot) === Compare.BIGGER_THAN) {
j--;
}
// 當(dāng)左指針指向的元素比主元大且右指針指向的元素比主元小，并且左指針?biāo)饕龥](méi)有右指針?biāo)饕髸r(shí)就交換i和j號(hào)元素的位置，隨后移動(dòng)兩個(gè)指針
if (i <= j) {
this.swap(array, i, j);
i++;
j--;
}
}
// 劃分結(jié)束，返回左指針?biāo)饕? return i;
}
編寫(xiě)測(cè)試代碼
我們通過(guò)一個(gè)例子，來(lái)測(cè)試下上述代碼是否都正確執(zhí)行。
const array = [12, 6, 3, 4, 1, 7];
const sort = new Sort(array);
const result = sort.quickSort();
console.log(result.join());
計(jì)數(shù)排序
計(jì)數(shù)排序是一個(gè)分布式排序，它是用來(lái)排序整數(shù)的優(yōu)秀算法。分布式排序使用已組織好的輔助數(shù)據(jù)結(jié)構(gòu)，然后進(jìn)行合并，得到排好序的數(shù)組。計(jì)數(shù)排序使用一個(gè)用來(lái)存儲(chǔ)每個(gè)元素在原始數(shù)組中出現(xiàn)次數(shù)的臨時(shí)數(shù)組。在所有元素都計(jì)數(shù)完成后，臨時(shí)數(shù)組已排好序并可迭代以構(gòu)建排序后的結(jié)果數(shù)組。
實(shí)現(xiàn)思路
- 找到要排序數(shù)組的最大值
- 以上一步找到的最大值+1為長(zhǎng)度創(chuàng)建一個(gè)計(jì)數(shù)數(shù)組
- 遍歷要排序的數(shù)組，以當(dāng)前遍歷的元素為索引，尋找計(jì)數(shù)數(shù)組中對(duì)應(yīng)的位置將其初始化為0，如果此處位置有相同元素的話就自增
- 遍歷計(jì)數(shù)數(shù)組，判斷當(dāng)前遍歷到的元素是否大于0，如果大于0就取當(dāng)前遍歷到的索引，替換待排序數(shù)組中的元素
接下來(lái)我們通過(guò)一個(gè)例子來(lái)講解下上述過(guò)程，如下圖所示：
實(shí)現(xiàn)代碼
接下來(lái)我們將上述思路轉(zhuǎn)換為代碼
countingSort(array: number[]): number[] {
// 待排序數(shù)組為空或只有一個(gè)元素則不用排序
if (array.length < 2) {
return array;
}
// 找到待排序數(shù)組中的最大值
const maxValue = this.findMaxValue(array);
// 創(chuàng)建計(jì)數(shù)數(shù)組，數(shù)組長(zhǎng)度為待排序數(shù)組的最大值+1
const counts = new Array(maxValue + 1);
// 遍歷待排序數(shù)組，為計(jì)數(shù)數(shù)組賦值
array.forEach((element) => {
// 以當(dāng)前遍歷到的元素值為索引將對(duì)應(yīng)位置元素值初始化為0
if (!counts[element]) {
counts[element] = 0;
}
// 當(dāng)前位置的值進(jìn)行自增，順便應(yīng)對(duì)數(shù)組中有重復(fù)值的情況，有重復(fù)值時(shí)當(dāng)前位置的值必定大于1
counts[element]++;
});
// 聲明一個(gè)變量用于數(shù)組最終排序
let sortedIndex = 0;
// 遍歷計(jì)數(shù)數(shù)組，根據(jù)計(jì)數(shù)數(shù)組的元素位置對(duì)待排序數(shù)組進(jìn)行排序
counts.forEach((count, i) => {
// 如果當(dāng)前遍歷到的元素值大于0，則執(zhí)行替換操作進(jìn)行排序
while (count > 0) {
// 將當(dāng)前元素索引賦值給array的sortedIndex號(hào)元素，隨后sortedIndex自增
array[sortedIndex++] = i;
// 當(dāng)前元素值自減，如果其值大于1，證明此處有重復(fù)元素，那么我們就繼續(xù)執(zhí)行while循環(huán)
count--;
}
});
// 最后，排序完成，返回排序好的數(shù)組
return array;
}
編寫(xiě)測(cè)試代碼
我們將上述圖中的例子放進(jìn)代碼中執(zhí)行，看看我們寫(xiě)的函數(shù)是否正確執(zhí)行。
const array = [12, 6, 3, 4, 1, 7];
const sort = new Sort(array);
const result = sort.countingSort(array);
console.log(result.join());
桶排序
桶排序也是一種分布式排序算法，它將元素分為不同的桶，再使用一個(gè)簡(jiǎn)單的排序算法，例如插入排序，來(lái)對(duì)每個(gè)桶進(jìn)行排序，最后，它將所有的桶合并為結(jié)果數(shù)組。
實(shí)現(xiàn)思路
首先，我們需要指定需要多個(gè)桶來(lái)排序各個(gè)元素，默認(rèn)情況，我們會(huì)使用5個(gè)桶。桶排序在所有元素平分到各個(gè)桶中時(shí)的表現(xiàn)最好。如果元素非常稀疏，則使用更多的桶會(huì)更好。如果元素非常密集，則使用較少的桶會(huì)更好。因此我們?yōu)榱怂惴ǖ男剩瑫?huì)讓調(diào)用者根據(jù)實(shí)際需求將桶的數(shù)量作為參數(shù)傳進(jìn)來(lái)。我們將算法分為兩個(gè)部分：
- 創(chuàng)建桶，并將桶分布到不同的桶中
- 對(duì)每個(gè)桶中的元素執(zhí)行排序算法并將所有桶合并成排序好后的結(jié)果數(shù)組
我們先來(lái)看看創(chuàng)建桶的思路
- 聲明創(chuàng)建桶函數(shù)（createBuckets），接收兩個(gè)參數(shù)：待排序數(shù)組（array），桶大小（bucketSize）
- 計(jì)算array中的最大值（maxValue）和最小值（minValue）
- 計(jì)算每個(gè)需要的桶數(shù)量，公式為：(maxValue - minValue) / bucketSize)+1
- 聲明一個(gè)二維數(shù)組buckets，用于存放所有桶
- 根據(jù)桶數(shù)量，初始化每個(gè)桶
- 遍歷array，將每個(gè)元素分布到桶中
- 計(jì)算需要將元素放到哪個(gè)桶中(bucketIndex)，公式為：(array[i] - minValue) / bucketSize
- 將元素與放進(jìn)合適的桶中，即buckets[bucketIndex].push(array[i])
- 將桶返回
接下來(lái)我們來(lái)看看對(duì)每個(gè)桶里的元素進(jìn)行排序的思路
- 創(chuàng)建排序桶函數(shù)（sortBuckets），接收一個(gè)參數(shù): 桶buckets
- 需要一個(gè)輔助數(shù)組sortedArray，用于存放排序好的結(jié)果數(shù)組
- 遍歷sortedArray
- 如果當(dāng)前桶內(nèi)存儲(chǔ)的桶buckets[i]不為null，就對(duì)其執(zhí)行插入排序
- 將排序好的桶buckets[i]解構(gòu)后放進(jìn)sortedArray中
- 最后，返回sortedArray
我們通過(guò)一個(gè)例子，來(lái)講解上述思路，如下圖所示
實(shí)現(xiàn)代碼
接下來(lái)，我們將上述思路轉(zhuǎn)換為代碼。
// 桶排序
bucketSort(array: number[], bucketSize = 5): T[] | number[] {
if (array.length < 2) {
return array;
}
// 創(chuàng)建桶，對(duì)桶進(jìn)行排序
return this.sortBuckets(<[][]>this.createBuckets(array, bucketSize));
}
/**
* 創(chuàng)建桶
* @param array 待排序數(shù)組
* @param bucketSize 桶大小，即每個(gè)桶里的元素?cái)?shù)量
*
* @return 二維數(shù)組類(lèi)型的桶
*/
private createBuckets = (array: number[], bucketSize: number): number[][] => {
// 計(jì)算數(shù)組最大值與最小值
let minValue = array[0];
let maxValue = array[0];
for (let i = 1; i < array.length; i++) {
if (array[i] < minValue) {
minValue = array[i];
} else if (array[i] > maxValue) {
maxValue = array[i];
}
}
// 計(jì)算需要的桶數(shù)量，公式為: 數(shù)組最大值與最小值的差值與桶大小進(jìn)行除法運(yùn)算
const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
// 用于存放桶的二維數(shù)組
const buckets: number[][] = [];
// 計(jì)算出桶數(shù)量后，初始化每個(gè)桶
for (let i = 0; i < bucketCount; i++) {
buckets[i] = [];
}
// 遍歷數(shù)組，將每個(gè)元素分布到桶中
for (let i = 0; i < array.length; i++) {
// 計(jì)算需要將元素放到哪個(gè)桶中，公式為: 當(dāng)前遍歷到的元素值與數(shù)組的最小值的差值與桶大小進(jìn)行除法運(yùn)算
const bucketIndex: number = Math.floor((array[i] - minValue) / bucketSize);
// 將元素放進(jìn)合適的桶中
buckets[bucketIndex].push(array[i]);
}
// 將桶返回
return buckets;
};
// 對(duì)每個(gè)桶進(jìn)行排序
private sortBuckets(buckets: T[][]): T[] {
const sortedArray: T[] = [];
for (let i = 0; i < buckets.length; i++) {
if (buckets[i] != null) {
// 調(diào)用插入排序
this.insertionSort(buckets[i]);
// 將排序好的桶取出來(lái)，放進(jìn)sortedArray中
sortedArray.push(...buckets[i]);
}
}
return sortedArray;
}
編寫(xiě)測(cè)試代碼
我們將上述圖中的例子放進(jìn)代碼中看其是否能正確執(zhí)行。
const array = [12, 5, 6, 7, 8, 9, 11, 3, 4, 19];
const sort = new Sort(array);
const result = sort.bucketSort(array);
console.log(result.join());
基數(shù)排序
基數(shù)排序也是一個(gè)分布式排序算法，它根據(jù)數(shù)字的有效位或基數(shù)將整數(shù)分布到桶中。比如，十進(jìn)制數(shù)，使用的基數(shù)是10.因此，算法將會(huì)使用10個(gè)桶用來(lái)分布元素并且首先基于各位數(shù)字進(jìn)行排序，然后基于十位數(shù)字，然后基于百位數(shù)字，以此類(lèi)推。
實(shí)現(xiàn)思路
基數(shù)排序也是用來(lái)排序整數(shù)，因此我們從最后一位開(kāi)始排序所有的數(shù)。首先，只會(huì)基于最后一位有效位對(duì)數(shù)字進(jìn)行排序，在下次迭代時(shí)，我們會(huì)基于第二個(gè)有效位進(jìn)行排序（十位數(shù)字），然后是第三個(gè)有效位（百位數(shù)字），以此類(lèi)推。我們繼續(xù)這個(gè)過(guò)程直到?jīng)]有待排序的有效位，因此我們需要知道數(shù)組中的最小值和最大值。實(shí)現(xiàn)基數(shù)排序我們需要一個(gè)輔助函數(shù)（countingSortForRadix），即根據(jù)有效位對(duì)數(shù)組進(jìn)行排序。接下來(lái)，我們先來(lái)看下基數(shù)排序主函數(shù)的實(shí)現(xiàn)思路。
- 創(chuàng)建基數(shù)排序函數(shù)（radixSort），接受2個(gè)參數(shù)：待排序數(shù)組array，基數(shù)radixBash
- 首先，獲取array的最大值maxValue和最小值minValue
- 聲明一個(gè)輔助變量significantDigit，用于存儲(chǔ)當(dāng)前有效數(shù)字，默認(rèn)從最后一位有效數(shù)字，即1
- 計(jì)算有效位，公式為：(maxValue - minValue) / significantDigit，計(jì)算出的值如果大于等于1執(zhí)行下述邏輯：
- 以當(dāng)前有效位作為參數(shù)調(diào)用singnificantDigit函數(shù)對(duì)數(shù)組進(jìn)行排序
- 當(dāng)前有效數(shù)字*基數(shù)，繼續(xù)執(zhí)行上述過(guò)程
- 最后，執(zhí)行完成返回排序好多的數(shù)組
接下來(lái)，我們來(lái)看下基于有效位進(jìn)行排序的函數(shù)實(shí)現(xiàn)思路。
- 創(chuàng)建countingSortForRadix函數(shù)，接受4個(gè)參數(shù)：待排序數(shù)組array，基數(shù)radixBase、有效位significantDigit、數(shù)組的最小值minValue
- 聲明桶索引bucketsIndex以及桶buckets以及輔助數(shù)組aux
- 通過(guò)radixBase來(lái)初始化桶，默認(rèn)初始化為0
- 遍歷array，基于有效位計(jì)算桶索引執(zhí)行計(jì)數(shù)排序
- 計(jì)算桶索引，公式為：((array[i] - minValue) / significantDigt) % radixBase
- 根據(jù)桶索引，執(zhí)行計(jì)數(shù)操作，即buckets[bucketsIndex++]
- 計(jì)算累積結(jié)果得到正確的計(jì)數(shù)值，從1開(kāi)始遍歷到radixBase位置。
- buckets[i]等于buckets[i] 加上buckrts[i - 1]的值
- 計(jì)數(shù)完成，遍歷array將值移回原始數(shù)組中，用aux輔助數(shù)組來(lái)存儲(chǔ)
- 計(jì)算當(dāng)前元素的桶索引bucketsIndex，公式為：((array[i] - minValue) / significantDigit) % radixBase
- 對(duì)當(dāng)前桶索引內(nèi)的元素執(zhí)行自檢操作，得到其在數(shù)組中的正確位置index
- 計(jì)算出索引后，在aux中的對(duì)應(yīng)位置存儲(chǔ)當(dāng)前遍歷到的元素
- 最后排序完成，返回axu。
我們通過(guò)一個(gè)例子來(lái)描述上述過(guò)程，如下圖所示。
實(shí)現(xiàn)代碼
接下來(lái)，我們將上述思路轉(zhuǎn)換為代碼.
/**
* 基數(shù)排序
* @param array 待排序數(shù)組
* @param radixBase 10進(jìn)制排序，基數(shù)為10
*/
radixSort(array: number[], radixBase = 10): number[] {
if (array.length < 2) {
return array;
}
// 獲取數(shù)組的最小值和最大值
const minValue = this.findMinValue(array);
const maxValue = this.findMaxValue(array);
// 當(dāng)前有效數(shù)字,默認(rèn)會(huì)從最后一位有效數(shù)字開(kāi)始排序
let significantDigit = 1;
/**
* 計(jì)算有效位
* 最大值和最小值的差與有效數(shù)字進(jìn)行除法運(yùn)算，其值大于等于1就代表還有待排序的有效位
*/
while ((maxValue - minValue) / significantDigit >= 1) {
// 以當(dāng)前有效位為參數(shù)對(duì)數(shù)組進(jìn)行排序
array = this.countingSortForRadix(array, radixBase, significantDigit, minValue);
// 當(dāng)前有效數(shù)字乘以基數(shù)，繼續(xù)執(zhí)行while循環(huán)進(jìn)行基數(shù)排序
significantDigit *= radixBase;
}
return array;
}
/**
* 基于有效位進(jìn)行排序
* @param array 待排序數(shù)組
* @param radixBase 基數(shù)
* @param significantDigit 有效位
* @param minValue 待排序數(shù)組的最小值
*/
private countingSortForRadix = (array: number[], radixBase: number, significantDigit: number, minValue: number) => {
// 聲明桶索引以及桶
let bucketsIndex;
const buckets = [];
// 輔助數(shù)組，用于計(jì)數(shù)完成的值移動(dòng)會(huì)原數(shù)組
const aux = [];
// 通過(guò)基數(shù)來(lái)初始化桶
for (let i = 0; i < radixBase; i++) {
buckets[i] = 0;
}
// 遍歷待排序數(shù)組，基于有效位計(jì)算桶索引執(zhí)行計(jì)數(shù)排序
for (let i = 0; i < array.length; i++) {
// 計(jì)算桶索引
bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase);
// 執(zhí)行計(jì)數(shù)操作
buckets[bucketsIndex]++;
}
// 計(jì)算累積結(jié)果得到正確的計(jì)數(shù)值
for (let i = 1; i < radixBase; i++) {
buckets[i] = buckets[i] + buckets[i - 1];
}
// 計(jì)數(shù)完成，將值移回原始數(shù)組中,用aux輔助數(shù)組來(lái)存儲(chǔ)
for (let i = array.length - 1; i >= 0; i--) {
// 計(jì)算當(dāng)前元素的桶索引
bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase);
// 對(duì)當(dāng)前桶索引內(nèi)的元素執(zhí)行自減操作,得到其在數(shù)組中的正確的位置
const index = --buckets[bucketsIndex];
// 計(jì)算出索引后，在aux中的對(duì)應(yīng)位置存儲(chǔ)當(dāng)前遍歷到的元素
aux[index] = array[i];
}
console.log(aux);
return aux;
};
編寫(xiě)測(cè)試代碼
接下來(lái)，我們將上圖中的例子放進(jìn)代碼中，觀察函數(shù)是否正確執(zhí)行。
const array = [12, 5, 6, 7, 8, 9, 11, 3, 4, 19];
const sort = new Sort(array);
const result = sort.radixSort(array);
console.log(result.join());
搜索算法
接下來(lái)，我們來(lái)學(xué)習(xí)搜索算法，搜索算法分為兩種：順序(線性)搜索和二分搜索。在之前文章中，我已經(jīng)詳細(xì)講解了這兩種搜索算法的基礎(chǔ)原理以及圖解實(shí)現(xiàn)，所以此處只講其代碼實(shí)現(xiàn)。文章傳送門(mén)：數(shù)組查找: 線性查找與二分查找本文示例代碼地址：SearchArithmetic.ts
順序搜索
順序搜索是最基本的搜索算法，它會(huì)將每一個(gè)數(shù)據(jù)結(jié)構(gòu)中的元素和我們要找的元素做比較。它也是最低效的一種搜索算法。
實(shí)現(xiàn)代碼
linearSearch(): number | null {
for (let i = 0; i < this.array.length; i++) {
if (this.array[i] === this.target) {
return i;
}
}
return null;
}
編寫(xiě)測(cè)試代碼
const array = [7, 8, 1, 2, 3, 5, 12, 13, 16, 19];
const searchArithmetic = new SearchArithmetic(array, 7);
const mid = searchArithmetic.linearSearch();
console.log(mid);
二分搜索
二分搜索要求被搜索的數(shù)據(jù)結(jié)構(gòu)已經(jīng)排好序，它的基本原理就是找到數(shù)組的中間值，然后將目標(biāo)值和找到的值進(jìn)行大小比較，如果比中間值大就往中間值的右邊找，否則就往中間值的左邊找。
實(shí)現(xiàn)思路
- 選擇數(shù)組的中間值
- 如果選中值是待搜索值，那么算法執(zhí)行完畢
- 如果待搜索值比選中值要小，則返回步驟1并在選中值左邊的子數(shù)組中尋找（較小）
- 如果待搜索值比選中值要大，則返回步驟1并在選中值右邊的子數(shù)組中尋找（較大）
實(shí)現(xiàn)代碼
binarySearch(): number | null {
// 對(duì)數(shù)組進(jìn)行排序
this.sort.quickSort();
// 設(shè)置指針作為數(shù)組邊界
let low = 0;
let high = this.array.length - 1;
while (low <= high) {
// 獲取數(shù)組中間值
const mid = Math.floor((low + high) / 2);
// 獲取數(shù)組的中間值
const element = this.array[mid];
// 如果數(shù)組中間值小于目標(biāo)值，low+1,向其右邊繼續(xù)找
if (this.compareFn(element, this.target) === Compare.LESS_THAN) {
low = mid + 1;
} else if (this.compareFn(element, this.target) === Compare.BIGGER_THAN) {
// 如果中間值大于目標(biāo)值,向其左邊繼續(xù)找
high = mid - 1;
} else {
// 中間值等于目標(biāo)值，元素找到，返回mid即當(dāng)前元素在數(shù)組的位置
return mid;
}
}
// 未找到，返回null
return null;
}
編寫(xiě)測(cè)試代碼
const array = [7, 8, 1, 2, 3, 5, 12, 13, 16, 19];
const searchArithmetic = new SearchArithmetic(array, 7);
const mid = searchArithmetic.binarySearch();
console.log(mid);
內(nèi)插搜索
內(nèi)插搜索是改良版的二分搜索。二分搜索總是檢查mid位置上的值，而內(nèi)插搜索可能會(huì)根據(jù)要搜索的值檢查數(shù)組中的不同地方。
實(shí)現(xiàn)思路
它遵循以下步驟：
- 使用position公式選中一個(gè)值
- 如果待搜索值比選中值要小，則返回步驟1并在選中值左邊的子數(shù)組中尋找（較小）
- 如果待搜索值比選中值要大，則返回步驟1并在選中值右邊的子數(shù)組中尋找（較大）
實(shí)現(xiàn)代碼
/**
* 內(nèi)插搜索
* 二分查找的優(yōu)化，通過(guò)特定算法計(jì)算delta和position的值優(yōu)化掉二分查找的尋找中間值做法
* @param equalsFn 校驗(yàn)兩個(gè)值是否相等函數(shù)
* @param diffFn 計(jì)算兩個(gè)數(shù)的差值函數(shù)
*/
interpolationSearch(equalsFn = defaultEquals, diffFn: IDiffFunction<T> = defaultDiff): number | null {
// 排序
this.sort.quickSort();
// 獲取數(shù)組程度
const { length } = this.array;
// 定義指針，確定數(shù)組邊界
let low = 0;
let high = length - 1;
// 聲明position，用于公式
let position = -1;
let delta = -1;
// 目標(biāo)值大于等于數(shù)組的low邊界值且目標(biāo)值小于等于high邊界值就執(zhí)行循環(huán)里的內(nèi)容
while (low <= high && biggerEquals(this.target, this.array[low], this.compareFn) && lesserEquals(this.target, this.array[high], this.compareFn)) {
// 目標(biāo)值與array的low邊界的值做差
// 與array的high邊界的值和low邊界的值做差
// 最后將二者得出的值做除法運(yùn)算，計(jì)算出delta值
delta = diffFn(this.target, this.array[low]) / diffFn(this.array[high], this.array[low]);
// 計(jì)算比較值的位置
position = low + Math.floor((high - low) * delta);
// 如果比較值位置的元素等于目標(biāo)值，則返回當(dāng)前索引
if (equalsFn(this.array[position], this.target)) {
return position;
}
// 如果比較值位置的元素小于目標(biāo)值，則向其右邊繼續(xù)找
if (this.compareFn(this.array[position], this.target) === Compare.LESS_THAN) {
low = position + 1;
} else {
// 如果比較值位置的元素大于目標(biāo)值，則向其左邊繼續(xù)查找
high = position - 1;
}
}
// 未找到
return null;
}
編寫(xiě)測(cè)試代碼
const array = [7, 8, 1, 2, 3, 5, 12, 13, 16, 19];
const searchArithmetic = new SearchArithmetic(array, 7);
const mid = searchArithmetic.interpolationSearch();
console.log(mid);
隨機(jī)算法
在日常開(kāi)發(fā)中，我們會(huì)遇到將數(shù)組中的元素打亂位置，這樣的場(chǎng)景，那么此時(shí)我們就需要設(shè)計(jì)一種隨機(jī)算法來(lái)實(shí)現(xiàn)了，現(xiàn)實(shí)中一個(gè)很常見(jiàn)的場(chǎng)景就是洗撲克牌。
Fisher-Yates算法
此處我們講解一種隨機(jī)算法，名為Fisher-Yates，顧名思義，該算法就是由Fisher 和 Yates 創(chuàng)造。
實(shí)現(xiàn)思路
該算法的核心思想就是，從數(shù)組的最后一位開(kāi)始迭代數(shù)組，將迭代到的元素和一個(gè)隨機(jī)位置進(jìn)行交換。這個(gè)隨機(jī)位置比當(dāng)前位置小。這樣這個(gè)就算法可以保證隨機(jī)過(guò)的位置不會(huì)再被隨機(jī)一次。下圖展示了這個(gè)算法的操作過(guò)程
實(shí)現(xiàn)代碼
export class ShuffleArithmetic<T> {
constructor(private array: T[]) {}
// Fisher-Yates隨機(jī)算法
fisherYates(): T[] {
// 從數(shù)組的最后一位向前遍歷數(shù)組
for (let i = this.array.length - 1; i > 0; i--) {
// 計(jì)算隨機(jī)位置,用一個(gè)隨機(jī)數(shù)與i+1相加,得出的隨機(jī)位置一定比當(dāng)前位置小
const randomIndex = Math.floor(Math.random() * (i + 1));
// 交換當(dāng)前位置的元素和隨機(jī)位置的元素
this.swap(i, randomIndex);
}
return this.array;
}
/**
* 交換數(shù)組的元素
* @param a
* @param b
* @private
*/
private swap(a: number, b: number) {
const temp: T = this.array[a];
this.array[a] = this.array[b];
this.array[b] = temp;
}
}
編寫(xiě)測(cè)試代碼
import { ShuffleArithmetic } from "./lib/ShuffleArithmetic.ts";
const array = [4, 5, 6, 1, 2, 3, 4, 5, 8, 9, 0, 11, 22, 41];
const shuffleArithmetic = new ShuffleArithmetic(array);
shuffleArithmetic.fisherYates();
console.log("隨機(jī)排序后的數(shù)組元素", array.join());
作者：神奇的程序員K
轉(zhuǎn)發(fā)鏈接：https://mp.weixin.qq.com/s/3B8dZRfbIuktSBeArXlmcQ
