用C语言实现插入排序算法 C++, Java, Python 例子
陈莎拉
什么是插入排序？
插入排序是一种比较排序算法，它通过一次迭代一个元素，并将该元素放置在已排序区域中的正确位置来对元素进行排序。
每个元素按顺序插入到一个已排序的列表中。初始时，已排序列表的大小为 1。插入排序算法确保在外部循环的第 k 次迭代后，前 k 个元素已排序。
由于插入排序是逐步构建结果的，因此它易于教授、易于调试，并且对于非常小的输入来说是一个强大的基准，而更复杂的算法会增加开销却没有可衡量的收益。
插入排序算法的特点
插入排序算法具有以下重要特征，这些特征可以解释其在实际工作负载下的表现：
- 它是一种稳定的排序技术，因此它不会改变相同元素的相对顺序。
- 对于较小的数据集，这种方法效率很高；但对于以二次增长为主的大型列表，这种方法效果不佳。
- 插入排序是一种自适应算法，如果输入数据部分有序，它可以减少总步骤数。 排列 提供输入是为了提高效率，因为随机访问可以在内循环期间实现恒定时间的移位。
- 这是一个原地算法，因此不需要与输入大小成比例的辅助存储空间。
考虑到这些特点，下一节将解释算法每次迭代的核心插入操作。
如何插入 Opera工作？
在插入排序算法中，插入操作用于对未排序的元素进行排序。它有助于将新元素插入到已排序的列表中，同时保持已排序区域的现有顺序。
插入操作的伪代码：
考虑一个包含 N 个元素的列表 A。
// Insert A[N-1] into sorted sublist A[0..N-2] for i = N-1 to 1: if A[i] < A[i-1], then swap A[i] and A[i-1] else stop
在上面的例子中，新元素 6 被插入到一个已经排序的列表中。以下步骤 trace 内部循环，因为新元素向左移动到其正确位置。
步骤1） 与 A[5] 左相邻元素相比，9 > 6，我们交换 9 和 6 的位置。现在元素 6 被移动到 A[4] 中。
步骤2） 现在，我们比较 A[4] 和 A[3]，发现 A[3] > A[4]，所以我们再次交换 6 和 8 的位置。
步骤3） 现在比较 A[3] 和 A[2]。由于 A[2] > A[3]，我们交换 7 和 6 的位置。
步骤4） 我们比较 A[1] 和 A[2]。由于 A[1] < A[2]，其左侧相邻元素不再大于 A[2]。因此，我们得出结论：插入的元素 6 正确，内层循环到此结束。
插入排序的工作原理
上面讨论的插入操作是插入排序的核心。插入过程会对每个元素执行，最终，随着每次外层遍历，排序区域都会增加一个元素，从而得到排序后的列表。
上图展示了插入排序在数据结构中的工作原理。初始时，已排序子列表中只有一个元素，即 4。插入 A[1]（即 3）后，已排序子列表的大小增加到 2，算法继续执行此过程，直到所有元素都被插入。
概念流程确定后，以下章节将展示具体的实现方式。 C++, C, 和 Python 这样你就可以比较不同语言的循环结构了。
C++ 插入排序程序
此 C++ 下面实现使用了两个嵌套循环：外层循环选择下一个未排序的元素，内层循环将其向左移动，直到找到正确的位置。
#include <iostream> using namespace std; int main(){ //unsorted list int unsorted[] = {9,8,7,6,5,4,3,3,2,1}; //size of list int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]); //printing unsorted list cout << "\nUnsorted: "; for(int i = 0 ; i < size_unsorted ; i++){ cout << unsorted[i] << " "; } int current_element,temp; for(int i = 1; i < size_unsorted; i++){ current_element = unsorted[i]; for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){ //swapping if current element is lesser temp = unsorted[j+1]; unsorted[j+1] = unsorted[j]; unsorted[j] = temp; } } //printing sorted list cout << "\nSorted: "; for(int i = 0 ; i < size_unsorted ; i++){ cout << unsorted[i] << " "; } return 0; }
输出：
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
C Code 插入排序
同样的逻辑可以直接翻译成 C 语言。标准 printf 调用会替换流输出，但内部循环内的交换模式与此相同。 C++ 版。
#include <stdio.h> int main() { //unsorted list int unsorted[] = {9,8,7,6,5,4,3,3,2,1}; //size of list int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]); //printing unsorted list printf("\nUnsorted: "); for(int i = 0 ; i < size_unsorted ; i++){ printf("%d ", unsorted[i]); } int current_element, temp; for(int i = 1; i < size_unsorted; i++){ current_element = unsorted[i]; for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){ //swapping if current element is lesser temp = unsorted[j+1]; unsorted[j+1] = unsorted[j]; unsorted[j] = temp; } } //printing sorted list printf("\nSorted: "); for(int i = 0 ; i < size_unsorted ; i++){ printf("%d ", unsorted[i]); } return 0; }
输出：
Output: Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Python 插入排序程序
Python 支持元组交换ping 在一个表达式中，因此内部循环比其 C 语言版本更紧凑。 C++ 在保持相同算法行为的同时，实现对应的功能。
#unsorted list unsorted = [9,8,7,6,5,4,3,3,2,1] #size of list size_unsorted = len(unsorted) #printing unsorted list print("\nUnsorted: ", end="") for i in range(size_unsorted): print(unsorted[i], end=" ") for i in range(1, size_unsorted): current_element = unsorted[i] j = i - 1 while j >= 0 and unsorted[j] > current_element: #swapping if current element is lesser unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1] j -= 1 #printing sorted list print("\nSorted: ", end="") for i in range(size_unsorted): print(unsorted[i], end=" ")
输出：
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
插入排序的性质
以下是插入排序的一些重要特性，可以帮助您判断何时应该使用它：
- 线上： 插入排序可以在接收到元素的同时对其进行排序。如果我们已经对一个元素列表进行了排序，并且向列表中添加了更多元素，那么我们不需要再次运行整个排序过程。相反，我们只需要对新添加的元素进行迭代即可。
- 到位： 插入排序算法的空间复杂度是常数，不需要额外的空间。该算法对元素进行原地排序。
- 稳定： 在插入排序中，如果元素的值相等，我们不会交换它们。例如，如果两个元素 x 和 y 相等，并且在未排序的列表中 x 排在 y 之前，那么在排序后的列表中，x 仍然会排在 y 之前。这使得插入排序具有稳定性。
- 自适应： A 排序算法 如果输入元素或其子集已经排序，则插入排序算法耗时更短，因此称其为自适应排序算法。如上所述，插入排序的最佳运行时间为 O(N)，最差运行时间为 O(N²)。插入排序是一种自适应排序算法。
插入排序的复杂性
以下对复杂度的讨论涵盖了内存使用和运行时间，以便您可以将插入排序与其它算法进行比较，例如…… Bubbl电子排序 和 快速排序.
空间复杂度
插入排序不需要额外的空间来对元素进行排序。其空间复杂度为常数，即 O(1)，因为无论输入规模如何，都只使用少量临时变量。
时间复杂度
由于插入排序每次只处理一个元素，因此对 N 个元素进行排序需要 N-1 次迭代。每次迭代中，如果元素已经排序，则可能不需要交换元素；如果元素是按降序排列的，则可能需要交换元素很多次。
- 对于第 1 轮，所需的最小交换次数为零，所需的最大交换次数为 1。
- 对于第 2 轮，所需的最小交换次数为零，所需的最大交换次数为 2。
- 对于第 N 轮，所需的最小交换次数为零，所需的最大交换次数为 N。
- 最小交换为零，因此迭代 N 次的最佳时间复杂度为 O(N)。
- 最大交换次数为 (1+2+3+4+…+N)，即 N(N+1)/2，因此最坏时间复杂度为 O(N^2)。
以下是插入排序的重要时间复杂度：
- 最坏情况复杂度：O(n^2)：当需要升序排列数组时，却按降序排列，这是最坏的情况。
- 最佳情况复杂度： O(n)：最佳情况是数组已经排序；外层循环运行 n 次，而内层循环根本不运行。因为只有 n 次比较，所以复杂度是线性的。
- 平均案例复杂度： O(n^2): 当数组元素的顺序被打乱，既不是升序也不是降序时，就会发生这种情况。
