相關(guān)概念

• 1.算法復(fù)雜度
  • 時間復(fù)雜度：是指執(zhí)行算法所需要的時間(計算工作量)功氨。
    • 語句頻度/時間頻度：一個算法中的語句執(zhí)行次數(shù)序苏，記為T(n)。
  • 空間復(fù)雜度：是指執(zhí)行這個算法所需要的內(nèi)存空間捷凄。
• 2.排序方式
  • 根據(jù)是否需要借助額外的數(shù)組來輔助排序忱详，分為：
    • In-place：不需要借助額外的數(shù)組，直接對待排序數(shù)組中的元素進(jìn)行比較和交換跺涤。
    • Out-place：需要利用額外的數(shù)組來輔助排序匈睁。
  • 舉例：冒泡排序，不需要借助額外數(shù)組桶错，直接對待排序數(shù)組的相鄰元素兩兩比較和交換航唆，屬于In-place。計數(shù)排序院刁，需要一個額外的計數(shù)數(shù)組來輔助排序糯钙，屬于Out-place。
• 3.穩(wěn)定性
  • 穩(wěn)定：等值元素的先后順序退腥，排序前后“不”發(fā)生改變任岸，稱這種排序算法是穩(wěn)定的。
    • 包括：冒泡排序狡刘，直接插入排序享潜，歸并排序，計數(shù)排序颓帝，桶排序米碰，基數(shù)排序窝革。
  • 不穩(wěn)定：等值元素的先后順序，排序前后“可能”發(fā)生改變吕座，稱為不穩(wěn)定的虐译。
  • 包括：快速排序，希爾排序吴趴，簡單選擇排序漆诽，堆排序。

總結(jié)十大排序算法的復(fù)雜度锣枝、排序方式厢拭、穩(wěn)定性

原理簡述

• 1.冒泡排序
  1）比較相鄰的元素，如果前一個比后一個大撇叁，就交換它們供鸠。
  2）對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對陨闹。這樣一輪比較結(jié)束楞捂，最大的數(shù)被移動到了最后的位置。
  3）針對所有的元素重復(fù)以上的步驟趋厉，除了最后一個寨闹。
  4）持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較君账。

• 2.快速排序
  1）先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)繁堡。
  2）分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊乡数，小于或等于它的數(shù)全放到它的左邊椭蹄。
  3）再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)瞳脓。
  更多參考「快速排序」塑娇，對挖坑填數(shù)進(jìn)行總結(jié):

  • 1．i=L; j=R; 將基準(zhǔn)數(shù)挖出形成第一個坑a[i]。
  • 2．j--由后向前找比它小的數(shù)劫侧，找到后挖出此數(shù)填前一個坑a[i]中埋酬。
  • 3．i++由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個坑a[j]中烧栋。
  • 4．再重復(fù)執(zhí)行2写妥，3二步，直到i==j审姓，將基準(zhǔn)數(shù)填入a[i]中珍特。

• 3.直接插入排序
  1）先將數(shù)組arr分為左右兩部分，左側(cè)sorted_list=[arr[0]]魔吐，右側(cè)unsorted_list=arr[1:]扎筒。
  2）依次遍歷unsorted_list列表中的元素a：

  • 元素a與sorted_list中的元素b從后向前依次進(jìn)行比較莱找；
  • 滿足條件a<b或a>b(根據(jù)排序順序確定)時，b元素往后移動一格嗜桌；
  • 直到最終不滿足條件時奥溺，將元素a填入sorted_list中的索引空位。

• 4.希爾排序
  1）取序列長度的一半(向下取整)作為增量gap骨宠，對序列進(jìn)行分組浮定。
  2）然后對各組進(jìn)行“直接插入排序”。
  3）增量gap依次減半(向下取整)层亿，重復(fù)1）桦卒、2），最終一次的增量gap為1匿又。

• 5.簡單選擇排序
  第一輪找最小的數(shù)并放到第一個位置方灾。
  第二輪找第二小的數(shù)并放到第二個位置。
  依次迭代...

• 6.堆排序
  1）把無序數(shù)組構(gòu)建成二叉堆(若從小到大排序碌更，則構(gòu)建成最大堆)迎吵。
  2）將堆頂元素與二叉堆末尾元素進(jìn)行替換(此時，最后一個元素已經(jīng)排序好了)针贬。
  3）對剩余未排序的元素，循環(huán)重復(fù)1）拢蛋、2）桦他。

• 7.歸并排序
  二路歸并排序：將序列不斷二分為多個子序列，對子序列從上到下依次進(jìn)行排序合并谆棱。

• 8.計數(shù)排序
  定義一個計數(shù)數(shù)組快压，統(tǒng)計每個元素出現(xiàn)的次數(shù)。

• 9.桶排序
  先分桶垃瞧，每個桶代表一個數(shù)值區(qū)間范圍蔫劣，將元素放入對應(yīng)桶中。
  然后个从，對每個桶分別進(jìn)行排序(可遞歸調(diào)用桶排序)脉幢。
  最后，合并所有的桶即可嗦锐。

• 10.基數(shù)排序
  取數(shù)組中最大元素的位深(個嫌松、十、百...)奕污。
  按個位分桶萎羔，然后取出。
  按十位分桶碳默，然后取出贾陷。
  依次類推...