插入排序算法

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

这是一种基于比较的原地排序算法。在此，维护一个始终排序的子列表。例如，数组的下半部分保持排序状态。要“插入”到此排序子列表中的元素必须找到其适当的位置，然后将其插入到该位置。因此得名：**插入排序**。

顺序搜索数组并将未排序的项目移动并插入到排序的子列表（在同一个数组中）。此算法不适用于大型数据集，因为其平均和最坏情况的复杂度为 Ο(n²)，其中n 是项目的数量。

插入排序算法

现在我们对这种排序技术的运作方式有了更全面的了解，因此我们可以推导出一些简单的步骤来实现插入排序。

**步骤 1** - 如果是第一个元素，则已排序。返回 1;

**步骤 2** - 选择下一个元素

**步骤 3** - 与排序子列表中的所有元素进行比较

**步骤 4** - 将排序子列表中所有大于要排序的值的元素进行移位

**步骤 5** - 插入该值

**步骤 6** - 重复此过程，直到列表排序

伪代码

Algorithm: 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 个元素的排序子列表。

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

实现

由于插入排序是一种原地排序算法，因此算法的实现方式是，将迭代选择为数组中每个元素的关键元素与后续元素进行比较以检查其位置。如果关键元素小于其后续元素，则不进行交换。否则，将交换这两个比较的元素，并将下一个元素选择为关键元素。

插入排序已在四种编程语言中实现，分别是 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];//take value
      j = i;
      while(j > 0 && array[j-1]>key) {
         array[j] = array[j-1];
         j--;
      }
      array[j] = key; //insert in right place
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; // initialize the array
   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];//take value
      j = i;
      while(j > 0 && array[j-1]>key) {
         array[j] = array[j-1];
         j--;
      }
      array[j] = key; //insert in right place
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; // initialize the array
   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}; //initialize an array
      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];//take value
         int j = i;
         while(j > 0 && arr[j-1]>key) {
            arr[j] = arr[j-1];
            j--;
         }
         arr[j] = key; //insert in right place
      }
      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]