五、請完成下列表格有關排序演算法的 time complexity（假設排序資料有 n 個，資料位數有 d 個）、是否為 In− Space 演算法、是否為 Stable 演算法及範例數列 50, 46, 37, 28, 19 進行降冪排列時所需的比較次數。（30 分）

 

 

 

1. Bubble Sort

• 最佳時間複雜度:O(n) – 在陣列已經排序的情況下發生。
• 最壞時間複雜度:O(n^2) – 在陣列以反序排序的情況下發生。
• 原地排序:是。
• 穩定性:是。

2. Insertion Sort

• 最佳時間複雜度:O(n) – 在陣列已經排序的情況下發生。
• 最壞時間複雜度:O(n^2) – 在陣列以反序排序的情況下發生。
• 原地排序:是。
• 穩定性:是。

3. Merge Sort

• 最佳時間複雜度:O(n log n)。
• 最壞時間複雜度:O(n log n)。
• 原地排序:否(通常如此,儘管存在原地版本)。
• 穩定性:是。

4. Quick Sort

• 最佳時間複雜度:O(n log n) – 通常透過良好的支點選擇而達成。
• 最壞時間複雜度:O(n^2) – 發生在永遠選擇最小或最大元素作為支點的情況。
• 原地排序:是,但不總是(取決於具體實作)。
• 穩定性:否(通常如此,儘管存在穩定版本)。

5. Radix Sort (基數10)

• 最佳時間複雜度:O(d * (n + b)) – 其中 d 是位數個數,b 是基數(此情況為10)。
• 最壞時間複雜度:O(d * (n + b))。
• 原地排序:否。
• 穩定性:是。

6. Selection Sort

• 最佳時間複雜度:O(n^2)。
• 最壞時間複雜度:O(n^2)。
• 原地排序:是。
• 穩定性:否(通常如此,儘管存在穩定版本)。

降冪排序:序列 50, 46, 37, 28, 19

• Bubble Sort 和 Insertion Sort:這些演算法在最壞情況下將執行 n(n-1)/2 次比較,其中 n 是元素數量。所以對於 5 個元素,就是 5 * 4 / 2 = 10 次比較。
• Selection Sort:此演算法始終執行 n(n-1)/2 次比較,不論元素順序如何。所以與上面相同,10 次比較。
• Merge Sort:
  對於五個元素的數列，合併過程大致如下：
  • 將數列分割成單個元素的子數列。
  • 將兩個單個元素的數列合併，共需比較 4 次（因為有兩對需要合併）。
  • 將兩個兩元素的數列以及一個單個元素的數列合併，共需比較 4 + 2 = 6 次。
  • 最後，將一個四元素的數列和一個單個元素的數列合併，最多需要 4 次比較。
  因此，總共的比較次數是 4 + 6 + 4 = 14 次。
• Radix Sort: Radix 排序法不是比較排序法，所以排序時比較0次。

AI创作