相關(guān)概念

穩(wěn)定性

• 穩(wěn)定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不穩(wěn)定：如果a原本在b的前面，而a=b，排序之后 a 可能會(huì)出現(xiàn)在 b 的后面。

時(shí)間復(fù)雜度

• 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí)，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。

最壞時(shí)間復(fù)雜度

• 最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界，這就保證了算法的運(yùn)行時(shí)間不會(huì)比任何更長(zhǎng)。

平均時(shí)間復(fù)雜度

• 平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間。設(shè)每種情況的出現(xiàn)的概率為pi,平均時(shí)間復(fù)雜度則為sum(pi*f(n))
  和平均時(shí)間復(fù)雜度

空間復(fù)雜度

• 一個(gè)程序的空間復(fù)雜度是指運(yùn)行完一個(gè)程序所需內(nèi)存的大小。

注意

• 基于比較的排序算法時(shí)間復(fù)雜度最快為O(nlogn)
• 部分情況下，O(n2) 也會(huì)比O(nlogn)快（數(shù)據(jù)長(zhǎng)度較小時(shí)），一般的用于算法時(shí)，數(shù)據(jù)量都可以超過臨界點(diǎn)，所以一般關(guān)注算法復(fù)雜度級(jí)別
• 非線性比較算法，基數(shù)排序和計(jì)數(shù)排序都是特別的桶排序，桶排序是一種空間換時(shí)間的算法

算法對(duì)照表

1.png

一、冒泡排序

算法思想：

• 對(duì)相鄰的元素進(jìn)行兩兩比較，順序相反則進(jìn)行交換，這樣，每一趟會(huì)將最小或最大的元素“浮”到頂端，最終達(dá)到完全有序。

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
      }
    }
  } 
}

二、選擇排序

算法思想:

• 首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。

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 
    }
  }
}

三、插入排序

算法思想:

• 每一步將一個(gè)待排序的記錄，插入到前面已經(jīng)排好序的有序序列中去，直到插完所有元素為止。

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--
    }
  } 
}

四、快速排序

算法思想:

• 通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

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))
}

五、堆排序

算法思想:

• 堆的特點(diǎn)就是堆頂?shù)脑厥且粋€(gè)最值，大頂堆的堆頂是最大值，小頂堆則是最小值。
• 堆排序就是把堆頂?shù)脑嘏c最后一個(gè)元素交換，交換之后破壞了堆的特性，我們?cè)侔讯阎惺Ｓ嗟脑卦俅螛?gòu)成一個(gè)大頂堆，然后再把堆頂元素與最后第二個(gè)元素交換….如此往復(fù)下去，等到剩余的元素只有一個(gè)的時(shí)候，此時(shí)的數(shù)組就是有序的了。

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
  }
}

六、歸并排序

算法思想:

• 將一個(gè)大的無序數(shù)組有序，我們可以把大的數(shù)組分成兩個(gè)，然后對(duì)這兩個(gè)數(shù)組分別進(jìn)行排序，之后在把這兩個(gè)數(shù)組合并成一個(gè)有序的數(shù)組。由于兩個(gè)小的數(shù)組都是有序的，所以在合并的時(shí)候是很快的。
• 通過遞歸的方式將大的數(shù)組一直分割，直到數(shù)組的大小為 1，此時(shí)只有一個(gè)元素，那么該數(shù)組就是有序的了，之后再把兩個(gè)數(shù)組大小為1的合并成一個(gè)大小為2的，再把兩個(gè)大小為2的合并成4的 ….. 直到全部小的數(shù)組合并起來。

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++]
    }
  }
}

七、希爾排序 （縮小增量排序）

算法思想:

• 希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。

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
      }
    }
  }
}

八、計(jì)數(shù)排序

算法思想:

• 就是把數(shù)組元素作為數(shù)組的下標(biāo)，然后用一個(gè)臨時(shí)數(shù)組統(tǒng)計(jì)該元素出現(xiàn)的次數(shù)，例如 temp[i] = m, 表示元素 i 一共出現(xiàn)了 m 次。最后再把臨時(shí)數(shù)組統(tǒng)計(jì)的數(shù)據(jù)從小到大匯總起來，此時(shí)匯總起來是數(shù)據(jù)是有序的。

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]--
    }
  }
}

九、基數(shù)排序

算法思想:

• 先以個(gè)位數(shù)的大小來對(duì)數(shù)據(jù)進(jìn)行排序，接著以十位數(shù)的大小來多數(shù)進(jìn)行排序，接著以百位數(shù)的大小，以此類推...排到最后，就是一組有序的元素了。

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++
  }
}

十、桶排序

算法思想:

• 基數(shù)排序和計(jì)數(shù)排序都是特殊的桶排序，主要思想就是按照一定的規(guī)則將長(zhǎng)度為n的數(shù)組，放進(jìn)k個(gè)桶中，在分別進(jìn)行排序在合并。
  時(shí)間復(fù)雜度：
  (n/k)lg(n/k)k+n => n(lgn-lgk)+n => n+k