数据结构&算法插入排序

插入排序

插入排序是一个基于就地比较的排序算法。这里维护了一个总是排序的子列表。例如，数组的下半部分保持为排序。要在这个排序的子列表中“插入”的元素必须找到合适的位置，然后必须插入到那里。因此命名为插入排序。数组按顺序搜索，未排序的项被移动并插入到已排序的子列表中(在同一个数组中)。该算法不适合大型数据集的平均和最坏情况的复杂性Ο(n²),其中n是项的数量。

插入排序如何工作？

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

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

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

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

并发现33位置不正确。

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

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

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

因此，我们交换它们。

但是，交换使27和10未排序。-

因此，我们也交换它们。

同样，我们以未排序的顺序找到14和10。

我们再次交换它们。到第三次迭代结束时，我们有了一个包含4个项目的排序子列表。

该过程一直进行到所有未排序的值都包含在已排序的子列表中为止。现在我们将看到插入排序的一些编程方面。

算法

现在，我们对这种排序技术的工作原理有了更全面的了解，因此我们可以推导简单的步骤来实现插入排序。


步骤 1 − 如果它是第一个元素，那么它已经排好序了。返回1;
步骤 2 − 选择下一个元素
步骤 3 − 与排序后的子列表中的所有元素进行比较
步骤 4 − 移动已排序子列表中大于待排序值的所有元素
步骤 5 − 插入的值
步骤 6 − 重复，直到列表被排序

伪码


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);
}

尝试一下

数据结构&算法 插入排序

插入排序

插入排序如何工作？

算法

伪码

实现

数据结构&算法插入排序