排序算法
- 主要讲述七种排序方法并深入探究其使用场景
- 时间复杂度 O(n * n)
- 时间复杂度 O(n _ n) < 我在这里 < O(n _ logn)
- 时间复杂度 O(n * logn)
slow 三人组 O(n * n)
冒泡排序
- 顾名思义,冒泡排序每次选择一个最大或者最小的元素,循环 n^2 次后每个元素都将变得有序
function bubbleSort(arr: number[]) {
for (let i = 0; i < arr.length; i++) {、
for (let j = 0; j < arr.length; j++) {
if (arr[j] > arr[i]) {
[arr[j], arr[i]] = [arr[i], arr[j]];
}
}
}
return arr;
}
选择排序
function selectSort(arr: number[]) {
for (let i = 0; i < arr.length; i++) {
let min = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
[arr[min], arr[i]] = [arr[i], arr[min]];
}
return arr;
}
插入排序
- 插入排序可以理解为我们摸扑克牌,其中 i 代表我们新摸到的牌,j 代表我们手里的最后一张牌
function insertSort(arr: number[]) {
for (let i = 1; i < arr.length; i++) {
let j = i - 1;
while (j >= 0 && arr[j + 1] < arr[j]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
j -= 1;
}
}
return arr;
}
五五开小王子 O(n * (2/3) * n)
希尔排序
- 希尔排序是插入排序的变种,增加了 gap 间隔,从插入排序的 1 变为了数组长度的二分
function shellSort(arr: number[]) {
function insertSortForShell(arr: number[], gap: number) {
for (let i = gap; i < arr.length; i++) {
let j = i - gap;
while (j >= 0 && arr[j + gap] < arr[j]) {
[arr[j], arr[j + gap]] = [arr[j + gap], arr[j]];
j -= gap;
}
}
return arr;
}
let mid = arr.length >> 1;
while (mid) {
insertSortForShell(arr, mid);
mid >>= 1;
}
return arr;
}
fast 三人组 O(n * logn)
快速排序
- 快速排序是递归的算法,需要一个 partition 辅助函数进行分隔
function partition(arr: number[], left: number, right: number) {
const tmp = arr[left];
while (left < right) {
while (left < right && arr[right] >= tmp) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= tmp) {
left++;
}
arr[right] = arr[left];
}
arr[left] = tmp;
return left;
}
function quickSort(arr: number[], left: number, right: number) {
if (left < right) {
const mid = partition(arr, left, right);
quickSort(arr, left, mid);
quickSort(arr, mid + 1, right);
}
return arr;
}
归并排序
- 归并排序是递归的进行分隔然后合并两个有序数组,当数组长度为时就不需要分隔了自己本身就是有序数组了
function merge(left: number[], right: number[]) {
const tmp: number[] = [];
while (left.length && right.length) {
tmp.push(left[0] < right[0] ? left.shift()! : right.shift()!);
}
return [...tmp, ...left, ...right];
}
function mergeSort(arr: number[]) {
if (arr.length <= 1) return arr;
const mid = arr.length >> 1;
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
堆排序
function sift(arr: number[], low: number, high: number) {
let i = low;
let j = 2 * i + 1;
const tmp = arr[i];
while (j <= high) {
if (j + 1 <= high && arr[j + 1] > arr[j]) {
j = j + 1;
}
if (arr[j] > tmp) {
[arr[j], arr[i]] = [arr[i], arr[j]];
i = j;
j = 2 * i + 1;
} else {
break;
}
}
arr[i] = tmp;
}
function heapSort(arr: number[]) {
const high = arr.length - 1;
for (let i = (high - 1) >> 1; i >= 0; i--) {
sift(arr, i, high);
}
for (let j = high; j >= 0; j--) {
[arr[j], arr[0]] = [arr[0], arr[j]];
sift(arr, 0, j - 1);
}
return arr;
}