C++ 中插入排序的時間複雜度問題

插入排序的時間複雜度是多少？

時間複雜度是指一組程式碼或演算法處理或執行所需的時間量，它是輸入量的一個函式。

對於插入排序，在最佳情況下，時間複雜度為 O(n)，即 n 的大 O 階。而在平均或最壞情況下，複雜度為 O(n²)。

當對以下形式的 n 個大小的陣列應用插入排序演算法時，排序的時間複雜度是多少：6, 5, 8, 7, 10, 9 …… I, i-1

對上述陣列進行排序的時間複雜度為 O(n)。仔細觀察該演算法，這裡所有對都從其原始位置交換，即元素 1 和元素 2 的位置互換，3 和 4 互換，依此類推。因此，在排序過程中，演算法只需要進行 n 次操作即可完成排序。

定義插入排序並編寫插入排序的程式碼？

插入排序是一種排序演算法，它透過將元素放置到已排序陣列中的正確位置來對資料結構進行排序。

以下程式碼顯示了插入排序的函式：

示例

void insertionSort(int arr[], int n) {
   for (int i = 1; i < n; i++){
      int element = arr[i];
      int j = i-1;
      while (j >= 0 && arr[j] > element){
         arr[j+1] = arr[j];
         j = j-1;
      }
      arr[j+1] = element;
   }
}

sudhir sharma

更新於: 2019-10-24

1K+ 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習