一、冒泡排序
思路：遍历数组，比较相邻的元素，如果比后者大（升序），就交换位置，进行n-1轮
function bubbleSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
const tem = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = tem
}
}
}
return arr
}
let arr = [8, 4, 2, 5, 2]
console.log(bubbleSort(arr))
过程：
第一趟交换
[8, 4, 2, 5, 2] - [4, 8, 2, 5, 2] - [4, 2, 8, 5, 2] - [4, 2, 5, 8, 2] - [4, 2, 5, 2, 8]
第二趟交换
[4, 2, 5, 2, 8] - [2, 4, 5, 2, 8] - [2, 4, 2, 5, 8]
第三趟交换
[2, 4, 2, 5, 8] - [2, 2, 4, 5, 8]
改进：
思路：当一次遍历前后数组不产生变化时，说明该数组已经有序，结束排序
function bubbleSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
let exchange = false
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
const tem = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = tem
exchange = true;
}
}
if(!exchange) return arr
}
return arr
}
let arr = [8, 4, 2, 5, 2, 8, 9]
console.log(bubbleSort(arr))
二、选择排序
思路： 找到最小值，放在第一位，然后找到第二小的值，放在第二位，以此类推，执行n-1轮
function selecttionSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
let min = i
for (let j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) min = j
}
if (min != i) {
[arr[min], arr[i]] = [arr[i], arr[min]]
}
}
return arr
}
console.log(selecttionSort([3, 2, 5, 1, 4]))
过程：
[3, 2, 5, 1, 4] - [1, 2, 5, 3, 4] - [1, 2, 5, 3, 4] - [1, 2, 3, 5, 4] - [1, 2, 3, 4, 5]
三、插入排序
思路：从数组下标1开始每增1项排序一次，越往后遍历次数越多
function insertSort(arr) {
//从数组的第二位开始往左比较，所以i=1
for (let i = 1; i < arr.length; i++) {
let target = i; //这个是当前要插入的数，第一次循环默认位第二个数
for (let j = i - 1; j >= 0; j--) {
//将target与左边排序好的数比较，如果比较小，则与被比较的数交换位置
if (arr[target] < arr[j]) {
const tem = arr[target]
arr[target] = arr[j]
arr[j] = tem
}else{
//如果前面没有比target小的数，退出循环
break;
}
target = j
}
}
return arr
}
let arr = [3, 2, 5, 1, 4]
console.log(arr)
console.log(insertSort(arr))
过程：
index = 1: [3, 2, 5, 1, 4] - [2, 3, 5 ,1, 4]
index = 2: [2, 3, 5, 1, 4]
index = 3: [2, 3, 5 ,1, 4] - [2, 3, 1, 5, 4] - [2, 1, 3, 5, 4] - [1, 2, 3, 5, 4]
index = 4: [1, 2, 3, 5, 4] - [1, 2, 3, 4 ,5]
四、归并排序
思路：将无序的数组 拆成N部分进行有序处理，然后合并。
代码参考https://juejin.cn/post/6911517734152962056
const mergeSort = (arr) => {
if (arr.length < 2) {
return arr;
}
const mid = Math.floor(arr.length / 2); //获取数组中间下标，将数组分为左右两个数组
const left = arr.slice(0, mid); //左边数组
const right = arr.slice(mid, arr.length); //右边数组
//调用递归将左右两边的数组继续拆分，直到数组长度小于2
const orderLeft = mergeSort(left); //有序的左边数组，最后return出来的长度为1
const orderRight = mergeSort(right); //有序的右边数组
const res = [];
//当左边或者右边数组有值的情况下
while (orderLeft.length || orderRight.length) {
//当左边数组和右边数组都有值的情况下，比较左右两边数组的第一个数，将较小的数推入res中
if (orderLeft.length && orderRight.length) {
res.push(
orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift()
);
}
//如果右边数组值为空，左边不为空，将左边的数全部推入res
else if (orderLeft.length) {
res.push(orderLeft.shift()); //删除并返回数组的第一个元素
} else if (orderRight.length) {
res.push(orderRight.shift());
}
}
//返回合并后的有序数组作为递归的结果
return res;
};
console.log(mergeSort([9,8,7,6,5,4,3]))
五、快速排序
思路：也是分治思想。找一个数为基准，比它小的放左边，比它大的放右边，然后递归。
const quickSort = (function a(arr) {
if (arr.length < 2) return arr
const mid = arr[0] //数组的第一位为基准
const left = [] //比基准小的数组
const right = [] //比基准大的数组
//从数组的第二位开始循环与基准进行比较
for (let i = 1; i < arr.length; i++) {
if (arr[i] < mid) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
//返回值为左边数组+基准元素+右边数组
return [...a(left), mid, ...a(right)]
})
console.log(quickSort([9, 8, 7, 6, 5, 4, 3]))
网友评论