js排序算法

js交换两个值的三种方法

方式1：算术运算

function swap1(arr, i, j) {let temp = arr[i];arr[i] = arr[j];arr[j] = temp
}

方式2：ES6解构

不需要第三方变量

function swap2(arr, i, j) {[arr[j], arr[i]] = [arr[i], arr[j]]
}

方式3：数组的特性

function swap3(arr, i, j) {const temp = [arr[i], arr[j]]arr[i] = temp[1]arr[j] = temp[0]
}

冒泡排序

实现思路

1. 通过相邻元素比较和交换
2. 使得每一趟遍历，最后的一个数数都是最大的
3. 循环都能找到未排序的子数组，直到排序完成。

图解

bubbleSort

/*** @Name:* @author: liuk* @Description: 冒泡排序* @data: 2023/4/13**/
// Bubble Sort
const bubbleSort = (arr) => {const len = arr.length;if (!len) return []for (let i = 0; i < len; i++) {for (let j = 0; j < len - i - 1; j++) {if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1)}}}return arr
}

参考视频

链接

选择排序

实现思路

1. 通过已排序序列末尾元素
2. 与剩余元素的最小值的比较和交换(索引)
3. 使得每一趟遍历，已排序序列从小到大排序，直到排序完成。

剩余元素为遍历节点之后的全部元素

图解

selectionSort

/*** @Name:* @author: liuk* @Description: 选择排序* @data: 2023/4/13**/
// Selection Sort
const selectionSort = (arr) => {const len = arr.lengthlet minIndex;if (!len) return []for (let i = 0; i < len; i++) {minIndex = ifor (let j = i; j < len; j++) {if (arr[j] < arr[minIndex]) {minIndex = j}}swap(arr, minIndex, i)}return arr
}

参考视频

链接

插入排序

实现思路

1. 通过当前遍历节点的值
2. 与已排序序列的每个值进行比较和交换(值)
3. 使得每一趟遍历，遍历节点前都为已排序序列，直到排序完成。

图解

insertionSort

/*** @Name:* @author: liuk* @Description: 插入排序* @data: 2023/4/13**/
// Insertion Sort
const insertionSort = (arr) => {const len = arr.length;let current;if (!len) return [];for (let i = 1; i < len; i++) {current = arr[i]let j = i - 1;//上一个元素while (j >= 0 && current < arr[j]) {arr[j + 1] = arr[j]j--}arr[j + 1] = current}return arr
}

参考视频

链接