sort原理

sort()对数组进行排序，原数组改变

1. sort()方法没有参数时，按照ascii码对元素进行排序

let array = [12,45,34,78,21,10,3,6,27]
let newArray = array.sort()
console.log(array)
console.log(newArray)

sort()方法无参数时对数组的操作.PNG

2. sort()方法传入的参数返回一个负数，可实现数组的reverse()效果

let array = [12,45,34,78,21,10,3,6,27]
let newArray = array.sort((a,b) => {
  return -1
})
console.log(array)
console.log(newArray)

sort()方法实现reverse效果.PNG

3. sort()实现升序

let array = [12,45,34,78,21,10,3,6,27]
let newArray = array.sort((a,b) => {
  return a-b
})
console.log(newArray)

sort()方法实现升序.PNG

4. sort()方法实现降序

let array = [12,45,34,78,21,10,3,6,27]
let newArray = array.sort((a,b) => {
  return b-a
})
console.log(newArray)

sort()方法实现降序.PNG

关于a,b的取值

• a:array[1]---array[array.length-1]
• b:array[0]----array[array.length-2]

let array = [12,45,34,78,21,10,3,6,27]
array.sort((a,b) => {
  console.log("a:" +a)
  console.log("b:" +b)
})

a,b的取值.PNG

不同的浏览器对于sort排序的方法不一样，V8引擎，数组元素小于10，采用插入排序，数组元素大于10，采用快排。

插入排序

插入排序的复杂度是n^2，但是由于数据量很小，因此是常量的复杂度，效率很高，而且插入排序是一个稳定的排序算法。

• 代码

function insertSort(array){
  for(let i = 1; i< array.length; i++){
    let temp  = array[i];
    let j = i;
    for(;j >0; j--){
        if(temp>=array[j-1]){
          break;
        }
        array[j] = array[j-1]
    }
    console.log(j)
    array[j] = temp
    console.log(i + '----')
  }
  return array
}
let array = [1,4,2,7,3,9,5,0]
console.log(insertSort(array))

插入排序.PNG

快速排序

平均情况下快速排序的时间复杂度是Θ(nlgn)，最坏情况是n2，但通过随机算法可以避免最坏情况。由于递归调用，快排的空间复杂度是Θ(lgn)。

• 代码

function quickSort(arr){
  //对数组元素个数进行判断
  if(arr.length <= 1){return arr}
  //选取一个基数，并定义左右两个数组
  let povitIndex = Math.floor(arr.length / 2);
  let povit = arr.splice(povitIndex,1)[0]; //原数组改变
  let left = [];
  let right = [];
  //对数组进行遍历，小于基数放左边，其余放右边
  for(let i = 0; i< arr.length; i++){
    if(arr[i] < povit){
      left.push(arr[i])
    }else {
      right.push(arr[i])
    }
  }
  //递归调用
  return quickSort(left).concat([povit],quickSort(right))
}
let array = [23,56,12,65,38,0,9,7,25]
console.log(quickSort(array))

快速排序.PNG