十大经典排序算法笔记

相关概念

稳定性

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

时间复杂度

• 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

最坏时间复杂度

• 最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

平均时间复杂度

• 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。设每种情况的出现的概率为pi,平均时间复杂度则为sum(pi*f(n))
  和平均时间复杂度

空间复杂度

• 一个程序的空间复杂度是指运行完一个程序所需内存的大小。

注意

• 基于比较的排序算法时间复杂度最快为O(nlogn)
• 部分情况下，O(n²) 也会比O(nlogn)快（数据长度较小时），一般的用于算法时，数据量都可以超过临界点，所以一般关注算法复杂度级别
• 非线性比较算法，基数排序和计数排序都是特别的桶排序，桶排序是一种空间换时间的算法

算法对照表

1.png

一、冒泡排序

算法思想：

• 对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。

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

二、选择排序

算法思想:

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

function selectSort(arr){
  for(let i=0;i<arr.length;i++){
    let min = i
    for(let j=i+1;j<arr.length;j++){
      if(arr[min] > arr[j]){
        min = j
      }
    }
    if(i != min){
      let swap = arr[i]
      arr[i] = arr[min]
      arr[min] = swap 
    }
  }
}

三、插入排序

算法思想:

• 每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

function insertSort(arr){
  for(let i=1;i<arr.length;i++){
    let cur = i
    while(arr[cur] < arr[cur-1]){
      let swap = arr[cur]
      arr[cur] = arr[cur-1]
      arr[cur-1] = swap
      cur--
    }
  } 
}

四、快速排序

算法思想:

• 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

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

五、堆排序

算法思想:

• 堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。
• 堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换….如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。

function swap(arr, i, j){
  let swap = arr[i]
  arr[i] = arr[j]
  arr[j] = swap
}
function sort(arr){
  for(let i=Math.floor(arr.length/2)-1;i>=0;i--){
    heap(arr, i, arr.length)   
  }
  for(let i=arr.length-1;i>0;i--){
    swap(arr, 0, i)
    heap(arr, 0, i)
  }
}
function heap(arr, i, length){
  let temp = arr[i]  
  for(let k=2*i+1;k<length;k=2*k+1){
    if(k+1 < length && arr[k] < arr[k+1]){
      k++
    }
    if(temp < arr[k]){
      arr[i] = arr[k]
      i = k
    }else{
      break;
    }
    arr[i] = temp
  }
}

六、归并排序

算法思想:

• 将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。
• 通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 ….. 直到全部小的数组合并起来。

function merge(begin,end){
  if(end-begin <2){
    return
  }
  let mid = begin + end >> 1
  merge(begin,mid)
  merge(mid,end)
  sort(begin,mid,end)
}
function sort(begin, mid, end){
  let li = 0,le = mid-begin
  let ri = mid,re = end
  let ai = begin
  let leftArray = []
  for(let i=0;i<le;i++){
    leftArray[i] = arr[begin++]
  }
  while(li < le){
    if(ri < re && arr[ri] <= leftArray[li]){
      arr[ai++] = arr[ri++]
    }else{
      arr[ai++] = leftArray[li++]
    }
  }
}

七、希尔排序 （缩小增量排序）

算法思想:

• 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

function shell(arr){
  let step = stepArr(arr)
  for(let i=0;i<step.length;i++){
    insert(arr,step[i])
  }
}
function stepArr(arr){
  let step = arr.length
  let squense = []
  while((step>>=1)>0){
    squense.push(step)
  }
  return squense
}
function swap(arr,i,j){
  let swap = arr[i]
  arr[i] = arr[j]
  arr[j] = swap
}
function insert(arr, step){
  for(let col = 0;col < step;col++){
    for(let i=col+step;i<arr.length;i+=step){
      let cur = i
      while(cur > 0 && arr[cur] < arr[cur-step]){
        swap(arr,cur,cur-step)
        cur-=step
      }
    }
  }
}

八、计数排序

算法思想:

• 就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。

function countSort(arr){
  let max = arr[0]
  for(let i=1;i<arr.length;i++){
    if(arr[i] > max){
      max = arr[i]
    }
  }
  let count = []
  count.length = max+1
  count.fill(0,0,max+1)
  for(let i=0;i<arr.length;i++){     
    count[arr[i]]++
  }
  let newArray = []
  for(let i=0;i<count.length;i++){
    while(count[i] > 0){
      newArray.push(i)
      count[i]--
    }
  }
}

九、基数排序

算法思想:

• 先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小，以此类推...排到最后，就是一组有序的元素了。

function baseSort(arr){
  let max = arr[0]
  for(let i=1;i<arr.length;i++){
    if(max < arr[i]){
      max = arr[i]
    }
  } 
  let j=0
  while(Math.pow(10,j) <= max){
    let array = []
    array.length = 10
    for(let i=0;i<10;i++){
      array[i] = new Array()
    }
    for(let i=0;i<arr.length;i++){
      let digit = Math.floor(arr[i] / Math.pow(10,j)) % 10
      let len = array[digit].length 
      array[digit][len] = arr[i]
    }
    arr = []
    for(let i=0;i<array.length;i++){
      if(array[i].length>0){
        arr = arr.concat(array[i])
      }
    }
    j++
  }
}

十、桶排序

算法思想:

• 基数排序和计数排序都是特殊的桶排序，主要思想就是按照一定的规则将长度为n的数组，放进k个桶中，在分别进行排序在合并。
  时间复杂度：
  (n/k)lg(n/k)k+n => n(lgn-lgk)+n => n+k