1、冒泡排序
思路：（1）第一次找出最大的数放在最后一个位置, 需要两个数据项进行比较，是一个循环操作。（2） 第二次将第二大的数倒数第二个位置，也是两个数据项进行比较，只是不和最后一个数据项比较(少了一次)， 但是也是一个循环操作 。（3） 第三次...第四次...依次类推。（4） 其中规律就是一个循环中嵌套循环，并且被嵌套的循环次数越来越少的。
function maoSort(arr) {
var length = arr.length
for (var i = 1; i < length; i++) {
for (var j = 0; j < length - i; j++) {
if (arr[j] > arr[j+1]) {
var temp = arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
}
}
}
return arr
}
比较次数，
。
交换平均次数,
2、选择排序
改进了冒泡排序，（1）将交换次数由减少到了
。（2）比较次数扔是
。
思路：（1）选择第一个索引的位置，与后面元素依次比较，经过一轮的比较，记录最小的索引值，将最小的值与第一个位置交换。（2）第二轮会记录第二小的数，将第二小的值与第二个位置交换。第三轮会记录第三小的数，将第三小的值与第三个位置交换。。。依次类推。直到n-1轮。
function selectionSort(arr) {
var length = arr.length
for (var i = 0; i < length - 1; i++) { // 外层循环: 从0位置开始取出数据, 直到length-2位置
var min = i
for (var j = min + 1; j < length; j++) { // 内层循环: 从i+1位置开始, 和后面的内容比较
// .如果i位置的数据大于j位置的数据, 那么记录最小的位置
if (arr[i] > arr[j]) min = j
}
var temp = arr[i]
arr[i] = arr[min]
arr[min] = temp
}
return arr
}
3、插入排序
思路：（1）从第一个元素开始，该元素可被认为已经排好序。（2）取出下一个元素，在已经排序的元素序列中从后往前扫描，扫描时如果该元素大于已排序的元素，交换两者位置。（3）重复步骤2，直到该元素大于等于已排序的元素。（4）将该元素插入到该位置后，重复上述步骤来插入后续元素。
function insertionSort(arr) {
var length = arr.length
// 外层循环: 外层循环是从1位置开始, 依次遍历到最后
for (var i = 1; i < length; i++) {
// 记录选出的元素, 放在变量temp中
var temp = arr[i]
var j = i
//内层循环不确定循环的次数, 最好使用while循环
while (arr[j - 1] > temp && j > 0) {
arr[j] = arr[j - 1]
j--
}
// 将选出的j位置, 放入temp元素
arr[j] = temp
}
return arr
}
比较次数：第一趟最多1次，第二趟最多2次....第n趟最多N-1次，最多的比较次数：，平均比较次数
.
复制次数：第一趟最多1次，第二趟最多2次....第n趟最多N-1次，最多的比较次数：，平均复制次数
。
4、希尔排序
希尔排序建立在插入排序的基础上。
function shellSort(arr) {
var length = arr.length
var gap = length >> 1
// 增量不断变量小, 大于0就继续排序
while (gap >= 1) {
// 4.实现插入排序
for (var i = gap; i < length; i++) {
// 4.1.保存临时变量
var temp = arr[i]
var j = i
// 4.2.插入排序的内层循环
while (arr[j - gap] > temp && j > gap - 1) {
arr[j] = arr[j - gap]//复制.
j -= gap
}
// 4.3.将选出的j位置设置为temp
arr[j] = temp
}
gap = gap >> 1
}
}
希尔排序的平均时间复杂度为o(nlogn)。
5、快速排序
思路：分而治之。平均效率：o(nlogn)
function quickSort(arr){
if(arr.length === 0){
return []
}
let midIndex = arr.length >> 1
let mid = num.splice(midIndex, 1)
let left = []
let right = []
for(let i = 0; i < arr.length; i++){
if(num[i] < mid){
left.push(num[i])
}else{
right.push(num[i])
}
}
arr = quickSort(left).contact(mid, quickSort(right))
return arr
}
