深入了解插入式排序的经典案例。
插入式排序是一种排序技术，可以用我们玩牌的方式来看待。 我们在一副牌中插入任何一张牌或将其删除，插入式排序的工作方式也是如此。
插入排序算法技术比泡沫排序和选择排序技术更有效，但比其他技术如Quicksort和Merge排序效率低。
概述
在插入式排序技术中，我们从第二个元素开始，将其与第一个元素进行比较，并将其放在适当的位置。 然后我们对随后的元素执行这一过程。
我们将每个元素与之前的所有元素进行比较，然后将元素放到或插入到适当的位置。 插入式排序技术对于元素数量较少的数组来说比较可行。 它对于链接列表的排序也很有用。
链表有一个指向下一个元素的指针（如果是单链表）和一个指向上一个元素的指针（如果是双链表）。 因此，对链表实现插入排序变得更加容易。
让我们在本教程中探索关于插入式排序的所有内容。
一般算法
步骤1 : 对K=1至N-1重复步骤2至5
第2步 : 设定temp = A[K]
步骤3 : 设J = K - 1
第四步 : 重复而temp <=A[J]
设A[J+1]=A[J]
设J=J-1
[内循环结束]
第5步 : 设置A[J + 1] = temp
[循环结束]
第6步 : 退出
因此，在插入式排序技术中，我们从第二个元素开始，因为我们假设第一个元素总是被排序的。 然后从第二个元素到最后一个元素，我们将每个元素与它之前的所有元素进行比较，然后将该元素放在适当的位置。
伪代码
以下是插入式排序的伪代码。
程序 insertionSort(array,N ) array - 要排序的数组 N-元素数 begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //确定插入元素的自由位置 whilefreePosition> 0 and array[freePosition -1]> insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //插入元素。自由位置的数字 数组[freePosition] = insert_val end for 结束程序
上面给出的是插入式排序的伪代码，接下来，我们将在下面的例子中说明这一技术。
插图
要排序的数组如下：
现在，对于每一次传递，我们将当前元素与之前的所有元素进行比较。 因此，在第一次传递中，我们从第二个元素开始。
因此，我们需要N次传递来完全排序一个包含N个元素的数组。
上述说明可以用表格的形式进行总结：
| 通过 | 未分类列表 | 比较 | 排序的列表 |
|---|---|---|---|
| 1 | {12,3,5,10,8,1} | {12,3} | {3,12,5,10,8,1} |
| 2 | {3,12,5,10,8,1} | {3,12,5} | {3,5,12,10,8,1} |
| 3 | {3,5,12,10,8,1} | {3,5,12,10} | {3,5,10,12,8,1} |
| 4 | {3,5,10,12,8,1} | {3,5,10,12,8} | {3,5,8,10,12,1} |
| 5 | {3,5,8,10,12,1} | {3,5,8,10,12,1} | {1,3,5,8,10,12} |
| 6 | {} | {} | {1,3,5,8,10,12} |
如上图所示，我们从第二个元素开始，因为我们假设第一个元素总是被排序的。 所以我们开始比较第二个元素和第一个元素，如果第二个元素比第一个元素少，就交换位置。
这个比较和交换过程将两个元素放在适当的位置上。 接下来，我们将第三个元素与它之前的（第一和第二）元素进行比较，并执行同样的程序，将第三个元素放在适当的位置。
在这种方式下，对于每一次传递，我们把一个元素放在它的位置上。 对于第一次传递，我们把第二个元素放在它的位置上。 因此，在一般情况下，为了把N个元素放在它们适当的位置上，我们需要N-1次传递。
接下来，我们将演示插入式排序技术在C++语言中的实现。
C++实例
#include using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout<<"\nInput list is \n"; for(int i=0;i<10; i++) { cout <； ="" 输出：
输入列表是
12 4 3 1 15 45 33 21 10 2
排序后的列表是
1 2 3 4 10 12 15 21 33 45
接下来，我们将看到插入式排序技术的Java实现。
Java实例
public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println("Input list of elements ..."); for(int i=0;i<10;i++) { System.out.print(myarray[i] + " " ) ; } for(int k=1; k=0 & & temp <= myarray[j]) { myarray[j+1] = myarray[j]; j = j-1; } myarray[j+1] = temp; } System.out.println(" nsorted list of elements ..." ) ; for(inti=0;i<10;i++) { System.out.print(myarray[i] + " " ); } } } } 输出：
输入的元素列表...
12 4 3 1 15 45 33 21 10 2
排序的元素列表 ...
1 2 3 4 10 12 15 21 33 45
在这两个实现中，我们可以看到，我们从数组的第2个元素开始排序（循环变量j=1），并反复比较当前元素和其之前的所有元素，如果当前元素与之前的所有元素不一致，则对该元素进行排序，将其置于正确位置。
如果数组被部分排序，插入排序的效果最好，可以在较少的时间内完成。 但是，随着列表的增大，其性能也会下降。 插入排序的另一个优点是它是一个稳定的排序，这意味着它可以保持列表中相等元素的顺序。
插入式排序算法的复杂度分析
从上面的伪代码和插图来看，与冒泡排序或选择排序相比，插入排序是一种高效的算法。 它没有使用for循环和当前条件，而是使用了一个while循环，在数组排序后不再执行任何额外步骤。
然而，即使我们将排序后的数组传递给插入式排序技术，它仍然会执行外部for循环，从而需要n个步骤来对已经排序的数组进行排序。 这使得插入式排序的最佳时间复杂性是N的线性函数，其中N是数组中的元素数量。
因此，插入式排序技术的各种复杂情况如下：
最坏情况下的时间复杂性 O(n 2 ) 最佳情况下的时间复杂性 O(n) 平均时间复杂度 O(n 2 ) 空间的复杂性 O(1)
尽管有这些复杂性，我们仍然可以得出结论，与其他排序技术如泡沫排序和选择排序相比，插入排序是最有效的算法。
总结
插入排序是到目前为止讨论的三种技术中最有效的。 在这里，我们假设第一个元素被排序，然后重复比较每个元素和它之前的所有元素，然后将当前元素放在数组中的正确位置。
在本教程中，在讨论插入式排序时，我们注意到，我们使用1的增量来比较元素，而且它们是连续的。 这个特点导致需要更多的传递来获得排序的列表。
在我们即将到来的教程中，我们将讨论 "Shell sort"，它是对Selection sort的一种改进。
在shell排序中，我们引入了一个被称为 "增量 "或 "间隙 "的变量，用它将列表划分为包含非连续元素的子列表，这些元素之间存在 "间隙"。 与Insertion排序相比，shell排序需要的次数更少，速度也更快。
在我们未来的教程中，我们将学习两种排序技术，"Quicksort "和 "Mergesort"，它们使用 "分而治之 "的策略对数据列表进行排序。