sort

快速排序

June 14, 2022

sort

思想 # 分治 + 递归 步骤 # 选定参考元素 p (例如最右侧元素) 遍历数组，将比参考元素小的元素都挪到左边，并记录元素数量 遍历结束，数组分为 <= p | >p | p 将 p 移到中间 <=p | p | >p 返回中间的索引 递归处理 <=p 部分 递归处理 >p 部分 排序结束 实现 # /** * 数组分割 */ const partition = (arr, p, r) => { // 选数组最后一个元素为分割点 const pivot = arr[r]; let i = p - 1; // 遍历，将比分割点小的元素都挪到左边 for (let j = p; j < r; j++) { if (arr[j] <= pivot) { i++; let tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } // 将分割点的元素挪到左右数组中间 const tmp = arr[i + 1]; arr[i + 1] = pivot; arr[r] = tmp; // 返回分割点的索引 return i + 1; }; /** * 快速排序 */ const quickSort = (arr, p, r) => { // p < r 时，数组中不止一个元素，需要排序，否则无需排序 if (p < r) { // 数组分割，找出分割点索引，分割点左侧的值都不大于分割点，右侧的值都大于分割点 const pivotIdx = partition(arr, p, r); // 快排左右两侧的子数组，注意这俩子数组里均不包含 pivotIdx // 左数组快排 quickSort(arr, p, pivotIdx - 1); // 右数组快排 quickSort(arr, pivotIdx + 1, r); } return arr; }; const arr = [2, 8, 7, 1, 3, 5, 6, 4]; export { quickSort }; 分析 # 时间复杂度： O(nlogn)

插入排序

June 10, 2022

sort

实现 # 时间复杂度 \( O(n^2 \) const insertSort = (arr) => { const len = arr.length // 从第二个元素开始遍历 for (let i = 1; i < len; i ++ ) { const ele = arr[i] // 索引i位置的值依次跟前面的元素比 for (let j = i - 1; j >= 0; j --) { const cur = arr[j] const next = arr[j + 1] if(cur < ele) { break } arr[j] = next arr[j+1] = cur } } return arr } 分析 #

归并排序

June 3, 2022

sort

实现 # 归并排序，采用分治法，时间复杂度为 \(O(nlog n)\) /** * @param {number[]} arr 待合并原始数组 * @param {number} p 左索引，第一个元素的索引 * @param {number} q 中位索引 * @param {number} r 右索引，最后一个元素的索引 * * [p, q), [q, r] 均为已排序好的子数组 * * 将 [p,q), [q, r] 合并为一个排序好的数组 * */ const merge = (arr, p, q, r) => { // concat 的为哨兵节点 const arrLeft = arr.slice(p, q + 1).concat(Number.POSITIVE_INFINITY); const arrRight = arr.slice(q + 1, r + 1). ...