js 常见排序算法（快速排序，选择排序等）

快速排序法

let partition = function(array, left, right) {
    let pivot = array[Math.floor((right + left) / 2)],  // 找出需要排序的数组中间基准值
    i = left,
    j = right;
  while (i <= j) {
     // 从左边开始遍历，如果值小于基准值, 继续往下遍历 i++，  
如果大于或者等于基准值，就停止，取该值下标i
    while (array[i] < pivot) {     
      i++;
    }
     // 从右边开始遍历，如果值大于基准值, 继续往下遍历 j--，  
如果小于或者等于基准值，就停止，取该值下标j
    while (array[j] > pivot) {       
      j--;
    }
    if (i <= j) {
    // 如果上面遍历两个数值下标 i<=j 时候，交换这两个数字，然后i，j各加一，
继续执行外层循环，直到，i> j 时候，这时候基准值左边都是比基准值小的数，
基准值右边都是比基准值大的数字
      swap(array, i, j);     
      i++;
      j--;
    }
  }
  return i;
};
let swap = function(array, index1, index2){
    var aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
};
let quick = function(array, left, right){
  var index;
  if (array.length > 1) {
    index = partition(array, left, right);
     // 将上一遍遍历基准值左边和右边按照上述规则，分别排序
    if (left < index - 1) {                     
      quick(array, left, index - 1);
    }
    if (index + 1 < right) {
      quick(array, index, right);
    }
  }
  return array;
};
var myArray = [12,34,45,3,67,76,33,5,87,10,11];
quick(myArray, 0, myArray.length-1)

选择排序

function selectSort(arr){
    let len=arr.length,minIndex,temp;
    // 第一层for循环，默认先把循环到的当前元素，作为最小值
    for(var i=0;i<len-1;i++){
      minIndex=i;
      // 第二层for循环，找出第一层for循环当前元素之后所有元素中最小的一个，与其交换
      for( var j=i+1;j<len;j++){
        if(arr[j]<arr[minIndex]){
          minIndex=j;
        }
      }
      temp=arr[i];
      arr[i]=arr[minIndex];
      arr[minIndex]=temp;
    }
    return arr;
  }
  var myArray = [12,34,45,3,67,76,33,5,87,10,11];
  selectSort(myArray)

插入排序

function insert_sort(arr) {
    var temp, length = arr.length, j;
    
    for(var i = 1; i< length; i++) {
      j = i;
      // 标记当前外层for循环到的元素
      temp = arr[i];   
      //  从外层标记的元素，while 循环往前查找，如果while循环的元素，比标记元素大，则将while 循环到的元素后移一位，当比标记元素小，或者等于标记元素时， 结束while 然后，将标记元素，填充到j-- 之后j 下标的位置。
      while (j> 0 && arr[j-1] > temp) {
        arr[j] = arr[j-1];
        j--;
      }
      arr[j] = temp;
    }
    return arr;
  }
var myArray = [12,34,45,3,67,76,33,5,87,10,11];
insert_sort(myArray);

冒泡排序

function bubbleSort(arr){
    var  i , j ,temp ,len = arr.length;
    // 外循环循arr 长度次数， 每次循环，执行内循环
    for(i = 0 ;i < len - 1; i++){
        // 每次内循环，比较左右两个数字，如果左边比右边大，则交换两个数字，内循环结束，数组最后一个为最大数，下一次循环，最后最大数不参与比较，所以要 arr.length - 1 -i , -i 就是为了不于最大数比较
        var bool = true; //  优化： 增加一个开关
        for(j= 0;j < len- 1 - i; j++){
            if(arr[j] > arr[j + 1]){
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
                bool = false;  // 有交换位置，说明，还没排好序
            }
        }
      // 如果循环为true，说明内层循环，没有再交换元素，说明排序完毕，跳出循环即可。
      if(bool){
          break;
      }
    }
    return arr;
}
var myArray= [12,34,45,3,67,76,33,5,87,10,11];
bubbleSort(myArray);