排序算法

• 选择排序 O(n^2)

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法

代码实现

function selectSort(arr){
  if(arr.length<=1)return arr
  for(let i=0;i<arr.length;i++){
    let minIndex = i
    for(let k=i+1;k<arr.length;k++){
      if(arr[k]<arr[minIndex]){
        minIndex = k
      }
    }
    [arr[i],arr[minIndex]] = [arr[minIndex],arr[i]]
  }
  return arr
}
console.log(selectSort([3,1,5,2,7]))//[1, 2, 3, 5, 7]
console.log(selectSort([3]))//[3]

---

• 计数排序 O(n+max)

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 ^[1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）

代码实现

function countSort(arr){
   let length = arr.length
  if(length<=1)return arr
  let hashTable = {}
  let max = arr[0]
  for(let i=0;i<length;i++){
    let item = arr[i]
    hashTable[item] = !hashTable[item]?1:hashTable[item]+1
    if(item>max)max = item
  }
  const result = []
  for(let m=1;m<=max;m++){
    if(hashTable[m]){
      for(let k=0;k<hashTable[m];k++){
        result.push(m)
      }
    }
  }
  return result
}
console.log(countSort([3,5,6,2,9,1]))
console.log(countSort([1,2,3,1]))

---

• 冒泡排序 O(n^2)

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

代码实例

function bubbleSort(arr){
   const {length} = arr
   for(let i=0;i<length-1;i++){
     for(let j=0;j<length-i-1;j++){
       if(arr[j]>arr[j+1]){
         [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
       }
     }
   }
  return arr
}
console.log(bubbleSort([3,5,6,2,9,1]))
console.log(bubbleSort([1,2,3,1]))

---

• 插入排序 O(n^2)

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 ^[1] 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 ^[2] 。

代码实现

function insertSort(arr){
  const {length} = arr
  if(length<=1)return arr
  for(let i=1;i<length;i++){
    let now = arr[i]
    let s
    for(s=i-1;s>=0;s--){
      if(now<arr[s]){
        arr[s+1] = arr[s]
      }else {
        break
      }
    }
    arr[s+1] = now
  }
  return arr
}
console.log(insertSort([3,5,6,2,9,1]))
console.log(insertSort([1,2,3,1]))
console.log(insertSort([3,1]))

---

• 希尔排序

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
代码实现

function shellSort(arr) {
    var len = arr.length;
    for(var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
        for(var i = gap; i < len; i++) {
            var j = i;
            var current = arr[i];
            while(j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}
let s = shellSort([1,5,7,2,4,3])
console.log(s)

---

• 二分查找 O(log2n)

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

代码实现

var Arr = [3, 5, 6, 7, 9, 12, 15];
function binary(find, arr, low, high) {
    if (low <= high) {
        if (arr[low] == find) {
            return low;
        }
        if (arr[high] == find) {
            return high;
        }
        var mid = Math.ceil((high + low) / 2);
        if (arr[mid] == find) {
            return mid;
        } else if (arr[mid] > find) {
            return binary(find, arr, low, mid - 1);
        } else {
            return binary(find, arr, mid + 1, high);
        }
    }
    return -1;
}
binary(15, Arr, 0, Arr.length - 1);

function bSearch(arr, n, start, end){
  if(end === start) return -1
  let mid = parseInt((start + end) / 2) 
  if(n === arr[mid]){
    return mid
  }else if(n > arr[mid]){
    return bSearch(arr,n,mid+1,end)
  }else {
    return bSearch(arr,n,start,mid)
  }
}
console.log(bSearch([2,2,2,4,5,6,8],7,0,7))