撩一下数组的几种排序算法

关于数组的排序算法，之前也看了很多次，感觉每次都记住了，但过段时间再去想，脑子里还是一片空白。还是要沉下心来学习一下，改掉自己眼高手低的毛病，代码这东西，眼睛看的都是别人的，用手敲下来的才是自己的。为了增强记忆，再配上对应的动态效果图。话不多说，开干！！！

冒泡排序

冒泡排序是一种简单的排序，它的实现就是重复走访问要排序的序列，依次比较两个相邻的元素，并排序。直到找不到可交换的元素为止，则完成了排序。这个算法的名字的由来就是越小的元素会经过交换慢慢“浮”到序列的顶端

算法描述

• 循环比较相邻的元素，如果前一个比后一个大，就交换它们的位置
• 对每一对相邻元素做同样的工作，从第一对开始到最后一对结束，这样最后的元素就是最大的
• 然后就是针对剩余所有的元素重复以上的步骤
• 重复1-3，直到排序完成

动图演示

代码实现

function bubbleSort(arr){
  let len = arr.length - 1;
  for(let i = 0; i < len; i++){
    for(let j = 0; j < len - i;j++){
      if(arr[j] > arr[j + 1]){
        let temp = arr[j + 1]
        arr[j + 1] = arr[j]
        arr[j] = temp
      }
    }
  }
}

选择排序

选择排序是一种简单直观的排序算法。原理就是先找到最小的元素，然后放到序列的第一位，然后再在剩余的元素中找到最小的元素，放到已排序的序列的末尾，以此类推，直到所有元素排序完成。

算法描述

• 设序列的长度为n，选择未排序序列的第一个元素，此时已排序序列为空
• 开始循环，拿取到的第一个元素和剩余的元素依次比较，遇到比选择的比较元素小的元素，则将目标元素替换为较小的元素。直到这次循环结束，则找到的就是下一个排序的元素。此时对已排序序列更新即交换序列中两个元素的位置
• 重复循环n - 1次，序列排序完成

动图演示

代码实现

function selectSort(arr){
  let len = arr.length
  for(let i = 0; i< len; i++){
    let min = i // 定义一个初始值
    for(let j = i; j < len; j++){
      if(arr[j] < min){  // 在剩余元素中要到是否存在小于最小值的元素
        let temp = arr[j]
        arr[j] = min
        min = arr[j]
      }
    }
    arr[i] = min //  每次内层循环结束以后，把找到的最小值替换为当前的
  }
}

插入排序

插入排序是通过元素位移来排序。原理是把构建一个已排序的序列，然后取出尚未排序的元素和已排序的序列元素依次比较插入。

算法描述

一般都是把序列左侧的部分认为是已排序的，算法过程如下：

• 从第一个元素开始，该元素可以认为是已经排序的
• 取出下一个元素，在已排序的序列中从后往前查找
• 如果该元素大于新元素，则将该元素移到下一个位置
• 重复步骤3，直到找到已排序序列中小于或者等于新元素的位置
• 将新元素插入到该位置
• 重复步骤2-5.

动图演示

代码实现

function insertSort(arr){
  let len = arr.length
  for(let i = 1; i < len; i++){
    let preIndex = i - 1
    let cur = arr[i] 
    // 下一个大于当前，则交换位置
    while(preIndex >= 0 && arr[preIndex] > cur){
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = cur
  }
}

快速排序

快速排序是通过排序将待排序的部分以某个基准点分隔成独立的两个部分，这样其中一部分的元素肯定都小于另一部分的，则可分别对这两个部分继续上述排序，以达到整个序列有序。

算法描述

快速排序采用分治法来把序列分为两个子序列。具体算法描述如下：

• 从序列中挑出一个元素作为基准值
• 重新排序，所有比基准值小的放在基准值前面，比基准值大的放在基准值后面。在这个分区结束后，该基准值就处于序列的中间位置
• 递归的把小于基准值的元素和大于基准值的元素的子序列排序

动图演示

代码实现

function quickSort(arr, left, right){
  var len = arr.length,
      partitionIndex,
      left = typeof left != 'number':0:left,
      right = typeof left != 'number':left - 1:right;
  if(left < right){
    partitionIndex = partition(arr, left, right)
    quickSort(arr, left, partitionIndex - 1)
    quickSort(arr, partitionIndex + 1, right)
  }
}
function partition(arr, left, right){
	var pivot = left,
    	index = pivot + 1;
  for(var i = index; i <= right; i++){
    if(arr[i] < arr[pivot]){
      swap(arr, i, index)
      index++
    }
  }
  swap(arr, povit,, index - 1)
  return index - 1
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用，将已有序的子序列合并，得到完全有有序的序列，即先使每个子序列有序，再使子序列段间有序。完成排序

算法描述

• 先把序列等分为两个子序列
• 对每个子序列分别采用归并排序
• 将两个排序成功的子序列合并成最终的排序序列

动图演示

代码实现

function mergeSort(arr){
  let len = arr.length
  if(len < 2) return arr
  let mid = Math.floor(len/2)
  let left = arr.slice(0, mid)
  let right = arr.slice(mid)
  return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right){
  let result = []
  while(left.length > 0 && right.length > 0){
    if(left[0] <= right[0]){
      result.push(left.shift())
    }else{
      result.push(right.shift())
    }
  }
  while(left.length) result.push(left.shift())
  while(right.length) result.push(right.shift())

  return result
}

总结

通过对以上几种算法的整理复习。也再次重新认识了数组的这几种排序算法。与之前的一知半解相比，有了更清晰地认识。

知识就像摆在书架的书一样，如果不拿下来翻翻，你就只能看到书名，而不会知道书里到底写的是什么。

我们自身拥有的知识和技能都不是一次就学会的，都是在不断的反复练习中逐渐加深和熟悉。所以，经常把脑子里的东西拿出来翻翻还是很有必要的。

鉴于自身能力有限，以上内容，如有错误，欢迎指正.