参考：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
参考：https://www.jianshu.com/p/f1f2dc978762
冒泡排序
冒泡排序的思路:
- 对未排序的各元素从头到尾依次比较相邻的两个元素大小关系
- 如果左边的队员高, 则两队员交换位置
- 向右移动一个位置, 比较下面两个队员
- 当走到最右端时, 最高的队员一定被放在了最右边
- 按照这个思路, 从最左端重新开始, 这次走到倒数第二个位置的队员即可.
- 依次类推, 就可以将数据排序完成
程序
function bubbleSort(arr) {
let len = arr.length
for(let i=0;i<len;i++){ //
let count = 0 // 标志位
for(let j=1;j< len-i;j++){
if(arr[j] > arr[j-1]) {
// 换位置操作 把大的放到前面，小的放在后面
let temp = arr[j]
arr[j] = arr[j-1]
arr[j-1] = temp
count = 1 // 执行了换位置操作则置1
}
}
if(count === 0){ // 表示内层循环没有执行换位置操作，即表明已排好序
return arr
}
}
}
bubbleSort([2,7,16,-3,32,9,0,0,1,7]) // [32, 16, 9, 7, 7, 2, 1, 0, 0, -3]
参考：https://www.runoob.com/w3cnote/bubble-sort.html
选择排序
选择排序的思路
- 选定第一个索引位置，然后和后面元素依次比较
- 如果后面的队员, 小于第一个索引位置的队员, 则交换位置
- 经过一轮的比较后, 可以确定第一个位置是最小的
- 然后使用同样的方法把剩下的元素逐个比较即可
- 可以看出选择排序，第一轮会选出最小值，第二轮会选出第二小的值，直到最后
程序
function selectionSort(arr) {
let len = arr.length
for(let i = 0;i < len-1;i++){
for(let j = i+1;j < len;j++){
if(arr[i] < arr[j]){
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
}
return arr
}
selectionSort([2,4,5,3,1,12,3,-1,0,0,2,7]) // [12, 7, 5, 4, 3, 3, 2, 2, 1, 0, 0, -1]
参考：https://www.runoob.com/w3cnote/selection-sort.html
插入排序
插入排序的思路
- 局部有序:
- 插入排序思想的核心是局部有序. 什么是局部有序呢?
- 比如在一个队列中的人, 我们选择其中一个作为标记的队员. 这个被标记的队员左边的所有队员已经是局部有序的.
- 这意味着, 有一部门人是按顺序排列好的. 有一部分还没有顺序.
- 插入排序的思路:
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复上一个步骤，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后, 重复上面的步骤.
程序
function insertSort(arr){
let len = arr.length
let localIndex; //定义局部有序 的最后一个index
for(let i = 1;i < len;i++){
localIndex = i - 1
current = arr[i]
while(localIndex >=0 && arr[localIndex] > current){
arr[localIndex+1] = arr[localIndex]
localIndex--
}
arr[localIndex+1] = current
}
return arr
}
insertSort([2,4,5,3,1,12,3,-1,0,0,2,7]) // [-1, 0, 0, 1, 2, 2, 3, 3, 4, 5, 7, 12]
