排序算法
冒泡排序
原理
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
演示图
代码实现
function bubbleSort(arr) {
let len = arr.length;
// 外层循环控制排序趟数
for (let i = 0; i < len; i++) {
// 内层循环控制每一趟排序多少次
for (let j = 0; j < len - 1 - i; j++) {
// 升序排列
if (arr[j] > arr[j + 1]) {
// 交换位置
// 使用解构赋值
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
性能分析
时间复杂度：O(n^2)
空间复杂度：O(1)
最好情况：输入数据已经是正序
最坏情况：输入数据是反序
选择排序
原理
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
演示图
代码实现
function selectionSort(arr) {
let len = arr.length;
let minIndex;
for (let i = 0; i < len - 1; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
// 将最小数的索引保存
minIndex = j;
}
}
// 使用解构赋值
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
性能分析
时间复杂度：O(n^2)
空间复杂度：O(1)
插入排序
原理
- 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
演示图
