冒泡和选择排序在平时自己做项目的时候还是很常见的，这里记录下原理和手写的实现，方便日后查阅，排序动态图来自菜鸟教程，上面还有更多排序算法，有需要的可以查阅。
冒泡排序 Bubble Sort
冒泡排序还是一个比较直观的排序算法，不断比较，把小的数放在前面，越小的元素会经由交换慢慢“浮”到数列的顶端，就像水里的泡泡最终会浮到水面上一样，所以叫冒泡排序
最主要的原理就是依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。
动态图来自菜鸟教程
冒泡排序
用JavaScript来实现其实就是2个for循环嵌套
// 冒泡排序
function bubbleSort(arr) {
// 保存传入的数组长度
let len = arr.length;
// 进行嵌套for循环
for (let i = 0; i < len - 1; i++) {
// 第一层执行length-1次，就是从数组的第一位到最后一位
for (let j = 0; j < len - 1 - i; j++) {
// 这里是循环从头循环到排好顺序的数据
if (arr[j] > arr[j+1]) {
// 如果后面的数更小，就保存后面的数字
let temp = arr[j+1];
// 元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
例如现在有个数组let arr1 = [50,3,23,2,45,7]，他的冒泡排列执行顺序如下
- i=0，最外层for循环循环5次，j=0，第二层for循环5次
根据程序是拿50和后面的数据排序，最后能得到[3,23,2,45,7,50]这样一个数组，之后i++ - 此时 i=1，最外层还需循环4次，j还是等于0，但是j所在的循环此时执行4次
根据程序是拿3和[23,2,45,7]来排序，最后可得到[3,2,23,7,45,50]这样的数组，最大的两个数已经确定了，之后i++ - 此时 i=2，最外层还需3次，j循环此时还需3次
相当于拿3和[2,23,7]比较，可以得到[2,3,7,23,45,50]数组，此时i++，我们这边看到当前数组已经排序好了，但是程序没有，还需之后该的2次循环，程序才会结束返回结果
由此可见：N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数。
所以冒泡排序总的平均时间复杂度为：O(n²)
选择排序
选择排序十分直观，直接选择第一个数据，逐个比较，把最小的数据放到第一位，然后再从剩余的未排序元素中寻找到最小元素，放到第二位，以此类推，直到全部待排序的数据元素的个数为零。
演示动态图来自菜鸟教程
选择排序
// 选择排序
function selectionSort(arr) {
// 保存传入数组的长度
let len = arr.length;
// 定义2个参数 minIndex用于保存最小数的index，temp用于交换数据
let minIndex, temp;
// 开始执行循环，循环次数为数组长度 - 1
for (let i = 0; i < len - 1; i++) {
// 假定当前i是最小数的index
minIndex = i;
// 从当前i之后开始循环，比较每一个数
for (let j = i + 1; j < len; j++) {
// 每当当前数小于最小数的时候
if (arr[j] < arr[minIndex]) {
// 将最小数的索引保存
minIndex = j;
}
}
// 交换数据
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
假设有这个数组let arr2 = [50,3,23,2,45,7,1,999,100,200]，那么需要循环9次，每次交换后的结果如下图
选择排序
看每次交换后的输出还是很好理解的，就是顺序取数，然后比较，和剩余数据中最小的数字交换即可。所以无论什么数据传入都要判断一次，时间复杂度都是O(n²)，因此不太适合太大的数据。
不难看出，两个循环都使用双层for循环数组，并且最外层循环的次数都相同，本质上的区别是，两者找到最大（最小）数的方法不同，冒泡是不断交换找到，选择是找到序号之后再交换。
