算法是程序开发中不可或缺的一部分。排序算法作为最基本、最常用的算法之一，在程序开发中起到了至关重要的作用。本文将深入探讨十大经典排序算法，探索这些排序算法的实现原理、时间复杂度及其适用场景并使用TypeScript语言来实现。废话不多说，让我们一同踏上 TypeScript排序算法实战的旅程！
一、综合分析二、冒泡排序冒泡排序是一种基本的排序算法，其思路是比较相邻元素的大小，如果逆序则交换，一轮结束后将最大元素“冒泡”到数列的末尾。这个过程像冒泡一样，因此被称为冒泡排序。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
代码语言：javascript复制const bubblesort = (arr) => {
for (let i = 0; i < arr.length; i++){
for (let j = 0; j < arr.length - i; j++){
if(arr[j] > arr[j + 1])
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
return arr;
}
console.log(bubblesort([4, 2, 6, 1, 5, 8, 7, 3]));时间复杂度：
最好情况：已经有序，只需要进行一次比较，时间复杂度为O(n)。最坏情况：完全逆序，需要进行n轮比较，时间复杂度为O(n^2)。平均情况：时间复杂度也为O(n^2)。三、选择排序选择排序是一种简单直观的排序算法，其思想是每次从待排序的数列中选择最小（或最大）的元素，放到已排序数列的末尾（或开头），直到整个数列有序。
代码语言：javascript复制const selectsort = (arr) => {
for (let i = 0; i < arr.length; i++) {
let tmpMin = arr[i];
let tmpIndex = i;
for (let j = i; j < arr.length; j++){
if (tmpMin > arr[j]) {
tmpMin = arr[j];
tmpIndex = j;
}
}
[arr[i], arr[tmpIndex]] = [arr[tmpIndex], arr[i]]
}
return arr;
}
console.log(selectsort([4, 2, 6, 1, 5, 8, 7, 3]));时间复杂度：
最好情况：O(n^2)。最坏情况：O(n^2)。平均情况：O(n^2)。四、插入排序插入排序是一种简单直观的排序算法，其基本思想是将待排序序列分为两部分，一部分已经排好序，另一部分待排序，然后将待排序部分的元素依次插入到已排序部分的适当位置，使得插入后仍然有序。
代码语言：javascript复制const insertsort = (arr) => {
for (let i = 1; i < arr.length; i++){
let cur = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > cur) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = cur;
}
return arr;
}
console.log(insertsort([4, 2, 6, 1, 5, 8, 7, 3]));时间复杂度：
最好情况：O(n)。最坏情况：O(n^2)。平均情况：O(n^2)。五、归并排序归并排序是一种经典的分治算法，它的基本思想是将待排序的数组划分为两个子数组，分别对这两个子数组进行排序，然后将排序后的子数组合并成一个有序数组。具体来说，归并排序的步骤如下：
分解：将待排序的数组不断地二分，直到每个子数组只包含一个元素，即认为这些子数组已经有序。合并：将已经有序的子数组两两合并，形成新的有序子数组。重复步骤2，直到只剩下一个有序数组，即为最终排序结果。简易写法：
代码语言：javascript复制const quickSort = (arr: number[]): number[] => {
if (arr.length <= 1) return arr;
const pivotIndex = Math.floor(arr.length / 2);
const pivot = arr[pivotIndex];
const left: number[] = [];
const right: number[] = [];
for (let i = 0; i < arr.length; i++) {
if (i == pivotIndex) continue;
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
};
console.log(quickSort([4, 2, 6, 1, 5, 8, 7, 3]));归并排序的时间复杂度是O(nlogn)，其中n是待排序数组的长度。虽然归并排序的时间复杂度比较稳定，但需要额外的空间来存储辅助数组，因此其空间复杂度是O(n)。
时间复杂度：假设数组长度为 n，需要进行 logn 次归并操作；每次归并操作需要 O(n) 的时间复杂度；
最好情况：O(n)。最坏情况：O(nlogn)。平均情况：O(nlogn)。五、快速排序代码语言：javascript复制const quickSort = (arr: number[]): number[] => {
if (arr.length <= 1) return arr;
const pivotIndex = Math.floor(arr.length / 2);
const pivot = arr[pivotIndex];
const left: number[] = [];
const right: number[] = [];
for (let i = 0; i < arr.length; i++) {
if (i == pivotIndex) continue;
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
};六、希尔排序希尔排序是一种插入排序的变体，也称为缩小增量排序。其基本思想是将待排序的数组分成若干个子序列，对每个子序列进行插入排序，然后逐步缩小增量，直到增量为1。
具体来说，希尔排序的步骤如下：
选择一个增量序列：将待排序数组按照一定的间隔划分成若干个子序列，对每个子序列进行插入排序。这里的增量序列可以使用Hibbard增量序列，它的公式为2k−12k−1，其中k为增量的大小，从n/2、n/4、n/8等不断除以2，直到增量等于1为止。对子序列进行插入排序：对每个子序列进行插入排序，将子序列中的数依次插入到前面已经排好序的序列中，使得插入后仍然有序。逐步缩小增量：对于增量序列，逐步缩小增量，重复步骤2，直到增量为1。代码语言：javascript复制const shellSort = (arr: number[]): number[] => {
let gap = Math.floor(arr.length / 2);
while (gap > 0) {
for (let i = gap; i < arr.length; i++) {
const cur = arr[i];
let j = i;
while (j >= gap && arr[j - gap] > cur) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = cur;
}
gap = Math.floor(gap / 2);
}
return arr;
};
console.log(shellSort([4, 2, 6, 1, 5, 8, 7, 3]));最好情况：O(n)。最坏情况：O(n2n2)。平均情况：O(nlogn) ~ O(n2n2)。七、堆排序堆排序的实现过程主要分为两个步骤：
构建最大堆：将待排序的数组看作是完全二叉树的形式，从最后一个非叶子节点开始，依次对每个非叶子节点进行堆调整，使其成为最大堆的形式。具体做法是比较节点和它的两个子节点之间的大小，将较大的子节点调整到父节点的位置上，然后递归地对调整过后的子节点进行堆调整。堆排序：从最大堆中取出根节点（即数组的第一个元素），将其与最后一个元素交换位置，然后对剩余的节点重新进行堆调整，以确保剩余节点仍然构成最大堆。重复这个过程，直到所有元素都被取出并排序。堆排序相较于其他排序算法的优势在于，它是一种原地排序算法，只需要一个额外的空间来存放根节点的值，没有浪费的空间。同时，堆排序还具有稳定的时间复杂度和稳定的排序结果。不过，需要注意的是，堆排序对于小规模的数据排序并不是特别高效，适用于大规模数据的排序。
代码语言：javascript复制const heapSort = (arr: number[]): number[] => {
const adjustHeap = (arr: number[], i: number, len: number) => {
const tmp = arr[i];
for (let j = 2 * i + 1; j < len; j = 2 * j + 1) {
if (j + 1 < len && arr[j + 1] > arr[j]) j++;
if (arr[j] > tmp) {
arr[i] = arr[j];
i = j;
} else {
break;
}
}
arr[i] = tmp;
};
// 先建立大根堆（从最后一个非叶子节点向上调整）
for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
// 每次把堆顶的数与最后一个数交换，并重新调整堆
for (let i = arr.length - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
adjustHeap(arr, 0, i);
}
return arr;
};
console.log(heapSort([4, 2, 6, 1, 5, 8, 7, 3]));八、计数排序代码语言：javascript复制const countSort = (arr: number[]): number[] => {
if (arr.length <= 1) return arr;
// 找出最大值和最小值
let max = arr[0];
let min = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
// 统计数列中每个值出现的次数
const count = new Array(max - min + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
let index = 0;
for (let i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i + min;
count[i]--;
}
}
return arr;
};
console.log(countSort([4, 2, 6, 1, 5, 8, 7, 3]));九、桶排序代码语言：javascript复制const bucketSort = (arr: number[], bucketSize: number): number[] => {
if (arr.length <= 1) return arr;
// 插入排序
function insertionSort(arr: number[]) {
let i;
let j;
let temp;
for (i = 1; i < arr.length; i++) {
temp = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
return arr;
}
// 找到数组中的最大值和最小值
let minValue = arr[0];
let maxValue = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < minValue) minValue = arr[i];
else if (arr[i] > maxValue) maxValue = arr[i];
}
// 计算桶的数量
const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
const buckets = new Array(bucketCount);
for (let i = 0; i < buckets.length; i++) {
buckets[i] = [];
}
// 将数组中的元素分配到各个桶中
for (let i = 0; i < arr.length; i++) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
// 对每个桶中的元素进行排序
arr.length = 0;
for (let i = 0; i < buckets.length; i++) {
if (buckets[i].length > 0) {
insertionSort(buckets[i]);
for (let j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
}
return arr;
};
console.log(bucketSort([4, 2, 6, 1, 5, 8, 7, 3], 5));十、基数排序代码语言：javascript复制const radixSort = (arr: number[]) => {
const maxDigit = getMaxDigit(arr);
// 获取最大位数
function getMaxDigit(arr: number[]) {
let max = 0;
for (let i = 0; i < arr.length; i++) {
const digit = getDigitCount(arr[i]);
max = Math.max(max, digit);
}
return max;
} // 获取数字的位数
function getDigitCount(num: number) {
if (num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
} // 获取数字的第i位数字
function getDigit(num: number, i: number) {
return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}
for (let i = 0; i < maxDigit; i++) {
const buckets: number[][] = []; // 创建桶
for (let j = 0; j < arr.length; j++) {
const digit = getDigit(arr[j], i); // 获取数字的第i位数字
if (!buckets[digit]) {
buckets[digit] = [];
}
buckets[digit].push(arr[j]); // 将数字放入相应的桶中
}
const tmp: number[] = [];
arr = tmp.concat(...buckets); // 将桶中的数字取出来，重新放入arr数组中
}
return arr;
};
console.log(radixSort([4, 2, 6, 1, 5, 8, 7, 3]));