前端十种排序算法解析

1. 冒泡排序

1.1 说明

1. 冒泡排序为一种常用排序算法，执行过程为从数组的第一个位置开始，相邻的进行比较，将最大的数移动到数组的最后位置
2. 执行的时间复杂度与空间复杂度为 o(n^2)

1.2 执行过程

• 1. 从数组的第一个位置开始，截止位置为 arr.length - 1 - i, 相邻比较元素值
• 2. 如果前个元素值大于后个相邻元素值，交换两个元素的值
• 3. 重复执行 2 步骤
• 4. for 循环执行的次数完成及完成排序

1.3 实现代码

function bubbleSort(arr) {for (let i = 0; i < arr.length; i++) {for (let j = 0; j < arr.length - i - 1; j++) {//  比较相邻元素值，前个元素值大于后面元素的值就交换元素值if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];}}}return arr;
}

2. 选择排序

2.1 说明

1. 选择排序为默认选择一个数为最大或最小值
2. 默认选择第一个元素值为最小值，
3. 默认拿第一个元素索引与后面元素比较，如果后面元素小于该元素值，最小索引值为该元素的索引

2.2 执行过程

1. 定义一个minIndex = i; i从0开始
2. 比较Arr[minIndex] > arr[minIndex + 1]
3. 重复步骤 2 找出最小的元素索引
4. 交换元素位置 arr[i] = arr[minIndex], arr[minIndex= arr[i]

2.3 实现代码

function selectSort(arr = []) {for(var i = 0; i < arr.length; i++) {var minIndex = i; // 假设选择第一个元素为最小值，最小值的开始索引值从为i，也就是从0开始for(var j = minIndex + 1; j < arr.length; j++) {// 相邻比较元素值，找出比选择数更小的值if (arr[j] < arr[minIndex]) {minIndex = j}}// 如果最小值的索引和当前选择值的索引值不相等，则交换元素值位置if (minIndex != i) {[arr[minIndex], arr[i]] = [arr[i], arr[minIndex]]}}return arr
}

3. 归并排序

3.1

1. 归并排序为一种分治排序思想，通过将一个大数组分为多个子数组进行组内完成排序
2. 将组内完成排序的子数组再进行合并完成数组排序

3.2 执行过程

• 1. 从数组的一半位置拆分数组为左子数组（left）,右子数组（right）
• 2. 声明一个接受left,right两参数的函数，在函数内部分别比较两个子数组

3.3 实现代码

3.3.1

function mergeSort(arr = []) {if (arr.length < 2) return arrvar merge = (left, right) => {// 定义两个数组开始比较的索引值都从第一个元素开始var i = 0; var j = 0;// 定义一个比较完后的空数组var result = []while(i < left.length && j < right.length) {// 从两个数组的0位置开始比较，如果左数组第一个值小于右数组的第一个值，将做数组第一个值添加到空数组中，左数组索引值递增，再用左数组的第二个元素与右数组的第一个值比较，重复该步骤if (left[i] < right[j]) {result.push(left[i++])} else {result.push(right[j++])}}// 左数组剩余为比较的，默认添加到数组中while (i < left.length) {result.push(left[i++])}// 右数组剩余为比较的，默认添加到数组中while (j < right.length) {result.push(right[j++])}return result}var mid = Math.floor(arr.length / 2)var left = mergeSort(arr.slice(0, mid))var right = mergeSort(arr.slice(mid))return merge(left, right)
}

3.3.2

function mergeSort(arr) {if (arr.length <= 1) return arr;const mid = Math.floor(arr.length / 2);const left = mergeSort(arr.slice(0, mid));const right = mergeSort(arr.slice(mid));return merge(left, right);
}function merge(left, right) {let result = [];while (left.length && right.length) {left[0] < right[0] ? result.push(left.shift()) : result.push(right.shift());}return result.concat(left, right);
}

4. 快速排序

4.1 说明

1. 快速排序的思路为，找出一个基准数，然后从数组的两端开始，分别与基准数进行比较

4.2 实现代码

// 定义快速排序函数，参数为待排序的数组
function quickSort(array: number[]): number[] {// 定义辅助函数，用于排序function sort(left: number, right: number): void {// 如果左边的索引比右边的索引大，说明区间内已经没有数据，退出函数if (left >= right) {return;}// 取出基准数let pivot = array[left];// 定义两个指针let i = left;let j = right;// 开始排序while (i < j) {// 从右边开始搜索，直到找到比基准数小的数while (i < j && array[j] >= pivot) {j--;}// 如果找到了，则将该数存放在左边if (i < j) {array[i] = array[j];i++;}// 从左边开始搜索，直到找到比基准数大的数while (i < j && array[i] <= pivot) {i++;}// 如果找到了，则将该数存放在右边if (i < j) {array[j] = array[i];j--;}}// 将基准数存放在最终的位置上array[i] = pivot;// 递归处理基准数左边的数据sort(left, i - 1);// 递归处理基准数右边的数据sort(i + 1, right);}// 调用辅助函数，开始排序sort(0, array.length - 1);// 返回排序后的数组return array;
}

5. 插入排序

5.1 说明

插入排序的思想为选择一个数，与一个有序数组进行比较，找到小与该数的位置插入

5.2 实现代码

function insertionSort(arr: number[]): number[] {// 对于数组的每一个元素，从它开始到0位置，比较该元素和前一个元素的大小for (let i = 1; i < arr.length; i++) {let current = arr[i];let j = i - 1;// 如果该元素小于前一个元素，那么前一个元素向后移动，并继续向前比较while (j >= 0 && arr[j] > current) {arr[j + 1] = arr[j];j--;}// 如果该元素大于前一个元素，那么它将放到合适的位置arr[j + 1] = current;}// 返回排序后的数组return arr;
}// 测试数据
const testArr = [5, 2, 9, 1, 5, 6];
// 调用插入排序函数
const sortedArr = insertionSort(testArr);
// 打印结果
console.log(sortedArr);

6. 希尔排序

6.1 说明

希尔排揎为插入排序的改进方法，先将数组分组，然后每个子数组再进行排序

6.2 实现代码

function shellSort(arr) {// 定义增量, 每次分组, 增量为数组长度的一半let gap = Math.floor(arr.length / 2);while (gap > 0) {// 按组进行排序for (let i = gap; i < arr.length; i++) {// 获取当前元素let current = arr[i];let j = i;// 将相邻元素比较, 满足条件就后移while (j >= gap && arr[j - gap] > current) {arr[j] = arr[j - gap];j -= gap;}// 将当前元素插入合适的位置arr[j] = current;}// 每次递减增量, 直到为1gap = Math.floor(gap / 2);}return arr;
}

7. 基数排序

7.1 说明

1. 按位数进行排序
2. 只适合整数

7.2 实现代码

function radixSort(arr) {// 找到数组中的最大数const max = Math.max(...arr);// 找到最大数的位数const maxDigitCount = String(max).length;// 遍历位数for (let k = 0; k < maxDigitCount; k++) {// 创建桶const digitBuckets = Array.from({ length: 10 }, () => []);// 遍历数组for (let i = 0; i < arr.length; i++) {// 获取位数对应的值const digit = getDigit(arr[i], k);// 将数添加到对应的数对应的桶中digitBuckets[digit].push(arr[i]);}// 依次合并桶中的数arr = [].concat(...digitBuckets);}return arr;
}function getDigit(num, place) {return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

8. 计数排序

8.1 说明

非比较排序，适用于整数

8.2 实现代码

function countingSort(arr) {// 获取最大数const max = Math.max(...arr);// 创建有序的数组const count = new Array(max + 1).fill(0);const output = new Array(arr.length);// 遍历进行计数arr.forEach(num => count[num]++);for (let i = 1; i < count.length; i++) {count[i] += count[i - 1];}for (let i = arr.length - 1; i >= 0; i--) {output[count[arr[i]] - 1] = arr[i];count[arr[i]]--;}return output;
}

9. 桶排序

9.1 说明

将元素分到有限数量的桶里再排序

9.2 实现代码

function bucketSort(arr, bucketSize = 5) {if (arr.length === 0) return arr;const min = Math.min(...arr);const max = Math.max(...arr);const bucketCount = Math.floor((max - min) / bucketSize) + 1;const buckets = new Array(bucketCount).fill().map(() => []);arr.forEach(num => {const bucketIndex = Math.floor((num - min) / bucketSize);buckets[bucketIndex].push(num);});const result = [];buckets.forEach(bucket => {insertionSort(bucket); // 可以使用其他排序算法result.push(...bucket);});return result;
}

10. 堆排序

10.1 说明

利用堆数据结构设计

10.2 实现代码

function heapSort(arr) {let len = arr.length;for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {heapify(arr, len, i);}for (let i = len - 1; i > 0; i--) {[arr[0], arr[i]] = [arr[i], arr[0]];heapify(arr, i, 0);}return arr;
}function heapify(arr, len, i) {let largest = i;let left = 2 * i + 1;let right = 2 * i + 2;if (left < len && arr[left] > arr[largest]) largest = left;if (right < len && arr[right] > arr[largest]) largest = right;if (largest !== i) {[arr[i], arr[largest]] = [arr[largest], arr[i]];heapify(arr, len, largest);}
}

总结

排序算法 时间复杂度(平均) 空间复杂度 稳定性
冒泡排序 O(n²) O(1) 稳定
选择排序 O(n²) O(1) 不稳定
归并排序 O(n log n) O(n) 稳定
快速排序 O(n log n) O(log n) 不稳定
插入排序 O(n²) O(1) 稳定
希尔排序 O(n log n) O(1) 不稳定
基数排序 O(nk) O(n + k) 稳定
计数排序 O(n + k) O(k) 稳定
桶排序 O(n + k) O(n + k) 稳定
堆排序 O(n log n) O(1) 不稳定