关注我们

插入排序

这是基于就地比较的排序算法。在此，将始终维护一个子列表。如数组的下部保持被排序。要"插入"此排序子列表中的元素，必须找到其适当的位置，然后将其插入到该位置。因此，名称为插入排序。

依次搜索该数组，然后将未排序的项目移动并插入到已排序的子列表中(在同一数组中)。该算法不适用于大型数据集，因为其平均和最坏情况下的复杂度为Ο(n 2 )，其中 n 是元素。

插入排序

我们以未排序的数组为例。

插入排序比较前两个元素。

它发现14和33都已经按升序排列。目前，已排序的子列表中有14个。

插入排序前进，将33与27进行比较。

并发现33位置不正确。

它将33与27交换。它还将检查已排序子列表的所有元素。在这里，我们看到排序后的子列表只有一个元素14，而27大于14。因此，排序后的子列表在交换后仍保持排序。

到目前为止，我们在排序后的子列表中有14和27。接下来，将33与10进行比较。

无涯教程网

这些值不是按排序的顺序。

因此，我们交换它们。

但是，交换使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

C语言进行插入排序实现

在线运行

#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 ]
==================================================

祝学习愉快！(内容编辑有误？请选中要编辑内容 -> 右键 -> 修改 -> 提交！)

技术教程推荐

程序员的数学基础课 -〔黄申〕

TensorFlow快速入门与实战 -〔彭靖田〕

好记忆不如烂笔头。留下您的足迹吧 :)