相關(guān)概念

• 1.算法復(fù)雜度
  • 時(shí)間復(fù)雜度：是指執(zhí)行算法所需要的時(shí)間(計(jì)算工作量)。
    • 語(yǔ)句頻度/時(shí)間頻度：一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)，記為T(mén)(n)。
  • 空間復(fù)雜度：是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。
• 2.排序方式
  • 根據(jù)是否需要借助額外的數(shù)組來(lái)輔助排序，分為：
    • In-place：不需要借助額外的數(shù)組，直接對(duì)待排序數(shù)組中的元素進(jìn)行比較和交換。
    • Out-place：需要利用額外的數(shù)組來(lái)輔助排序。
  • 舉例：冒泡排序，不需要借助額外數(shù)組，直接對(duì)待排序數(shù)組的相鄰元素兩兩比較和交換，屬于In-place。計(jì)數(shù)排序，需要一個(gè)額外的計(jì)數(shù)數(shù)組來(lái)輔助排序，屬于Out-place。
• 3.穩(wěn)定性
  • 穩(wěn)定：等值元素的先后順序，排序前后“不”發(fā)生改變，稱(chēng)這種排序算法是穩(wěn)定的。
    • 包括：冒泡排序，直接插入排序，歸并排序，計(jì)數(shù)排序，桶排序，基數(shù)排序。
  • 不穩(wěn)定：等值元素的先后順序，排序前后“可能”發(fā)生改變，稱(chēng)為不穩(wěn)定的。
  • 包括：快速排序，希爾排序，簡(jiǎn)單選擇排序，堆排序。

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

原理簡(jiǎn)述

• 1.冒泡排序
  1）比較相鄰的元素，如果前一個(gè)比后一個(gè)大，就交換它們。
  2）對(duì)每一對(duì)相鄰元素做同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這樣一輪比較結(jié)束，最大的數(shù)被移動(dòng)到了最后的位置。
  3）針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
  4）持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

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

  • 1．i=L; j=R; 將基準(zhǔn)數(shù)挖出形成第一個(gè)坑a[i]。
  • 2．j--由后向前找比它小的數(shù)，找到后挖出此數(shù)填前一個(gè)坑a[i]中。
  • 3．i++由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個(gè)坑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ù)排序順序確定)時(shí)，b元素往后移動(dòng)一格；
  • 直到最終不滿足條件時(shí)，將元素a填入sorted_list中的索引空位。

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

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

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

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

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

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

• 10.基數(shù)排序
  取數(shù)組中最大元素的位深(個(gè)、十、百...)。
  按個(gè)位分桶，然后取出。
  按十位分桶，然后取出。
  依次類(lèi)推...