前端10大排序算法
image.png
image.png
冒泡🫧排序
通过相邻元素的比较和交换，使得每一趟循环都能找到未有序数组的最大值或最小值。 内循环： 使用相邻双指针 j , j + 1 从左至右遍历，依次比较相邻元素大小，若左元素大于右元素则将它们交换；遍历完成时，最大元素会被交换至数组最右边 。 外循环： 不断重复「内循环」，每轮将当前最大元素交换至 剩余未排序数组最右边 ，直至所有元素都被交换至正确位置时结束。
image.png
/**
* 冒泡🫧
* 每一趟找出最大的,总共比较次数为arr.length-1次,每次的比较次数为arr.length-1-i次，依次递减
* @param {*} arr
* @returns array
*/
function bubbleSort(arr) {
/**
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
原始数组： [ 99, 88, 66, 101, 90, 45 ]
第1次循环 [ 88, 66, 99, 90, 45, 101 ]
第2次循环 [ 66, 88, 90, 45, 99, 101 ]
第3次循环 [ 66, 88, 45, 90, 99, 101 ]
第4次循环 [ 66, 45, 88, 90, 99, 101 ]
第5次循环 [ 45, 66, 88, 90, 99, 101 ]
*/
let len = arr.length;
if (!len) {
return [];
}
console.log('原始数组：', arr);
//外循环，对被排序的数组进行遍历，轮数为数组的长度
for (let i = 0; i < len - 1; i++) {
// 内循环，循环比较相邻元素
for (let j = 0; j < len - 1 - i; j++) {
//如果前一个元素大于后一个元素的话，就交换两个元素的位置，最后是以从大到小的顺序输出
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; //元素交换
}
}
console.log(`第${i+1}次循环`, arr);
}
return arr;
}
image.png
优化
普通冒泡排序的时间复杂度恒为 O(N2)，与输入数组的元素分布无关。 通过增加一个标志位 flag ，若在某轮「内循环」中未执行任何交换操作，则说明数组已经完成排序，直接返回结果即可。 优化后的冒泡排序的最差和平均时间复杂度仍为 O(N2) ;在输入数组 已排序 时，达到 最佳时间复杂度 𝜴(N)
function bubbleSort(arr) {
let len = arr.length;
if (!len) {
return [];
}
console.log('原始数组：', arr);
//外循环，对被排序的数组进行遍历，轮数为数组的长度
for (let i = 0; i < len - 1; i++) {
let flag = false; // 初始化标志位
// 内循环，循环比较相邻元素
for (let j = 0; j < len - 1 - i; j++) {
//如果前一个元素大于后一个元素的话，就交换两个元素的位置，最后是以从大到小的顺序输出
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; //元素交换
flag = true; // 记录交换元素
}
}
if (!flag) break; // 内循环未交换任何元素，则跳出
console.log(`第${i+1}次循环`, arr);
}
return arr;
}选择排序
思路：依次找到剩余元素的最小值或者最大值，放置在末尾或者开头。
image.png
/**
* 选择排序
* 依次找到剩余元素的最小值或者最大值，放置在末尾或者开头。
* @param {Array} arr
* @returns
*/
function selectionSort(arr) {
let len = arr.length;
let minIndex;
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[minIndex], arr[i]] = [arr[i], arr[minIndex]]//交换两个元素
}
return arr;
}插入排序
思路：以第一个元素为有序数组，其后的元素通过再这个已有序的数组中找到合适的元素并插入。
function insertSort(arr) {
let length = arr.length,
preIndex, current;
for (let i = 1; i < length; i++) {
preIndex = i - 1;
current = arr[i];
// 和已经排序好的序列进行比较，插入到合适的位置
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
console.log(`第${i}次循环`, arr);
}
return arr;
}希尔排序
通过某个增量 gap，将整个序列分给若干组，从后往前进行组内成员的比较和交换，随后逐步缩小增量至 1。希尔排序类似于插入排序，只是一开始向前移动的步数从 1 变成了 gap
function shellSort(arr) {
let len = arr.length;
// 初始步数
let gap = parseInt(len / 2);
// 逐渐缩小步数
while (gap) {
// 从第gap个元素开始遍历
for (let i = gap; i < len; i++) {
// 逐步其和前面其他的组成员进行比较和交换
for (let j = i - gap; j >= 0; j -= gap) {
if (arr[j] > arr[j + gap]) {
[arr[j], arr[j + gap]] = [arr[j + gap], arr[j]];
} else {
break;
}
}
}
gap = parseInt(gap / 2);
}
}归并排序
递归将数组分为两个序列，有序合并这两个序列。作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
- 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第2种方法）。
- 自下而上的迭代。
function /**
* 归并排序
*/
mergeSort(arr) {
let len = arr.length;
if (len < 2) {
return arr;
}
let middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
console.log(`处理过程：`, arr);
return this.merge(this.mergeSort(left), this.mergeSort(right));
},
/**
* 归并排序辅助方法
*/
function merge(left, right) {
let 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;
}快速排序
快速排序算法是一种基于分治思想的排序算法，其核心思路在于通过选取一个基准值，将待排序数组划分为左右两个子序列，其中左侧序列所有元素均小于基准值，右侧序列所有元素均大于基准值。之后对左右子序列递归进行快排操作，最终将整个序列排好序。 以下是使用 TypeScript 实现的快速排序算法代码：
function quickSort(arr: number[]): number[] {
if (arr.length <= 1) {
return arr;
}
const pivotIndex = Math.floor(arr.length / 2);
const pivot = arr[pivotIndex];
const left = [];
const right = [];
for (let i = 0; i < arr.length; i++) {
if (i === pivotIndex) {
continue;
}
const currentItem = arr[i];
if (currentItem < pivot) {
left.push(currentItem);
} else {
right.push(currentItem);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}堆排序
堆排序算法是一种基于堆数据结构的排序算法，其核心思路在于将待排序数组看做二叉树，通过构建大顶堆或小顶堆来实现排序。对于大顶堆，每个节点的值均大于或等于它的子节点；对于小顶堆，每个节点的值均小于或等于它的子节点。排序时，取堆顶元素，将其存储到已排序数组中，并从堆中删除；然后重新调整剩余元素形成新的堆，重复以上操作直至所有元素排序完成。 以下是使用 TypeScript 实现的堆排序算法代码：
function heapSort(arr: number[]): number[] {
const 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;
}
// 堆化函数，将以i为根节点的子树调整为大顶堆
function heapify(arr: number[], len: number, i: number) {
let largest = i; // 最大值默认为根节点
const left = 2 * i + 1; // 左子节点下标
const 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);
}
}记数排序
记数排序（Counting Sort）是一种非基于比较的排序算法，其时间复杂度为O(n+k)，其中k表示待排序数组中最大元素与最小元素之差加1。该算法的基本思想是统计每个元素在待排序数组中出现的次数，然后根据统计结果构建有序序列。
/**
* 计数排序
* @param arr 待排序数组
* @returns 排序后数组
*/
function countingSort(arr: number[]): number[] {
const max = Math.max(...arr);
const count = new Array(max + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
const res = [];
for (let i = 0; i <= max; i++) {
while (count[i]--) {
res.push(i);
}
}
return res;
}桶排序
桶排序（Bucket Sort）是一种线性排序算法，它利用了函数的映射关系，将要排序的数据分到有限数量的桶子里，每个桶子再分别排序。桶排序的时间复杂度取决于桶的数量和桶内使用的排序算法，通常情况下是O(n+k)。
/**
* 桶排序
* @param arr 待排序数组
* @param bucketSize 桶大小
* @returns 排序后数组
*/
function bucketSort(arr: number[], bucketSize = 5): number[] {
if (arr.length === 0) {
return arr;
}
// 找出最大值和最小值
let min = arr[0];
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
} else if (arr[i] > max) {
max = arr[i];
}
}
// 计算桶的数量
const bucketCount = Math.floor((max - min) / bucketSize) + 1;
const buckets: number[][] = [];
for (let i = 0; i < bucketCount; i++) {
buckets[i] = [];
}
// 将元素分配到桶中
for (let i = 0; i < arr.length; i++) {
const index = Math.floor((arr[i] - min) / bucketSize);
buckets[index].push(arr[i]);
}
// 对每个桶进行排序，并将结果合并
const res = [];
for (let i = 0; i < buckets.length; i++) {
if (buckets[i]) {
const sortedBucket = countingSort(buckets[i]);
for (let j = 0; j < sortedBucket.length; j++) {
res.push(sortedBucket[j]);
}
}
}
return res;
}基数排序
基数排序（Radix Sort）是一种多关键字排序算法，可用于对数字序列进行排序。基数排序先按照最低有效位（LSB）对元素进行排序，然后依次按照次低有效位、次次低有效位……最高有效位进行排序。该算法的时间复杂度为O(d*(n+k))，其中d表示数字位数，k表示每个数字可能的取值范围。
/**
* 基数排序
* @param arr 待排序数组
* @returns 排序后数组
*/
function radixSort(arr: number[]): number[] {
const max = Math.max(...arr);
const buckets: number[][] = [];
// 初始化桶
for (let i = 0; i < 10; i++) {
buckets[i] = [];
}
// 计算最大数字的位数
let digitCount = 0;
while (max > 0) {
max = Math.floor(max / 10);
digitCount++;
}
// 根据每一位进行排序
for (let i = 0; i < digitCount; i++) {
for (let j = 0; j < arr.length; j++) {
const num = arr[j];
const digit = Math.floor(num / Math.pow(10, i)) % 10;
buckets[digit].push(num);
}
arr = [];
for (let k = 0; k < buckets.length; k++) {
while (buckets[k].length) {
arr.push(buckets[k].shift()!);
}
}
}
return arr;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-11-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录