跳到主要内容

插入排序算法

提示
  1. 基本概念：插入排序通过比较并移动元素，每次迭代将一个未排序的元素放置到正确位置，类似于整理纸牌。
  2. 排序过程：假设第一个元素已排序，逐个取出剩余元素与左侧已排序元素比较，插入到适当位置，保持左侧始终排序。
  3. 时间和空间复杂性：最佳情况时间复杂度为 O(n)，最差和平均为 O(n²)；空间复杂度为 O(1)，算法是稳定的。

插入排序是一种排序算法，它在每次迭代中将一个未排序的元素放置到合适的位置。

插入排序的工作方式类似于我们在纸牌游戏中对手中的牌进行排序。

我们假设第一张牌已经排好序，然后选择一张未排序的牌。如果未排序的牌大于手中的牌，它就被放在右边，否则放在左边。以同样的方式，其他未排序的牌被取出并放在它们正确的位置。

插入排序采用类似的方法。

插入排序的工作原理​

假设我们需要对以下数组进行排序。

插入排序步骤

  1. 数组中的第一个元素被认为是已排序的。取出第二个元素，并单独存储在 key 中。

    比较 key 与第一个元素。如果第一个元素大于 key，那么 key 被放置在第一个元素的前面。

    插入排序步骤

  2. 现在，前两个元素已经排序。

    取出第三个元素，将其与左侧的元素进行比较。将它放在比它小的元素的后面。如果没有比它小的元素，那么将它放在数组的开始位置。 插入排序步骤

  3. 类似地，将每个未排序的元素放置在其正确的位置。 插入排序步骤

插入排序步骤

插入排序算法​


insertionSort(array)
  标记第一个元素为已排序
  for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSort

Python、Java 和 C/C++ 中的插入排序​

Python Java C C++

# Python 中的插入排序

def insertionSort(array):

    for step in range(1, len(array)):
        key = array[step]
        j = step - 1

        # 比较 key 与它左边的每个元素，直到找到一个比它小的元素
        # 若要进行降序排列，将 key<array[j] 改为 key>array[j]
        while j >= 0 and key < array[j]:
            array[j + 1] = array[j]
            j = j - 1

        # 将 key 放在刚好比它小的元素之后
        array[j + 1] = key

data = [9, 5, 1, 4, 3]
insertionSort(data)
print('按升序排序的数组:')
print(data)
// Java 中的插入排序

import java.util.Arrays;

class InsertionSort {

  void insertionSort(int array[]) {
    int size = array.length;

    for (int step = 1; step < size; step++) {
      int key = array[step];
      int j = step - 1;

      // 比较 key 与它左边的每个元素，直到找到一个比它小的元素
      // 若要进行降序排列，将 key<array[j] 改为 key>array[j]
      while (j >= 0 && key < array[j]) {
        array[j + 1] = array[j];
        --j;
      }

      // 将 key 放在刚好比它小的元素之后


      array[j + 1] = key;
    }
  }

  // 驱动代码
  public static void main(String args[]) {
    int[] data = { 9, 5, 1, 4, 3 };
    InsertionSort is = new InsertionSort();
    is.insertionSort(data);
    System.out.println("按升序排序的数组: ");
    System.out.println(Arrays.toString(data));
  }
}
// 在C中的插入排序

#include <stdio.h>

// 打印数组的函数
void printArray(int array[], int size) {
  for (int i = 0; i < size; i++) {
    printf("%d ", array[i]);
  }
  printf("\n");
}

void insertionSort(int array[], int size) {
  for (int step = 1; step < size; step++) {
    int key = array[step];
    int j = step - 1;

    // 比较key与它左边的每个元素，直到找到一个比它小的元素。
    // 若要按降序排序，请将key < array[j]更改为key > array[j]。
    while (key < array[j] && j >= 0) {
      array[j + 1] = array[j];
      --j;
    }
    array[j + 1] = key;
  }
}

// 主函数
int main() {
  int data[] = {9, 5, 1, 4, 3};
  int size = sizeof(data) / sizeof(data[0]);
  insertionSort(data, size);
  printf("按升序排列的排序数组：\n");
  printArray(data, size);
}
// 在C++中的插入排序

#include <iostream>
using namespace std;

// 打印数组的函数
void printArray(int array[], int size) {
  for (int i = 0; i < size; i++) {
    cout << array[i] << " ";
  }
  cout << endl;
}

void insertionSort(int array[], int size) {
  for (int step = 1; step < size; step++) {
    int key = array[step];
    int j = step - 1;

    // 比较key与它左边的每个元素，直到找到一个比它小的元素。
    // 若要按降序排序，请将key < array[j]更改为key > array[j]。
    while (key < array[j] && j >= 0) {
      array[j + 1] = array[j];
      --j;
    }
    array[j + 1] = key;
  }
}

// 主函数
int main() {
  int data[] = {9, 5, 1, 4, 3};
  int size = sizeof(data) / sizeof(data[0]);
  insertionSort(data, size);
  cout << "按升序排列的排序数组：\n";
  printArray(data, size);
}

插入排序复杂性​

| **时间复杂性**       |       |
| -------------------- | ----- |
| 最佳                | O(n)  |
| 最差                | O(n2) |
| 平均                | O(n2) |
| **空间复杂性**       | O(1)  |
| ---                  | ---   |
| **稳定性**           | 是    |
| ---                  | ---   |

**时间复杂性**

- **最坏情况复杂性:** `O(n2)`
  假设一个数组按升序排列，而你想要将它按降序排列。在这种情况下，最坏情况复杂性会发生。

    每个元素都必须与其他每个元素进行比较，因此对于每个第n个元素，进行`(n-1)`次比较。

    因此，总的比较次数 = `n*(n-1) ~ n2`

- **最佳情况复杂性:** `O(n)`
  当数组已经排序好时，外部循环运行了`n`次，而内部循环根本不运行。所以，只有`n`次比较。因此，复杂性是线性的。
- **平均情况复杂性:** `O(n2)`
  当数组的元素是混乱的（既不升序也不降序）时会发生。

**空间复杂性**

空间复杂性为`O(1)`，因为使用了一个额外的变量`key`。

## 插入排序的应用

插入排序在以下情况下使用：

- 数组中的元素较少
- 仅剩下少量元素需要排序

## 类似的排序算法

1. [冒泡排序](/tutorials/dsa/bubble-sort)
2. [快速排序](/tutorials/dsa/quick-sort)
3. [归并排序](/tutorials/dsa/merge-sort)
4. [选择排序](/tutorials/dsa/selection-sort)
最后于 更新