7.2.1 直接插入排序.md

↩返回主页

⬅上一节 / 下一节➡

---

7.2.1 直接插入排序

  插入排序： 每次将一个待排序的序列插入到一个前面已排好序的子序列当中。

  直接插入排序： 是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增 1 的有序表。

• C 语言实现：

  void InsertSort(ElemType A[], int n) {
      int i, j;
      for(i=1; i<n; i++) {
          A[0] = A[i];
          for(j=i-1; A[0].key<A[j].key; j--)
              A[j+1] = A[j];
          A[j+1] = A[0];
      }
  }

  • 空间复杂度：O(1)

  • 最好时间复杂度：O(n)

  • 最坏时间复杂度：O(n²)

  • 平均时间复杂度：O(n²)

• 算法特点：

  • 属于内部排序

  • 时间复杂度：O(n²)

  • 空间复杂度：O(1)

  • 算法稳定

  • 适用于 顺序存储 和 链式存储

💡 题型

  xxx

单项选择题

1. xxxx（ ）

   A. xxx
   B. XX
   C. Xx
   D. xX
   
   

   查看解析

   答案：x

---

返回顶部⤴

-- 完 --