前言

本文将带大家实现下一些经典的排序算法，附上图文加以解析，在这里图示用到了visualgo.net/en 这个网站实现可视化。

冒泡排序

• 思路： 从左往右，相邻元素之间比较，如果当前元素大就交换位置，重复此操作直到比较最后一个元素，下一轮重复以上操作。这里由于每一轮比较后都会确认最大值在后面，所以进一步优化，每轮比较次数可以是总长度减去已经排好序的个数。

• 图示：

• 代码：

function bubbleSort(arr){
  const len=arr.length
  for(let i=0;i<len;i++){//要比较的次数
    let flag=false //flag标记本轮比较中是否有交换位置的，如果没有则代表已经排好序了
    for(let j=0;j<len-i;j++){
      if(arr[j]>arr[j+1]){
        [arr[j],arr[j+1]]=[arr[j+1],arr[j]]
        flag=true
      }
    }
    if(flag==false) return arr
  }
  return arr
}

let arr=[3,44,38,5,47,15,36,26,27,2]
console.log(bubbleSort(arr));

• 复杂度：

  1.时间复杂度(平均情况)：O(n^2)

  2.空间复杂度：O(1)

选择排序

• 思路： 遍历数组，设置最小值索引为0，如果取出的值比当前最小值小，就替换最小索引，本轮遍历完后将第一个元素和最小索引对应的值替换，此时第一个元素就是数组最小值。如此重复，找到最小的放到未排序序列的开始位置。
• 图示：

• 代码：

function selectSort(arr) {
  let len=arr.length,index=0
  for(let i=0;i<len-1;i++) {
    index=i
    for(let j=i+1;j<len;j++) {
      if(arr[j]<arr[index]){
        index=j
      }
    }
    if(index!==i) 
      [arr[i],arr[index]]=[arr[index],arr[i]]
  }
  return arr
}

let arr=[3,44,38,5,47,15,36,26,27,2]
console.log(selectSort(arr));

• 复杂度：

  1.时间复杂度(平均情况)：O(n^2)

  2.空间复杂度：O(1)

插入排序

• 思路： 将初始数据分为有序部分和无序部分，每一步从未排序部分取一个数插入到前面已经排好序的序列中，直到插完所有元素为止。
• 图示：

• 代码：

function insertSort(arr){
  let len=arr.length
  for(let i=1; i<len;i++){
    let j=i,temp=arr[i]
    while(j>0&&arr[j-1]>temp){
      arr[j]=arr[j-1]
      j--
    }
    arr[j]=temp
  }
  return arr
}

let arr=[3,44,38,5,47,15,36,26,27,2]
console.log(insertSort(arr));

• 复杂度：

  1.时间复杂度(平均情况)：O(n^2)

  2.空间复杂度：O(1)

归并排序

• 思路： 将两个或两个以上的有序表组合成一个新的有序表。假设有n个记录，视为n个有序的子表，每个子表的长度为1，然后两两合并，合并后继续两两合并，如此往复，直到合并成一个长度为n的有序表。

分：

合：

• 图示：

• 代码：

function mergeSort(arr){
  const len=arr.length
  if(len<=1)  return arr

  const mid=Math.floor(len/2)

  const leftArr=mergeSort(arr.slice(0, mid))
  const rightArr=mergeSort(arr.slice(mid,len))

  //合并子数组 leftArr rightArr
  arr=mergeArr(leftArr,rightArr)
  return arr
}

function mergeArr(arr1,arr2) {//合并两个有序数组
  let i=0,j=0
  const res=[]

  while(i<arr1.length && j<arr2.length){
    if(arr1[i]<=arr2[j]){
      res.push(arr1[i]);
      i++
    }else{
      res.push(arr2[j])
      j++
    }
  }

  if(i<arr1.length){
   return res.concat(arr1.slice(i))
  }else{
    return res.concat(arr2.slice(j))
  }
}

let arr=[3,44,38,5,47,15,36,26,27]
console.log(mergeSort(arr));

• 复杂度：

  1.时间复杂度(平均情况)：O(nlogn) (底数为2，显示不出来就省略了)

  2.空间复杂度：O(n)

快速排序

• 思路： 随机选取数组中的一个值作为基准值，从左往右取值与基准值对比大小，比基准值小的放数组左边，大的放右边，对比完后将基准值和第一个的值交换位置，然后将数组以基准值的位置分为两部分，继续递归以上操作。
• 图示：

• 代码：

function quickSort(arr,left,right){
  if(left<right){
    let mid=part(arr,left,right)
    quickSort(arr,left,mid-1)
    quickSort(arr,mid+1,right)
  }
}

function part(arr,left,right){
  let m=arr[left]
  while(left<right){
   while(left<right&& arr[right]>=m) --right
   arr[left]=arr[right]
   while(left<right&& arr[left]<=m) ++left
   arr[right]=arr[left]
  }
  arr[left]=m
  return left
}

let arr=[3,44,38,5,47,15,36,26,27]
quickSort(arr,0,arr.length-1)
console.log(arr);

• 复杂度：

  1.时间复杂度(平均情况)：O(nlogn) (底数为2，显示不出来就省略了)

  2.空间复杂度：O(logn) (底数为2)

计数排序

• 思路： 开辟连续的大小为最大值和最小值之间的插值的空间给数据进行存储，将数组中的每个数减去最小值就是数组的下标值，将这个数组中对应下标的值+1，遍历完整个数组，重复以上操作，最后再依次按对应次数输出。

• 图示：

• 代码：

function countSort(arr){
  let max=arr[0],min=arr[0]
  let len=arr.length
  let res=[]

  //求最大值和最小值
  arr.forEach(item=>{
    max=item>max?item:max
    min=item>min?min:item
  })

  //存放记录每个数出现的频率
  let newArr=new Array(max-min+1).fill(0)

  //计数
  for(let i=0;i<len;i++){
    newArr[arr[i]-min]++
  }

  //遍历输出
  for(let i=0,index=0;i<newArr.length;i++){
    let count=newArr[i]
    while(count--){
      res[index++]=i+min
    }
  }

  return res

}

let arr=[1,5,6,1,4,7,9,6,8,5,3]
console.log(countSort(arr));

• 复杂度：

  1.时间复杂度(平均情况)：O(n+k)

  2.空间复杂度：O(n+k)

结束语

本篇文章就到此为止啦，由于本人经验水平有限，难免会有纰漏，对此欢迎指正。如觉得本文对你有帮助的话，欢迎点赞收藏❤❤❤。要是您觉得有更好的方法，欢迎评论，提出建议！