写写常见的排序算法吧

冒泡排序

思想:双层循环,i从第一个元素开始作为外层循环,j从i+1开始,内层循环,比较arr[i]和arr[j],进行交换将大的放到后边,小的放到前边
特点：排序算法的基础。简单实用易于理解，缺点是比较次数多，效率较低。

function sort(arr) {
    for (var i = 0; i < arr.length - 1; i++) {
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                var item = arr[i];
                arr[i] = arr[j];
                arr[j] = item;
            }
        }
    }
    return arr;
}
var arr = [8, 4, 5, 2, 0, 9, 1];
console.log(sort(arr));//[ 0, 1, 2, 4, 5, 8, 9 ]

选择排序

思想:每次从未排序的元素中找出最小的与最左端的元素交换

function selectSort(arr) {
    for (var i = 0; i < arr.length - 1; i++) {
        var min = i;
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
               min = j;
            }
        }
        var item = arr[i];
        arr[i] = arr[min];
        arr[min] = item;
        console.log(arr);
    }
    return arr;
}

var arr = [8, 4, 5, 2, 0, 9, 1];
console.log(selectSort(arr));//[ 0, 1, 2, 4, 5, 8, 9 ]

插入排序

思想:默认第一个元素已经有序,双层循环,外层从1到最后一个元素,内层从最前边排好序的末尾到第一个,依次比较,需要交换则进行交换

function insertSort(array){
  for(var i = 1;i<array.length;i++){
    for(var j = i;j>0;j--){
      if(array[j] < array[j-1]){
        var temp = array[j];
        array[j] = array[j-1];
        array[j-1] = temp;
      }
      else{
        break;
      }
    }
  }
  return array;
}

var arr = [3,2,8,5,6,0,7];
console.log(insertSort(arr));

快速排序

思想:找最中间的元素作为基准元素(也可以选择其他的),申请两个空数组,left,right,比基准小的放到left中,比基准大的放到right中,分别再去递归调用该函数将这两个数组传递过去,并且将左右,中间基准元素拼接起来,当传过去的参数小于等于一个元素时直接返回数组.

function quickSort(arr){
  if(arr.length <= 1){
    return arr;
  }
  var index = Math.floor(arr.length/2);
  var flag = arr.splice(index,1)[0];
  var left = [];
  var right = [];
  for( i = 0;i<arr.length;i++){
    if(arr[i] < flag){
      left.push(arr[i]);
    }
    else{
      right.push(arr[i]);
    }
  }
  
  return quickSort(left).concat([flag],quickSort(right));
}

console.log(quickSort([2,1,5,6,3,9,0]));