阅读 33

排序算法编程实现(JS)

目录

  • 快速排序
  • 归并排序
  • 计数排序
  • 选择排序
  • 冒泡排序
  • 插入排序

快速排序

时间复杂度与空间复杂度

代码

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 =[],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))   //递归,返回最终数组
}
quickSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])
//[3, 44, 38, 5, 47, 15, 36, 27, 2, 46, 4, 19, 50, 48]
复制代码

动图演示

快速排序动图.gif

归并排序

时间复杂度与空间复杂度

代码

let mergeSort = (arr) => {
    if(arr.length <= 1){return arr}
    let left = arr.slice(0,Math.floor(arr.length /2))   //把数组分为两半
    let right = arr.slice(Math.floor(arr.length /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))
}
mergeSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
复制代码

动画演示

归并排序动图.gif

计数排序

时间复杂度与空间复杂度

代码

var 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 i = 0; i < hashTable[j]; i++){   //value为几就push几次
                result.push(j)
            }
        }
    }
    return result
}
countSort([2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2])
//[1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]
复制代码

动画演示

计数排序动图.gif

选择排序

时间复杂度与空间复杂度

代码

  • 循环实现
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 selectSort = (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
}
selectSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])
//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
复制代码
  • 递归实现
let min = (numbers) => {   //求多个数中的最小值
  if(numbers.length > 2){
    return min(
      [numbers[0], min(numbers.slice(1))]
    )
  }else{
    return Math.min.apply(null, numbers)
  }
}

let minIndex = (numbers) => {    //求数组中最小数的下标
  let index = 0
  for(let i=1; i<numbers.length; i++){
    if(numbers[i] < numbers[index]){
      index = i
    }
  }
  return index
}

let selectSort = (numbers) => {
  if(numbers.length > 2){
    let index = minIndex(numbers)
    let min = numbers[index]
    numbers.splice(index, 1)
    return [min].concat(selectSort(numbers))
  }else{
    return numbers[0]<numbers[1] ? numbers :
    numbers.reverse()
  }
}
selectSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])
//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
复制代码

动画演示

选择排序动图.gif

冒泡排序

时间复杂度与空间复杂度

代码

let bubbleSort =(arr) => {
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                let temp = arr[j+1];        //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}
bubbleSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])
//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
复制代码

动画演示

冒泡排序动图.gif

插入排序

时间复杂度与空间复杂度

代码

var insertionSort = arr => {
    for (var i = 1; i < arr.length; i++) {
        var key = arr[i];
        var j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr
}
insertionSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])
//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
复制代码

动画演示

插入排序动图.gif