Big Theta符號和選擇排序

Question

當數組通過重複添加19時，選擇排序算法的Big-Theta（T）符號中的最佳情況和最壞情況複雜度是多少？

例如：

[ 19, 13, 7, 19, 12, 16, 19 ], 
[ 19, 13, 7, 19, 12, 16, 19, 19 ], 
[ 19, 13, 7, 19, 12, 16, 19, 19, 19 ] 

等等。 n用於表示數組的長度。

所以我們將相同的數字添加到數組的末尾，但這個數字也恰好是最大的數字，所以它會停留在數組的末尾。這是否意味着它對效率沒有任何影響？我很困惑。

Answer 1

不，它對效率沒有影響。

在selection sort中，由於嵌套循環，性能爲N^2。即使最後的元素不需要交換，循環仍然會比較它們。因此，要回答您的確切問題：由於最佳案例，最差案例和平均案例性能均爲N^2，並且對效率沒有影響，所以性能沒有變化。

Answer 2

升序，

1. 查找最小值在列表
2. 用值交換它在第一位置
3. 重複上述用於清單的剩餘部分的步驟（開始於 的第二個位置和每次前進）

因此，我們必須通過檢查來檢查所有元素的其餘所有元素，以通過檢查來獲得最小值，即使相同元素在那裏，直到最後一個元素。

A - an array containing the list of numbers 
numItems - the number of numbers in the list 

for i = 0 to numItems - 1 
    for j = i+1 to numItems    
     if A[i] > A[j] 
      // Swap the entries 
      Temp = A[i] 
      A[i] = A[j] 
      A[j] = Temp   
     End If  
    Next j 
Next i 

正如你可以看到上面的僞代碼，兩個環路迭代器將結束無任何條件下自己的極限。所以它給了θ(n²)。但是，O(n)平均值，θ(n)最差和θ(1)最佳情況下的交換環境。