在計(jì)算機(jī)科學(xué)中捻浦，排序是將一串?dāng)?shù)據(jù)按照一定的順序排列起來的算法晤揣。排序算法是解決實(shí)際問題中常用的基本算法之一，應(yīng)用范圍非常廣泛朱灿。
常見的排序算法有冒泡排序昧识、選擇排序、插入排序盗扒、歸并排序跪楞、快速排序缀去、堆排序等等。不同的排序算法有著不同的特點(diǎn)和應(yīng)用場(chǎng)景甸祭，選擇適合的排序算法可以提高程序的效率缕碎。
下面我們就來深入淺出的講解一下幾種排序算法的原理和應(yīng)用，同時(shí)也提供相關(guān)的 TypeScript 代碼實(shí)現(xiàn)池户。
冒泡排序
冒泡排序是一種簡單直觀的排序方法咏雌，它的基本思想是通過不斷比較相鄰的元素，重復(fù)地將大的元素交換到后面校焦，從而逐步將整個(gè)序列排好順序赊抖。
下面是 TypeScript 實(shí)現(xiàn)冒泡排序的代碼：
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
選擇排序
選擇排序的基本思想是每次將未排序序列中最小的元素作為已排序序列的末尾元素。即每次選擇一個(gè)最小的數(shù)放到前面已經(jīng)排序好的序列的最后寨典。
下面是 TypeScript 實(shí)現(xiàn)選擇排序的代碼：
const len = arr.length;
let minIndex: number;
for (let i = 0; i < len - 1; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
插入排序
插入排序的基本思想是將未排序序列中的元素插入到已排序序列中的恰當(dāng)位置氛雪，使得插入后的序列仍然有序。
下面是 TypeScript 實(shí)現(xiàn)插入排序的代碼：
const len = arr.length;
let preIndex: number, current: number;
for (let i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
歸并排序
歸并排序采用分治的思想凝赛，將原序列分成較小的序列注暗，每個(gè)子序列排序后合并成一個(gè)大的有序序列。
下面是 TypeScript 實(shí)現(xiàn)歸并排序的代碼：
function mergeSort(arr: number[]): number[] {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const leftArr = arr.slice(0, mid);
const rightArr = arr.slice(mid);
return merge(mergeSort(leftArr), mergeSort(rightArr));
}
function merge(left: number[], right: number[]): number[] {
const res: number[] = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
res.push(left[leftIndex]);
leftIndex++;
} else {
res.push(right[rightIndex]);
rightIndex++;
}
}
return res.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
快速排序
快速排序采用分治的思想墓猎，將原序列分成兩個(gè)子序列捆昏，然后對(duì)子序列排序，最后將兩個(gè)子序列合并成一個(gè)有序序列毙沾。
下面是 TypeScript 實(shí)現(xiàn)快速排序的代碼：
function quickSort(arr: number[]): number[] {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[0];
const leftArr: number[] = [];
const rightArr: number[] = [];
for (let i = 1; i < arr.length; i++) {
arr[i] < pivot ? leftArr.push(arr[i]) : rightArr.push(arr[i]);
}
return quickSort(leftArr).concat(pivot).concat(quickSort(rightArr));
}
堆排序
堆排序?qū)⒋判蛐蛄袠?gòu)建成一個(gè)大根堆或小根堆骗卜，然后將堆頂元素放到序列的最后，再將剩余元素重新構(gòu)建成一個(gè)堆左胞，重復(fù)上述操作直到整個(gè)序列有序寇仓。
下面是 TypeScript 實(shí)現(xiàn)堆排序的代碼：
function heapSort(arr: number[]): number[] {
buildHeap(arr);
for (let i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
maxHeapify(arr, 0, i - 1);
}
return arr;
}
function buildHeap(arr: number[]): void {
const len = arr.length;
const lastNode = len - 1;
const parent = Math.floor((lastNode - 1) / 2);
for (let i = parent; i >= 0; i--) {
maxHeapify(arr, i, len - 1);
}
}
function maxHeapify(arr: number[], start: number, end: number): void {
let root = start;
let child = root * 2 + 1;
while (child <= end) {
if (child + 1 <= end && arr[child] < arr[child + 1]) {
child++;
}
if (arr[root] < arr[child]) {
swap(arr, root, child);
root = child;
child = root * 2 + 1;
} else {
return;
}
}
}
function swap(arr: number[], i: number, j: number): void {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
以上就是六種常見的排序算法以及 TypeScript 實(shí)現(xiàn)代碼。在實(shí)際開發(fā)中烤宙，我們需要根據(jù)不同的應(yīng)用場(chǎng)景選擇不同的排序算法遍烦，從而提高程序的效率。
