js合并排序
时间: 2023-06-22 15:29:36 浏览: 47
JS合并排序(归并排序)是一种基于分治思想的排序算法,其主要思路是将待排序数组分成若干个子数组,分别进行排序,再将子数组合并成一个有序的数组。
以下是JS合并排序的实现代码:
```javascript
function mergeSort(arr) {
if (arr.length <= 1) return arr; // 当数组长度小于等于1时,直接返回该数组
const midIndex = Math.floor(arr.length / 2); // 找到数组中间位置
const leftArr = mergeSort(arr.slice(0, midIndex)); // 对左半部分进行归并排序
const rightArr = mergeSort(arr.slice(midIndex)); // 对右半部分进行归并排序
return merge(leftArr, rightArr); // 将左右两部分合并
}
function merge(leftArr, rightArr) {
const result = []; // 用于存放合并后的结果
let leftIndex = 0; // 左半部分数组的指针
let rightIndex = 0; // 右半部分数组的指针
while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
if (leftArr[leftIndex] < rightArr[rightIndex]) {
result.push(leftArr[leftIndex]); // 将左半部分数组中的元素加入结果数组中
leftIndex++;
} else {
result.push(rightArr[rightIndex]); // 将右半部分数组中的元素加入结果数组中
rightIndex++;
}
}
// 将剩余的元素加入结果数组中
return result.concat(leftArr.slice(leftIndex)).concat(rightArr.slice(rightIndex));
}
```
该算法的时间复杂度为O(nlogn),是一种稳定的排序算法。