Appearance
数据结构和算法
常用排序
冒泡排序（Bubble Sort）
解题思路
给定一个数组，从左到右依次冒泡，把较大的数往右边挪动即可。
实现
每两个元素比较大小并进行交换，直到这一轮当中最大或最小的元素被放置在数组的尾部，然后不断地重复这个过程，直到所有元素都排好位置。其中，核心操作就是元素相互比较。
js
const arr = [2, 1, 7, 9, 5, 8]
function sort(arr) {
let len = arr.length
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换相邻的两个元素
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
console.log(sort(arr))插入排序（Insertion Sort）
解题思路
不断地将尚未排好序的数插入到已经排好序的部分。
实现
首先将数组分成左右两个部分，左边是已经排好序的部分，右边是还没有排好序的部分。
js
const arr = [2, 1, 7, 9, 5, 8]
function sort(arr) {
let len = arr.length
for (let i = 1; i < len; i++) {
let current = arr[i] // 当前要插入的元素
let j = i - 1 // 已排序部分的最后一个元素的索引
// 将大于current的元素向后移动
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j]
j--
}
// 插入当前元素到合适位置
arr[j + 1] = current
}
return arr
}
console.log(sort(arr))归并排序（Merge Sort）
解题思路
核心是分治，就是把一个复杂的问题分成两个或多个相同或相似的子问题，然后把子问题分成更小的子问题，直到子问题可以简单的直接求解，最原问题的解就是子问题解的合并。归并排序将分治的思想体现得淋漓尽致。
实现
一开始先把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素，才开始排序。
排序的方法就是按照大小顺序合并两个元素，接着依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。
js
const arr = [2, 1, 7, 9, 5, 8]
function sort(arr) {
if (arr.length <= 1) {
return arr // 当数组长度小于等于1时，无需继续拆分
}
let midIndex = Math.floor(arr.length / 2) // 中间索引
let leftArr = arr.slice(0, midIndex) // 左侧数组
let rightArr = arr.slice(midIndex) // 右侧数组
// 递归拆分左右两个子数组
let sortedLeftArr = sort(leftArr)
let sortedRightArr = sort(rightArr)
// 合并两个有序数组
return merge(sortedLeftArr, sortedRightArr)
}
// 合并两个有序数组
function merge(leftArr, rightArr) {
let mergedArr = []
let leftIndex = 0
let rightIndex = 0
// 比较左右两个数组的元素，并按照顺序合并到结果数组中
while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
if (leftArr[leftIndex] <= rightArr[rightIndex]) {
mergedArr.push(leftArr[leftIndex])
leftIndex++
} else {
mergedArr.push(rightArr[rightIndex])
rightIndex++
}
}
// 将剩余未合并的元素添加到结果数组中
while (leftIndex < leftArr.length) {
mergedArr.push(leftArr[leftIndex])
leftIndex++
}
while (rightIndex < rightArr.length) {
mergedArr.push(rightArr[rightIndex])
rightIndex++
}
return mergedArr
}
console.log(sort(arr))快速排序（Quick Sort）
解题思路
快速排序也采用了分治的思想。把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。
举例：把班里的所有同学按照高矮顺序排成一排。
解法：老师先随机地挑选了同学 A，让所有其他同学和 A 比高矮，比 A 矮的都站在 A 的左边，比 A 高的都站在 A 的右边。接下来，老师分别从左边和右边的同学里选择了同学 B 和 C，然后不断地筛选和排列下去。
在分成较小和较大的两个子数组过程中，如何选定一个基准值（也就是同学 A、B、C 等）尤为关键。
js
let arr = [2, 1, 7, 9, 5, 8]
function sdort(arr) {
if (arr.length <= 1) {
return arr // 当数组长度小于等于1时，无需排序
}
let pivotIndex = Math.floor(arr.length / 2) // 基准元素索引
let pivot = arr.splice(pivotIndex, 1)[0] // 基准元素值
let leftArr = []
let rightArr = []
// 将比基准元素小的元素放入左侧数组，比基准元素大的元素放入右侧数组
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
leftArr.push(arr[i])
} else {
rightArr.push(arr[i])
}
}
// 递归排序左右两个子数组，并合并结果
return sdort(leftArr).concat([pivot], sdort(rightArr))
}
console.log(sdort(arr))