冒泡排序
思路
需要遍历 length - 1 次
每一次遍历
都从后往前进行比较，
相邻的两两比较大小，小的向前浮动
时间复杂度 O(n2)
function bubbleSort(target) {
let temp = null
for(let i = 0; i < target.length - 1; i++) {
for(let j = target.length - 1; j > i; j--) {
if (target[j] < target[j - 1]) {
temp = target[j]
target[j] = target[j - 1]
target[j - 1] = temp
}
}
console.log(`第 ${i + 1} 次排序`)
}
return target
}
console.log(bubbleSort([23, 32, 5, 72, 12, 1]))
运行结果
缺点：
当目标对象是已经排序好的数据
也需要进行多次遍历
console.log(bubbleSort([1, 2, 3, 4, 5, 6]))
运行结果
优化
定义一个布尔值
在遍历每一次的时候，如果发生位置交换，就改变布尔值
当这一次循环结束之后，判断该布尔值是否变化
变化了则继续下一次，没变则退出
function bubbleSort(target) {
let temp = null
let flag = false
for(let i = 0; i < target.length - 1; i++) {
for(let j = target.length - 1; j > i; j--) {
if (target[j] < target[j - 1]) {
temp = target[j]
target[j] = target[j - 1]
target[j - 1] = temp
flag = true
}
}
console.log(`第 ${i + 1} 次排序`)
if (!flag) break
}
return target
}
console.log(bubbleSort([1, 2, 3, 4, 5, 6]))
运行结果
选择排序
遍历 length - 1 次
从左到右开始找，每遍历一次将最小值跟当前遍历的第一个元素交换
时间复杂度 O(n2)
function selctionSort(target) {
for (let i = 0; i < target.length - 1; i++) {
let min = target[i]
let minIndex = i
for (let j = i + 1; j < target.length; j++) {
if (target[j] < min) {
min = target[j]
minIndex = j
}
}
console.log(`第${i + 1}次循环`, target)
// 减少循环次数
if (minIndex === i) break
target[minIndex] = target[i]
target[i] = min
}
return target
}
console.log(selctionSort([23, 32, 5, 72, 12, 1]))
console.log(selctionSort([1, 2, 3, 4, 5, 6]))
运行结果
插入排序
遍历 length - 1 次
从 i + 1 项开始往前遍历，两两比较小的往前移动，
时间复杂度 O(n2)
function insertionSort(target) {
let temp
for (let i = 0; i < target.length - 1; i++) {
for (let j = i + 1; j > 0; j--) {
if (target[j] < target[j - 1]) {
temp = target[j - 1]
target[j - 1] = target[j]
target[j] = temp
} else {
// 当不小于已排序好的最大值时
// 退出每次遍历，进行下一次
break
}
}
console.log(`第${i + 1}次循环`, target)
}
return target
}
console.log(insertionSort([23, 32, 5, 72, 12, 1]))
运行结果
快速排序
/**
参数说明
target 需要排序的目标数组
l 需要排序的起始项
r 需要排序的终止项
*/
function quickSort(target, l, r) {
if (l >= r) return
let i = l; let j = r; let key = target[l];//选择第一个数为key
while (i < j) {
while (i < j && target[j] >= key)//从右向左找第一个小于key的值
j--;
if (i < j) {
target[i] = target[j];
i++;
}
while (i < j && target[i] < key)//从左向右找第一个大于key的值
i++;
if (i < j) {
target[j] = target[i];
j--;
}
}
//i == j
target[i] = key;
quickSort(target, l, i - 1);//递归调用
quickSort(target, i + 1, r);//递归调用
return target
}
console.log(quickSort([23, 32, 5, 72, 12, 1, 2], 0, 5))
console.log(quickSort([23, 32, 5, 72, 12, 1], 4, 5))
运行结果
【笔记不易，如对您有帮助，请点赞，谢谢】
