此处代码表示将数组里的两项元素进行置换
function swap(arr, i, j) { let temp = arr[j] arr[i] = arr[j] arr[j] = temp}
复制代码
冒泡排序
1.概念
比较相邻两元素。如果前一个比后一个大，则互换
对每一对相邻元素做同样的操作，从开始第一对到结尾的最后一对。这一步做完后，最后的元素会是最大的值。
针对所有元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
对于 n 个数的排序，需要经过 n-1 趟的比较
2.最快的时候
当输入的数据已经是正序时(已经是正序了)
3.最慢的时候
当输入的数据是反序时(可以写一个反输出的循环， 估不需要冒泡)
4.代码
function bubbleSort(arr) { let len = arr.length - 1 for (let i = 0; i < len; i++) { for (let j = 0; j < len - i; j++) { if (arr[j] > arr[j + 1]) { swap(arr, j, j + 1) } } }}
复制代码
冒泡排序改良版：
如果在一趟排序中，1 次交换都没有进行，则数据已经有序了，结束排序
改进思想： 只需要在原来的基础上，增加一个标志变量，判断某一趟排序是否有交换进行
function bubbleSort(arr) { // 如果数组为空 或者 数组只有一个元素， 则无需排队 if (arr == null || arr.length < 2) return const len = arr.length - 1 for (let i = 0; i < len; i++) { let flag = false // 是否有交换 for (let j = 0; j < len - i; j++) { if (arr[j] > arr[j + 1]) { flag = true // 经过了交换 swap(arr, j, j + 1) } } if (!flag) return // 如果一趟排序中，1次交换都没有，则数据已经有序，结束排序 }}
复制代码
选择排序
1.概念
首先在未排序序列中找到最小(最大)的元素，存放在排序序列的起始位置
再从剩余未排序元素中继续寻找最小(最大)元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完成
选择排序是不稳定的算法
2.代码
function selectionSort(arr) { let minIndex = 0 let len = arr.length for (let i = 0; i < len - 1; i++) { minIndex = i for (let j = 0; j < len; j++) { if (arr[minIndex] > arr[j]) { minIndex = j } } swap(arr, i, minIndex) } return arr}
复制代码
插入排序
评论