C++中的插入式排序及实例

深入了解插入式排序的经典案例。

插入式排序是一种排序技术,可以用我们玩牌的方式来看待。 我们在一副牌中插入任何一张牌或将其删除,插入式排序的工作方式也是如此。

插入排序算法技术比泡沫排序和选择排序技术更有效,但比其他技术如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",它们使用 "分而治之 "的策略对数据列表进行排序。

滚动到顶部