插入排序算法

插入排序是一种非常简单的方法，用于将数字按升序或降序排序。这种方法遵循增量方法。它可以与玩游戏时整理扑克牌的技术进行比较。

这是一个原地比较排序算法。在此，维护一个始终有序的子列表。例如，数组的较低部分被维护为有序。要“插入”到这个有序子列表中的元素，必须找到其合适的位置，然后插入到那里。因此得名，insertion sort。

数组被顺序搜索，无序项被移动并插入到有序子列表中（在同一数组中）。由于其平均和最坏情况复杂度为 O(n²)，其中 n 是项数，该算法不适合大型数据集。

插入排序算法

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

步骤 1 − 如果是第一个元素，它已经是排序好的。返回 1；

步骤 2 − 挑选下一个元素

步骤 3 − 与有序子列表中的所有元素比较

步骤 4 − 将有序子列表中大于待排序值的元素向后移动

步骤 5 − 插入该值

步骤 6 − 重复直到列表排序完成

伪代码

算法：Insertion-Sort(A)
for j = 2 to A.length
   key = A[j]
   i = j - 1
   while i > 0 and A[i] > key
      A[i + 1] = A[i]
      i = i - 1
   A[i + 1] = key

分析

该算法的运行时间很大程度上取决于给定的输入。

如果给定的数字已经排序，该算法以 O(n) 时间运行。如果给定的数字是逆序，该算法以 O(n²) 时间运行。

示例

我们以一个无序数组为例。

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

它发现 14 和 33 已经处于升序。目前，14 在有序子列表中。

插入排序继续前进并比较 33 和 27。

发现 33 不在正确位置。它将 33 与 27 交换。它还检查有序子列表的所有元素。这里我们看到，有序子列表只有一个元素 14，且 27 大于 14。因此，交换后有序子列表仍然有序。

到现在，有序子列表中有 14 和 27。接下来，它比较 33 和 10。这些值未按排序顺序排列。

因此它们被交换。

然而，交换使得 27 和 10 无序。

因此，我们也交换它们。

再次发现 14 和 10 未按排序顺序排列。

我们再次交换它们。

在第三次迭代结束时，我们有一个包含 4 个项的有序子列表。

这个过程持续进行，直到所有无序值都被包含在有序子列表中。现在我们将看到插入排序的一些编程方面。

实现

由于插入排序是一种原地排序算法，该算法的实现方式是：迭代选择数组中的每个元素作为key element（关键元素），并将其与后续元素比较以确定其位置。如果关键元素小于其后续元素，则不进行交换。否则，比较的两个元素将交换位置，然后选择下一个元素作为关键元素。

插入排序在四种编程语言中实现：C、C++、Java 和 Python −

#include <stdio.h>
void insertionSort(int array[], int size){
   int key, j;
   for(int i = 1; i<size; i++) {
      key = array[i];//取值
      j = i;
      while(j > 0 && array[j-1]>key) {
         array[j] = array[j-1];
         j--;
      }
      array[j] = key; //插入到正确位置
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; // 初始化数组
   printf("Array before Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ",arr[i]);
   printf("\n");
   insertionSort(arr, n);
   printf("Array after Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ", arr[i]);
   printf("\n");
}

Array before Sorting: 67 44 82 17 20 
Array after Sorting: 17 20 44 67 82 

#include<iostream>
using namespace std;
void insertionSort(int *array, int size){
   int key, j;
   for(int i = 1; i<size; i++) {
      key = array[i];//取值
      j = i;
      while(j > 0 && array[j-1]>key) {
         array[j] = array[j-1];
         j--;
      }
      array[j] = key; //插入到正确位置
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; // 初始化数组
   cout << "Array before Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
   insertionSort(arr, n);
   cout << "Array after Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
}

Array before Sorting: 67 44 82 17 20
Array after Sorting: 17 20 44 67 82

import java.io.*;
public class InsertionSort {
   public static void main(String args[]) {
      int n = 5;
      int[] arr = {67, 44, 82, 17, 20}; //初始化数组
      System.out.print("Array before Sorting: ");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
      for(int i = 1; i<n; i++) {
         int key = arr[i];//取值
         int j = i;
         while(j > 0 && arr[j-1]>key) {
            arr[j] = arr[j-1];
            j--;
         }
         arr[j] = key; //插入到正确位置
      }
      System.out.print("Array After Sorting: ");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
   }
}

Array before Sorting: 67 44 82 17 20
Array After Sorting: 17 20 44 67 82

def insertion_sort(array, size):
   for i in range(1, size):
      key = array[i]
      j = i
      while (j > 0) and (array[j-1] > key):
         array[j] = array[j-1]
         j = j-1
      array[j] = key
      
arr = [67, 44, 82, 17, 20]
n = len(arr)
print("Array before Sorting: ")
print(arr)
insertion_sort(arr, n);
print("Array after Sorting: ")
print(arr)

Array before Sorting: 
[67, 44, 82, 17, 20]
Array after Sorting: 
[17, 20, 44, 67, 82]