JS怎样实现插入 交换 挑选和归并四种排序

今天小编跟大家讲解下有关“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 

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)

稳定性

稳定

（编辑：银川站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!