这是基于就地比较的排序算法。在此,将始终维护一个子列表。如数组的下部保持被排序。要"插入"此排序子列表中的元素,必须找到其适当的位置,然后将其插入到该位置。因此,名称为插入排序。
依次搜索该数组,然后将未排序的项目移动并插入到已排序的子列表中(在同一数组中)。该算法不适用于大型数据集,因为其平均和最坏情况下的复杂度为Ο(n 2 ),其中 n 是元素。
我们以未排序的数组为例。
插入排序比较前两个元素。
它发现14和33都已经按升序排列。目前,已排序的子列表中有14个。
插入排序前进,将33与27进行比较。
并发现33位置不正确。
它将33与27交换。它还将检查已排序子列表的所有元素。在这里,我们看到排序后的子列表只有一个元素14,而27大于14。因此,排序后的子列表在交换后仍保持排序。
到目前为止,我们在排序后的子列表中有14和27。接下来,将33与10进行比较。
来源:LearnFk无涯教程网
这些值不是按排序的顺序。
因此,我们交换它们。
但是,交换使27和10未排序。
因此,我们也交换它们。
同样,我们以未排序的顺序找到14和10。
我们再次交换它们。到第三次迭代结束时,我们有了一个包含4个项目的排序子列表。
该进程一直进行到所有未排序的值都包含在已排序的子列表中为止。现在我们将看到插入排序的一些编程方面。
procedure insertionSort( A : array of items ) int holePosition int valueToInsert for i = 1 to length(A) inclusive do: /* select value to be inserted */ valueToInsert = A[i] holePosition = i /*locate hole position for the element to be inserted */ while holePosition > 0 and A[holePosition-1] > valueToInsert do: A[holePosition] = A[holePosition-1] holePosition = holePosition -1 end while /* insert the number at hole position */ A[holePosition] = valueToInsert end for end procedure
#include <stdio.h> #include <stdbool.h> #define MAX 7 int intArray[MAX] = {4,6,3,2,1,9,7}; void printline(int count) { int i; for(i = 0;i < count-1;i++) { printf("="); } printf("=\n"); } void display() { int i; printf("["); // navigate through all items for(i = 0;i < MAX;i++) { printf("%d ",intArray[i]); } printf("]\n"); } void insertionSort() { int valueToInsert; int holePosition; int i; // loop through all numbers for(i = 1; i < MAX; i++) { // select a value to be inserted. valueToInsert = intArray[i]; // select the hole position where number is to be inserted holePosition = i; // check if previous no. is larger than value to be inserted while (holePosition > 0 && intArray[holePosition-1] > valueToInsert) { intArray[holePosition] = intArray[holePosition-1]; holePosition--; printf(" item moved : %d\n" , intArray[holePosition]); } if(holePosition != i) { printf(" item inserted : %d, at position : %d\n" , valueToInsert,holePosition); // insert the number at hole position intArray[holePosition] = valueToInsert; } printf("Iteration %d#:",i); display(); } } void main() { printf("Input Array: "); display(); printline(50); insertionSort(); printf("Output Array: "); display(); printline(50); }
Input Array: [4 6 3 2 1 9 7 ] ================================================== Iteration 1#:[4 6 3 2 1 9 7 ] item moved : 6 item moved : 4 item inserted : 3, at position : 0 Iteration 2#:[3 4 6 2 1 9 7 ] item moved : 6 item moved : 4 item moved : 3 item inserted : 2, at position : 0 Iteration 3#:[2 3 4 6 1 9 7 ] item moved : 6 item moved : 4 item moved : 3 item moved : 2 item inserted : 1, at position : 0 Iteration 4#:[1 2 3 4 6 9 7 ] Iteration 5#:[1 2 3 4 6 9 7 ] item moved : 9 item inserted : 7, at position : 5 Iteration 6#:[1 2 3 4 6 7 9 ] Output Array: [1 2 3 4 6 7 9 ] ==================================================
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)