插入排序：C 语言算法， C++, Java, Python 例子

什么是插入排序？

插入排序是比较排序算法之一，通过一次迭代一个元素并将元素放置在正确的位置来对元素进行排序。

每个元素按顺序插入到已排序的列表中。已排序列表的大小最初为 1。插入排序算法确保前 k 个元素在第 k 次迭代后已排序。

插入排序算法的特点

插入排序算法具有以下重要特点：

• 它是一种稳定的排序技术，因此它不会改变相同元素的相对顺序。
• 它对于较小的数据集很有效，但对于较大的列表无效。
• 插入排序是自适应的，如果部分排序，它会减少其总步骤数。 排列 作为输入以使其高效。

如何插入 Opera工作？

在插入排序算法中，插入操作用于对未排序元素进行排序。它有助于将新元素插入到已排序的列表中。

插入操作的伪代码：

考虑一个包含 N 个元素的列表 A。

A[N-1] is the element to be inserted in the 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。

步骤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]，即左相邻元素不再大于。现在我们得出结论，6 插入正确，我们到此停止算法。

插入排序的工作原理

上面讨论的插入操作是插入排序的核心。插入过程在每个元素上执行，最后得到排序后的列表。

上图示例演示了数据结构中插入排序的工作原理。最初，排序子列表中只有一个元素，即 4。插入 A[1] 即 3 后，排序子列表的大小增加到 2。

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 代码

#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 插入排序程序

#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^2)。插入排序是自适应排序算法之一。

插入排序的复杂性

空间复杂度

插入排序不需要额外的空间来对元素进行排序，空间复杂度是常数，即O（1）。

时间复杂度

由于插入排序会同时迭代每个元素，因此需要 N-1 次遍历才能对 N 个元素进行排序。对于每次遍历，如果元素已经排序，则可能不进行任何交换；如果元素按降序排列，则进行交换。

• 对于第 1 轮，所需的最小交换次数为零，所需的最大交换次数为 1。
• 对于第 2 轮，所需的最小交换次数为零，所需的最大交换次数为 2。
• 对于第 N 轮，所需的最小交换次数为零，所需的最大交换次数为 N。
• 最小交换为零，因此迭代 N 次的最佳时间复杂度为 O(N)。
• 总最大交换次数为 (1+2+3+4+..+N) 即 N(N+1)/2，最坏时间复杂度为 O(N^2)。

这是插入排序的重要时间复杂度：

• 最坏情况复杂度：O(n2)：当数组按升序排列时，按降序排序是最坏的情况。
• 最佳情况复杂度： O(n)：最佳复杂度发生在数组已经排序时，外循环运行 n 次，而内循环根本不运行。只有 n 次比较。因此，在这种情况下，复杂度是线性的。
• 平均案例复杂度： O(n2)：当数组元素以混乱的顺序出现时，即既不升序也不降序，就会发生这种情况。

总结

• 插入排序是一种基于比较的排序算法方法。
• 它是一种稳定的排序技术，因此它不会改变相同元素的相对顺序。
• 对于每个元素，均使用插入操作将元素插入已排序的子列表中。
• 插入排序是一种就地排序算法。
• 插入排序的最坏和平均时间复杂度都是二次方，即O(N^2)。
• 插入排序不需要任何辅助空间。