排序
冒泡排序
- 相邻元素置换位置,从头到尾
- 然后从第二个元素开始,重复第一步
空间复杂度 O(n^2)
优化:有序数据可以标记判断,将时间降到 O(n)
js
// 1 4 5 2 3
// 1 4 2 5 3
// 1 2 4 3 5
// 1 2 3 4 5
// 了解原理后如何思考,从具体到抽象
// 内部是置换循环,外部是重复循环
// 内循环,减掉已经排好的,当 i 为 1 时,j < arr.length - 1
// 小于等于不动,大于时置换
function bubbleSort(arr) {
let i, j
let n = arr.length
for (i = 0; i < n - 1; i++) { // 注意边界处理
for (j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
var tmp = arr[j]
arr[j] = arr[i]
arr[i] = tmp
}
}
}
return arr
}
let result = bubbleSort([0, 10, 1, 3, 5, 4])
console.log(result)
// 优化
function bubbleSort(arr) {
let i, j
let n = arr.length
let isSorted = true // flag
for (i = 0; i < n - 1; i++) { // 注意边界处理
for (j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
var tmp = arr[j]
arr[j] = arr[i]
arr[i] = tmp
isSorted = false
}
}
if (isSorted) {
break
}
}
return arr
}
字符串按长度排序
js
function strSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i + 1; j < arr.length; j++) {
// if (arr[i] > arr[j]) {
if (arr[i].length > arr[j].length) {
let tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
}
}
return arr
}
console.log(strSort(['abcd', 'a', 'abc', 'abd']))
// expect: ["a", "ab", "abc", "abcd"]
// 快排 [...sort(left), mid, ...sort(right)]
function strSort(arr) {
if (arr.length <= 1) return arr
let left = []
let right = []
let midIndex = Math.floor(arr.length / 2)
let mid = arr[midIndex]
for (let i = 0; i < arr.length; i++) {
if (i === midIndex) continue
if (arr[i].length < mid.length) {
// if (arr[i] > mid) {
left.push(arr[i])
} else (
right.push(arr[i])
)
}
return [...strSort(left), mid, ...strSort(right)]
}
console.log(strSort(['abcd', 'a', 'abc', 'abd']))
选择排序
选择元素置换位置
js
// 如何在未排序元素中找到最小值
// 外循环的 i 表示当前位置,min 表示最小值的位置
// 内循环只查找最小值,内循环完成后如果最小值位置与当前位置不同,则进行置换
function selectionSort(arr) {
let i, j, selected, tmp
for (i = 0; i < arr.length; i++) {
selected = i
for (j = i + 1; j < arr.length; j++) {
if (arr[selected] > arr[j]) {
selected = j
}
}
if (i !== selected) {
tmp = arr[selected]
arr[selected] = arr[i]
arr[i] = tmp
}
}
return arr
}
let result = selectionSort([3, 1, 2, 5, 4])
console.log(result)
快速排序(快排)
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为较小和较大的2个子序列,然后递归地排序两个子序列。
- 找出基准值
- 递归形式:[...fn(left), pivot, ...fn(right)]
- pivot 单独拿出来,不需要参与递归处理
js
// 先考虑主要功能,再考虑边界情况
// 注意最后数组合并用了递归,结束条件是传入的数组只剩下一个值
// 是否假定了数组没有重复项,如果有重复项如何处理
// 方法1:将 pivot 从中间取出,与剩余比较
// 方法2:将 pivot 从开头pop,与剩余比较
function quickSort(arr) {
if (arr.length <= 1) return arr
let left = []
let right = []
// let pivot = arr[arr.length - 1]
// for (let i = 0; i < arr.length - 1; i++) {
// 改进,不要依赖最后一个值,注意 pivot 表示基准值,还需要提前算下 privotIndex
let pivotIndex = Math.floor(arr.length / 2)
// 这里切一个数出来。数据就会减少。否则像 [1, 1] 会无限循环下去
let pivot = arr.splice(pivotIndex, 1)[0] // splice 返回的是数组
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return [...quickSort(left), pivot, ...quickSort(right)]
}
const arr = [85, 24, 63, 45, 17, 31, 96, 50]
console.log(quickSort(arr))
插入排序
描述:
- 往前数牌,不断比较移动元素,找到最终插入位置时插入
- 下一个数
js
// 将值在数组前插入
// 移除某个位置的值
function insertionSort(arr) {
for (let i = 0; i < arr.length; i++){
let j = i
let cur = arr[i]
while(j > 0 && arr[j - 1] > cur) {
arr[j] = arr[j - 1]
j--
}
arr[j] = cur
}
return arr
}
let result = insertionSort([3, 5, 2, 11, 1, 2, 'abc', 'zfd', 'sad', 'eng'])
console.log(result)
快速选择
分区函数,返回 index
发现小于 k element,与当前区间交换
快速选择一般是以原地算法的方式实现,除了选出第k小的元素,数据也得到了部分地排序。
i 1 3 5 9 4 6
t 5
i j // 1 3 4 9 5 6
Quick Sort and Quick Select - YouTubehttps://leetcode.cn/problems/kth-largest-element-in-an-array/solution/javascriptsi-chong-fang-shi-jie-topkwen-ti-by-user/
归并排序
text
递推公式:
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
终止条件:
p >= r 不用再继续分解
- 分组
- 合并:如何合并两个有序数组(leetcode 88 是要求原地修改)
js
function merge(left, right){
const result = [];
while(left.length > 0 && right.length > 0){
if (left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return result.concat(left, right);
}
function mergeSort(arr){
if(arr.length <=1) return arr;
var middle = Math.floor(arr.length / 2);
var left = arr.slice(0, middle);
var right = arr.slice(middle);
let ret = merge(mergeSort(left), mergeSort(right));
console.log(ret)
return ret
}
let arr = [32, 12, 56, 78, 76, 45, 36]
let d = mergeSort(arr)
console.log(d)