四种排序

选择排序 快速排序 归并排序 计数排序

选择排序(循环)

思路:每次查找最小值,拿最小值的索引下标跟数组升序下标逐步交换.

//交换
let swap = (array,i,j) =>{
  let temp = array[i];
  array[i]=array[j];
  array[j]=temp;
}

//寻找最小值索引
let minIndex = (numbers) =>{
  let index = 0;
  for(let i=1;i<numbers.length;i++){
      if(numbers[i]<numbers[index]){
        index = i;
      }
  }
  return index;
}

//选择排序(从小到大)
let sort = (numbers) =>{
  for(let i=0;i<numbers.length-1;i++){
    let index = minIndex(numbers.slice(i))+i
    if(index!==i){
      swap(numbers,index,i)
    }
  }
  return numbers;
}


//slice()：方法是 Array.prototype.slice();返回一个新对象,
//这一对象是由一个begin和end决定的原数组的浅拷贝(包含begin,不包含end)。原始数组不会被改变

快速排序(quick sort)(递归)

let quickSort =  arr =>{
  if(arr.length <= 1){return arr}
  let pivotIndex = Math.floor(arr.length/2);
  let pivot = arr.splice(pivotIndex,1)[0];  //取[0]的值
  let left = [];
  let right = [];
  for(let i = 0;i<arr.length;i++){
    if(arr[i]>pivot){
      right.push(arr[i]);
    }else{
      left.push(arr[i]);
    }
  }

  return quickSort(left).concat([pivot],quickSort(right));
}

//Math.floor()方法 : 向下取整
//Array.prototype.splice()方法 : 删除或替换现有元素或者原地添加元素来修改数组,并以数组形式返回被修改的内容.此方法会改变原数组
//Array.prototype.push()方法 ：将一个或多个元素数组的末尾,并返回数组的新长度
//Array.prototype.concat()方法 : 用于合并两个或多个数组.此方法不会更改现有数组,而是返回一个新数组

归并排序(merge sort)

//一个数组拆分两个数组(拆成数组只有一个元素为止)
let mergeSort = arr =>{
  let k = arr.length;
  if(k===1||k===0){return arr}
  let left = arr.slice(0,Math.floor(k/2))
  let right = arr.slice(Math.floor(k/2))
  return merge(mergeSort(left),mergeSort(right))
}
//两个数组排序从小到大成一个数组
let merge = (a, b) =>{
  if(a.length === 0){return b}
  if(b.length === 0){return a}
  return a[0] > b[0] ?
      [b[0]].concat(merge(a,b.slice(1))) :
      [a[0]].concat(merge(a.slice(1),b))
}

//Array.prototype.slice()方法: 返回一个新的数组对象,这一对象是一个由begin和end决定的原数组的浅拷贝(包含begin,不包含end).原数组不会被改变

计数排序(count sort)

let countSort = arr =>{
  let hashTable = {},max = 0,result = [];
  //遍历数组
  for(let i =0;i<arr.length;i++){
    if(!(arr[i] in hashTable)){
      hashTable[arr[i]] = 1
    }else{
      hashTable[arr[i]] += 1
    }
    if(arr[i]>max){max = arr[i]}
  }
  console.dir(hashTable)
  //遍历哈希表
  for(let j=0; j<=max; j++){
      if(j in hashTable){
        for(let i =0;i<hashTable[j];i++){
          result.push(j)
        }
      }
  }
  return result
}

// in 运算符：如果指定的属性在指定的对象或原型链中,则in运算符返回true
//Array.prototype.push() : 方法将一个或多个添加到数组的末尾,并返回该数组的新长度