# 插入排序算法 > 原文： [https://www.programiz.com/dsa/insertion-sort](https://www.programiz.com/dsa/insertion-sort) #### 在本教程中，您將學習插入排序的工作原理。 此外，您還將找到使用 C，C++ ，Java 和 Python 進行插入排序的有效示例。 插入排序的工作方式與我們在紙牌游戲中對手牌進行排序的方式類似。 我們假設第一張卡片已經被排序，那么我們選擇一個未排序的卡片。 如果未排序的卡片大于手中的卡片，則將其放置在右側，否則放置在左側。 同樣，其他未排序的卡片也會被拿到正確的位置。 插入排序使用類似的方法。 插入排序是一種排序算法，它在每次迭代中將未排序的元素放置在其合適的位置。 * * * ## 插入排序如何工作？ 假設我們需要對以下數組進行排序。  初始數組 1. 假定數組中的第一個元素已排序。 取第二個元素并將其分別存儲在`key`中。 將`key`與第一個元素進行比較。 如果第一個元素大于`key`，則將`key`放在第一個元素的前面。  如果第一個元素大于`key`，則將`key`放在第一個元素的前面。 2. 現在，對前兩個元素進行排序。 取第三個元素并將其與左側的元素進行比較。 將其放置在比其小的元素后面。 如果沒有比它小的元素，則將其放在數組的開頭。  將 1 放在開頭 3. 同樣，將每個未排序的元素放在正確的位置。  將 4 放在 1 后面 [  將 3 放在 1 后面，并對數組進行排序 * * * ## 插入排序算法 ``` insertionSort(array) mark first element as sorted 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++ 示例 ```py # Insertion sort in Python def insertionSort(array): for step in range(1, len(array)): key = array[step] j = step - 1 # Compare key with each element on the left of it until an element smaller than it is found # For descending order, change key<array[j] to key>array[j]. while j >= 0 and key < array[j]: array[j + 1] = array[j] j = j - 1 # Place key at after the element just smaller than it. array[j + 1] = key data = [9, 5, 1, 4, 3] insertionSort(data) print('Sorted Array in Ascending Order:') print(data) ``` ```java // Insertion sort in 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; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change key<array[j] to key>array[j]. while (j >= 0 && key < array[j]) { array[j + 1] = array[j]; --j; } // Place key at after the element just smaller than it. array[j + 1] = key; } } // Driver code public static void main(String args[]) { int[] data = { 9, 5, 1, 4, 3 }; InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); } } ``` ```c // Insertion sort in C #include <stdio.h> // Function to print an array 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; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change key<array[j] to key>array[j]. while (key < array[j] && j >= 0) { array[j + 1] = array[j]; --j; } array[j + 1] = key; } } // Driver code int main() { int data[] = {9, 5, 1, 4, 3}; int size = sizeof(data) / sizeof(data[0]); insertionSort(data, size); printf("Sorted array in ascending order:\n"); printArray(data, size); } ``` ```cpp // Insertion sort in C++ #include <iostream> using namespace std; // Function to print an array 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; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change key<array[j] to key>array[j]. while (key < array[j] && j >= 0) { array[j + 1] = array[j]; --j; } array[j + 1] = key; } } // Driver code int main() { int data[] = {9, 5, 1, 4, 3}; int size = sizeof(data) / sizeof(data[0]); insertionSort(data, size); cout << "Sorted array in ascending order:\n"; printArray(data, size); } ``` * * * ## 復雜度 **時間復雜度** * **最壞情況的復雜度**： `O(n^2)` 假設一個數組是升序的，并且您想按降序對其進行排序。 在這種情況下，最壞情況下的復雜度就會發生。 每個元素都必須與其他每個元素進行比較，因此，對于每第`n`個元素，進行`(n-1)`個比較。 因此，比較總數= `n*(n-1) ~ n^2` * **最佳情況復雜度**： `O(n)` 當數組已經排序時，外循環運行`n`次數，而內循環則根本不運行。 因此，只有`n`個比較。 因此，復雜度是線性的。 * **平均情況復雜度**： `O(n^2)` 當數組的元素處于混亂順序（既不升也不降）時，會發生這種情況。 **空間復雜度** 空間復雜度為`O(1)`，因為使用了額外的變量`key`。 * * * ## 插入排序應用 在以下情況下使用插入排序： * 數組包含少量元素 * 僅剩下一些要排序的元素