系列文章目录
文章目录
系列文章目录前言一、冒泡排序二、快速排序三、插入排序四、总结
前言
这是我整理的数组的三种常见排序方法，如有问题欢迎指出！
一、冒泡排序
冒泡排序，是一种简单的排序算法，它通过重复遍历待排序的数列，比较相邻元素并交换它们的位置，直到整个数列有序；这个过程就像气泡一样，让较大的元素逐渐“浮”到数组的顶端；
从头到尾遍历整个数列，比较相邻的元素； 如果前一个元素大于后一个元素，则交换它们的位置； 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对； 对整个数组除了最后一个元素的元素重复上述过程，每次需要交换的元素越来越少，直到没有需要交换的元素为止；
let arr = [4, 5, 3, 21, 8, 90, 6];
for (let i = 0; i < arr.length; i++) {
for (let j = i - 1; j < arr.length; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
console.log(arr);//[3, 4, 5, 6, 8, 21, 90]
二、快速排序
快速排序是一种运行高效，应用广泛的排序算法，其核心操作是：选择数组中某个元素作为“中间数”，将所有小于中间数的元素放在其左边，大于基准数的元素放在其右边，从而将数组划分成左子数组和右子数组，再分别递归左子数组和右子数组。
let arr = [4, 5, 3, 21, 8, 90, 6];
function quickSort(arr) {
if (arr.length <= 1) {
return arr
}
let left = [];
let right = [];
let center = arr[Math.floor(arr.length / 2)];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < center) {
left.push(arr[i])
} else if (arr[i] > center) {
right.push(arr[i])
}
}
return quickSort(left).concat([center], quickSort(right))
}
console.log(quickSort(arr));//[3, 4, 5, 6, 8, 21, 90]
三、插入排序
1.从第二个元素开始遍历： 将数组视为两部分，第一部分是已排序的部分，初始只有第一个元素；第二部分是未排序的部分，包括剩余的元素。
2.找到合适的位置插入： 对于未排序部分的每个元素，与已排序部分的元素依次比较，找到合适的位置插入，使得已排序部分依然有序。
3.重复操作： 重复以上步骤，直至整个数组有序。
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
// 当前待插入的元素
let current = arr[i];
let j = i - 1;
// 在已排序的部分中找到合适的位置插入
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
// 插入当前元素
arr[j + 1] = current;
}
return arr;
}
const arr3 = [4, 5, 3, 21, 8, 90, 6];
console.log(insertionSort(arr3)); // 输出 [3, 4, 5, 6, 8, 21, 90]
四、总结
冒泡排序的使用最为广泛，其次是快速排序，再就是插入排序；虽然后两个排序方式使用相对少一些，但还是要知道这两种方法的存在。