冒泡排序
时间复杂度
O(n^2)
空间复杂度O(1)
typescript
function bubbleSort(arr) {
// 外层循环控制每次排序的轮数
for (let i = 0; i < arr.length - 1; i++) {
// 内层循环控制每次排序的比较和交换
for (let j = 0; j < arr.length - 1 - i; j++) {
// 如果前一个元素大于后一个元素,则交换它们的位置
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
// 示例
const arr = [3, 1, 6, 2, 8, 5];
console.log(bubbleSort(arr)); // 输出 [1, 2, 3, 5, 6, 8]
选择排序
时间复杂度
O(n^2)
空间复杂度O(1)
typescript
function selectSort(nums) {
let len = nums.length;
// 最后一轮只有一个元素,一定是最大的元素,因此写 i < len - 1
for (let i = 0; i < len - 1; i++) {
// 在 [i + 1, len - 1] 区间里选择最小的元素的下标
// 这种一趟扫描选出最值的方法,有一个很形象的名字叫:打擂台算法
let minIndex = i;
for (let j = i + 1; j < len; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
// 将最小的元素交换到未排序的第一项
[nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
}
return nums;
}
插入排序
时间复杂度
O(n^2)
空间复杂度O(1)
typescript
let insertionSort = function (nums) {
let len = nums.length;
// 1. 将 nums[i] 插入到区间 [0, i) 使之成为有序数组
for (let i = 1; i < len; i++) {
// 2. 从后向前逐个交换,直到前面的那个元素小于或者等于当前要插入的这个元素
for (let j = i; j > 0; j--) {
if (nums[j - 1] > nums[j]) {
[nums[j - 1], nums[j]] = [nums[j], nums[j - 1]]; // 交换位置
} else {
break; // 插入后无需再比较,跳出循环
}
}
}
return nums;
}
希尔排序
时间复杂度
O(nlogn)
空间复杂度O(1)
归并排序
时间复杂度
O(nlogn)
空间复杂度O(n)
typescript
function mergeSort(arr) {
if (arr.length < 2) {
return arr;
}
// 分
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
// 合
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
const result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) {
result.push(left.shift());
}
while (right.length) {
result.push(right.shift());
}
return result;
}
var arr = [6, 1, 4, 7, 3, 8, 2, 5];
console.log(mergeSort(arr)); // 输出: [ 1, 2, 3, 4, 5, 6, 7, 8 ]
快速排序
时间复杂度
O(nlogn)
空间复杂度O(logn)
typescript
function quickSort(arr) {
if (arr.length < 2) {
return arr
}
const mid = arr[0]
const left = []
const right = []
for (let i = 1; i < arr.length; i++) {
if (arr[i] < mid) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return quickSort(left).concat(mid, quickSort(right))
}
var arr = [6, 1, 4, 7, 3, 8, 2, 5]
console.log(quickSort(arr)) // 输出: [ 1, 2, 3, 4, 5, 6, 7, 8 ]
堆排序
时间复杂度
O(nlogn)
空间复杂度O(1)