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+ 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习