【C】初阶数据结构9 -- 直接插入排序

  前面我们学习了数据结构二叉树，接下来我们将开启一个新的章节，那就是在日常生活中经常会用到的排序算法。

  所谓排序算法就是给你一堆数据，让你从小到大（或从大到小）的将这些数据排成一个有序的序列（这些数据通常是存放在数组中）。排序算法有很多，前面我们在学习堆的时候已经介绍过一种经典的排序算法 -- 堆排序，不知道你是否还记得堆排序的算法思想和时间复杂度呢？接下来我们将会讲解其他的 6 个经典排序算法，包括插入排序，希尔排序，直接选择排序，冒泡排序，快速排序以及归并排序。

---

目录

1  算法思想

2  代码实现

3  时间复杂度与空间复杂度

---

1  算法思想

  所谓直接插入排序就是在已经排好序的序列中依次插入要插入的数字，所以数组中的数据会被划分为两大部分，分别是已经排好序的一部分，还有待排序的一部分，直接插入排序就是将没有排好序的数字依次插入到已经排好序的序列中。

  如以下这个序列进行直接插入排序的过程如图所示：

 这里假设要对数组 arr 排升序：开始我们先定义一个循环变量 i，让其从 0 下标开始遍历 arr 数组，结束条件我们先暂时不管。然后在循环里面定义一个 end 和 tmp 变量，end 变量指向已经排好序的序列的最后一个元素，tmp 变量用来暂存待排序的那个数字（也就是要插入到有序序列中的那个数字），即 arr[end + 1]。在循环里面，如果 arr[end] > tmp ，说明 arr[end] 是排在 tmp 后面的，就要让 arr[end + 1] = arr[end]，让数组元素向后挪，直到出现 arr[end] <= tmp 或者 有序序列的元素已经全部挪完了，即end < 0 了，此时，tmp 就应该插入到 arr[end + 1] 的位置。

  那么遍历数组的循环的结束条件应该是什么呢？由于 end 每次都是指向的排好序的序列的最后一个元素，而第一次循环的排好序的最后一个元素就是第一个元素（也就是下标为 0 的元素）；第二次循环排好序的最后一个元素就是第二个元素（下标为1），所以每次进入循环 end 应该是等于 i 的，这样 end 所指向的元素才是排好序序列的最后一个元素。既然 end = i，那么在循环里面由于要挪动元素，就会出现 arr[end + 1]  = arr[end]，所以为了防止 end + 1 超出数组访问范围，发生越界，所以 i 最后一次应该是指向倒数第二个元素，即下标为 n - 2 的元素（n 为数组元素个数），所以循环停止条件应该是 i <= n - 2 或者 i < n - 1。

---

2  代码实现

//直接插入排序
//这里排升序
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void InsertSort(int* arr, int n)
{for (int i = 0;i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){Swap(&arr[end], &arr[end-1]);end--;}else{break;}}Swap(&arr[end + 1], &tmp);
}

​测试用例：

//打印函数
void Print(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}//测试InsertSort
int main()
{int arr[] = { 10, 2, 5, 7, 1, 4, 8 };int n = sizeof(arr) / sizeof(arr[0]);InsertSort(arr, n);Print(arr, n);return 0;
}

---

3  时间复杂度与空间复杂度

  时间复杂度：最坏情况下 T(n) = O(n^2)，但是在一般情况下，直接插入排序是小于O(n^2)的，因为如果end位置小于tmp的话，就会跳出第二层循环，所以是小于O(n^2)的。

  空间复杂度：由于在代码中仅仅使用了几个变量，所以空间复杂度是 O(1) 的。