常见排序算法

这里介绍四种排序算法，选择排序、快速排序、归并排序、计数排序

选择排序（使用递归）

// 选择排序 递归
let min = (arr) => {
  if(arr.length > 2){
    return min([arr[0], min(arr.slice(1))])
  }else{
    return Math.min.apply(null, arr)
  }
}
// console.log(min([3,5,9,6]))

let sort2 = ([a, b]) => a < b ? [a, b] : [b, a];
// console.log(sort2.call(null, [12, 3]))

// 最小值下标，有个bug，两个最小数相同，只显示第一个的下标
let minIndex = (nums) => {
  return nums.indexOf(min(nums))
}
// console.log(minIndex([10, 9, 12, 6,1, 2]))

let sort3 = (arr) => {
  let index = minIndex(arr);
  //let min = arr[index];//这行可以不要了
  let min = arr.splice(index, 1);//splice返回值就是截取元素组成的数组
  return min.concat(sort2(arr));
}
// console.log(sort3([4,1,3]))

let sort4 = (arr) => {
  let index = minIndex(arr);
  let min = arr.splice(index, 1);
  return min.concat(sort3(arr))
}
// console.log(sort4([10,9,11,8]))

let sort = (arr) => {
  if(arr.length > 2){
    let index = minIndex(arr);
    let min = arr.splice(index, 1);
    return min.concat(sort(arr));
  }else{
    return arr[0] < arr[1] ? arr : arr.reverse();
  }
}
console.log(sort([12,23,2,56,23,8]))

选择排序（使用循环）

// 选择排序 循环
let minIndex = (nums)=>{
  let index = 0;
  for(let i = 1; i < nums.length; i++){
    index = nums[index] > nums[i] ? i : index;
  }
  return index;
}

let swap = (arr, x, y) => {
  let temp = arr[x];
  arr[x] = arr[y];
  arr[y] = temp;
}

let sort = (nums)=>{
  for(let i = 0; i < nums.length-1; i++){
//     console.log(`第${i+1}轮----`);
    let index = minIndex(nums.slice(i)) + i; 
//     console.log(`index:${index}`);
//     console.log(`min:${nums[index]}`);
    if(index !== i){
      swap(nums, index, i);
//       console.log(`swap:${index}:${i}`);
//       console.log(nums)
    }
  }
  return nums
}

let arr = [10,50,40,20,30]
console.log(sort(arr))

快速排序（递归）

//  快速排序

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

let arr = [24,12,36,6,18,4,2]
console.log(quickSort(arr))

归并排序（递归）

// 归并排序
let mergeSort = arr => {
  let k = arr.length
  if(k <= 1) 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] ? 
    [a[0]].concat(merge(a.slice(1), b)) :
    [b[0]].concat(merge(a, b.slice(1)))
}

let arr = [24,12,36,6,18,4,2]
console.log(mergeSort(arr))

计数排序

// 计数排序
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]}
  }
  for(let j = 0; j <= max; j++){
    if(j in hashTable){
      for(let k = 0; k < hashTable[j]; k++){
        result.push(j)
      }
    }
  }
  return arr
}

let arr = [12,25,41,25,16,98, 63]
console.log(countSort(arr))