本文深入解析JavaScript中四种核心排序算法的实现原理与代码。涵盖直接插入排序、冒泡排序（含优化）、快速排序及归并排序。详细阐述各算法的时间复杂度、空间复杂度及稳定性，并提供完整JS代码示例，帮助开发者理解分治与递归在排序中的应用。
一、插入排序
插入排序包含直接插入排序、折半插入排序和希尔排序等变体，本文重点实现最常用的直接插入排序。
直接插入排序
该方法将数组左侧部分视为已有序序列，每次从右侧未排序部分取出一个元素，将其插入到左侧有序序列的正确位置。
在插入过程中，从有序序列的最右侧元素开始向前比较。若当前比较的元素值大于待插入元素，则将该元素向后移动一位，继续向前比较，直到找到合适位置或到达序列起始处。
function insertSort(array) {
//第一个默认已经排好
for (let i = 1; i < array.length; i++) {
let target = i;
for (let j = i - 1; j >= 0; j--) {
if (array[target] < array[j]) {
[array[target], array[j]] = [array[j], array[target]]
target = j;
} else {
break;
}
}
}
return array;
}
复杂度
时间复杂度：O(n2)
空间复杂度:O(1)
稳定性
稳定
二、交换排序
（1）冒泡排序
遍历数组，依次比较相邻的两个元素。若当前元素小于前一个元素（即顺序错误），则交换它们的位置，使较小元素像气泡一样逐渐“冒”到前端。
经过一次完整的遍历后，最前端的元素即为当前未排序部分的最小值。
后续循环继续执行上述操作，但无需再处理已经排序好的前端元素。
优化策略：若在单次遍历中未发生任何元素交换，说明数组已完全有序，可提前终止循环以节省时间。
function bubbleSort(array) {
//第一个循环是所需次数
for (let j = 0; j < array.length; j++) {
let complete = true;
for (let i = array.length-1; i>j; i--) {
// 比较相邻数
if (array[i] < array[i -1]) {
[array[i], array[i - 1]] = [array[i - 1], array[i]];
complete = false;
}
}
// 没有冒泡结束循环
if (complete) {
break;
}
}
return array;
}复杂度
时间复杂度：O(n2)
空间复杂度:O(1)
稳定性
稳定
（2）快速排序
快速排序的核心思想是通过一趟排序将待排数据分割成独立的两部分，其中一部分的所有数据均小于另一部分的所有数据。随后对这两部分数据分别递归执行快速排序，直至整个数据序列变为有序。
实现步骤：
- 选择一个基准元素target（通常选择序列的第一个元素）。
- 遍历数组，将小于target的元素移动到数组左侧，大于target的元素移动到数组右侧。
- 分别对target左侧和右侧的子序列递归执行快速排序。
从上述步骤可见，快速排序利用了分治思想，即将大问题分解为小问题递归求解。
以下是对序列6、1、2、7、9、3、4、5、10、8进行排序的具体过程演示。
//JS自带的sort()就是快排
function quickSort(array, start, end) {
if (end - start < 1) {
return;
}
const target = array[start];
let l = start;
let r = end;
while (l < r) {
while (l < r && array[r] >= target) {
r--;
}
array[l] = array[r];
while (l < r && array[l] < target) {
l++;
}
array[r] = array[l];
}
array[l] = target;
quickSort(array, start, l - 1);
quickSort(array, l + 1, end);
return array;
}复杂度
时间复杂度：平均O(nlogn)，最坏O(n2)，实际上大多数情况下小于O(nlogn)
空间复杂度:O(logn)（递归调用消耗）
稳定性
不稳定
三、选择排序
（1）简单选择排序
每次遍历未排序部分，选取最小的元素，将其交换到已排序序列的末尾（即未排序部分的起始位置）。
function selectionSort(array) {
for (let i = 0; i < array.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
[array[minIndex], array[i]] = [array[i], array[minIndex]];
}
}
复杂度
时间复杂度：O(n2)
空间复杂度:O(1)
稳定性
不稳定
（2）堆排序
首先构建一个大顶堆，此时堆顶元素一定是当前序列中的最大值。
将堆顶元素（第一个元素）与堆的最后一个元素交换，使最大值位于序列末尾。随后对剩余元素重新调整为大顶堆。
重复上述交换与调整过程，从后往前依次确定每个位置的最大值，直至排序完成。
function heapSort(array) {
creatHeap(array);
console.log(array);
// 交换第一个和最后一个元素，然后重新调整大顶堆
for (let i = array.length - 1; i > 0; i--) {
[array[i], array[0]] = [array[0], array[i]];
adjust(array, 0, i);
}
return array;
}
// 构建大顶堆，从第一个非叶子节点开始，进行下沉操作
function creatHeap(array) {
const len = array.length;
const start = parseInt(len / 2) - 1;
for (let i = start; i >= 0; i--) {
adjust(array, i, len);
}
}
// 将第target个元素进行下沉，孩子节点有比他大的就下沉
function adjust(array, target, len) {
for (let i = 2 * target + 1; i < len; i = 2 * i + 1) {
// 找到孩子节点中最大的
if (i + 1 < len && array[i + 1] > array[i]) {
i = i + 1;
}
// 下沉
if (array[i] > array[target]) {
[array[i], array[target]] = [array[target], array[i]]
target = i;
} else {
break;
}
}
}复杂度
时间复杂度：O(nlogn)
空间复杂度:O(1)
稳定性
不稳定
四、归并排序
归并排序是基于归并思想实现的一种高效排序方法。
该算法是分治法（Divide and Conquer）的典型应用。分治法将原问题分解为若干小问题递归求解，然后在“治”的阶段将各子问题的解合并，即“分而治之”。
- 核心操作是将已有序的子序列合并，从而生成完全有序的序列。
- 具体而言，先使每个子序列内部有序，再使子序列段之间有序。
- 若将两个有序表合并成一个有序表，称为二路归并。
分割：
- 将数组从中点分割为左、右两个子数组。
- 递归地对左、右数组进行分割，直到子数组长度小于2（即不可再分）。
归并：
在合并阶段，左右两个子数组已经是有序的。
创建一个临时存储数组temp，比较左右两数组的第一个元素，将较小的元素加入temp数组。
若左右数组中有一个已为空，则另一个数组剩余的所有元素必然大于temp中的所有元素，直接将其全部追加到temp末尾。
function mergeSort(array) {
if (array.length < 2) {
return array;
}
const mid = Math.floor(array.length / 2);
const front = array.slice(0, mid);
const end = array.slice(mid);
return merge(mergeSort(front), mergeSort(end));
}
function merge(front, end) {
const temp = [];
while (front.length && end.length) {
if (front[0] < end[0]) {
temp.push(front.shift());
} else {
temp.push(end.shift());
}
}
while (front.length) {
temp.push(front.shift());
}
while (end.length) {
temp.push(end.shift());
}
return temp;
}在实际编程题目中，上述合并过程可能涉及额外的删除操作，对于极大样本可能导致超时。建议采用下文提供的优化方法。
function merge(left, right){
let leftLen = left.length, rightLen = right.length;
let i = 0, j = 0;
let temp = new Array(leftLen + rightLen);
for(let cur = 0; cur < leftLen + rightLen; cur++){
// 检查i, j有没有超界
if(i >= leftLen) temp[cur]= right[j++];
else if(j >= rightLen) temp[cur] = left[i++];
else if(left[i] <= right[j]){
temp[cur] = left[i++];
}else{
temp[cur] = right[j++];
}
}
return temp;
}复杂度
时间复杂度：O(nlogn)
空间复杂度:O(n)
稳定性
稳定
到此这篇关于详解JavaScript如何实现四种常用排序的文章就介绍到这了,更多相关JavaScript排序内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！