什么是插入排序？
插入排序（Insertion Sort） 是一種簡單且逐步構建有序序列的排序算法。它的思想是將數組分為兩部分：已排序的部分和未排序的部分。初始時，已排序部分只包含數組的第一個元素，然后逐步將未排序部分的元素插入到已排序部分的正確位置，直到整個數組有序為止。
插入排序的詳細步驟
1、從數組的第二個元素開始，將其視為待插入的元素。
2、將待插入元素與已排序部分的元素進行比較，從已排序部分的末尾開始。
3、如果待插入元素小于已排序部分的某個元素，則將該元素向右移動一位，為待插入元素騰出插入位置。
4、重復步驟 3，直到找到待插入元素的正確位置。
5、將待插入元素插入到正確的位置。
6、重復步驟 2 到 5，直到將所有元素插入到已排序部分。
舉例說明
假設我們有以下待排序的數組：[5, 2, 9, 1, 5, 6]。
第一輪： 將數組中的第一個元素（5）視為已排序部分，然后將下一個元素（2）插入到已排序部分的正確位置。
排序后數組：[2, 5, 9, 1, 5, 6]
第二輪： 將數組中的第一個和第二個元素（2, 5）視為已排序部分，然后將下一個元素（9）插入到已排序部分的正確位置。
排序后數組：[2, 5, 9, 1, 5, 6]
第三輪： 將數組中的前三個元素（2, 5, 9）視為已排序部分，然后將下一個元素（1）插入到已排序部分的正確位置。
排序后數組：[1, 2, 5, 9, 5, 6]
第四輪： 將數組中的前四個元素（1, 2, 5, 9）視為已排序部分，然后將下一個元素（5）插入到已排序部分的正確位置。
排序后數組：[1, 2, 5, 5, 9, 6]
第五輪： 將數組中的前五個元素（1, 2, 5, 5, 9）視為已排序部分，然后將下一個元素（6）插入到已排序部分的正確位置。
排序后數組：[1, 2, 5, 5, 6, 9]
最終，整個數組變得有序：[1, 2, 5, 5, 6, 9]。
示例代碼
#include <stdio.h>void InsertionSortFor(int arr[], int length);void InsertionSortWhile(int arr[], int length);void PrintArray(int arr[], int length);int main()
{int arr[] = {5, 2, 9, 1, 5, 6};/*不可以放在函數內部，當數組作為函數參數傳遞給函數時，數組參數會被轉換為指針類型，因此在函數內部無法通過sizeof操作符獲取數組的長度。*/int length = sizeof(arr) / sizeof(arr[0]);printf("原始數組：");PrintArray(arr, length);InsertionSortFor(arr, length);printf("排序后的數組：");PrintArray(arr, length);return 0;
}void InsertionSortFor(int arr[], int length)
{int i, j, key;for (i = 1; i < length; i++){key = arr[i];// 從當前位置向前遍歷已排序的子數組，找到合適的插入位置for (j = i - 1; j >= 0 && arr[j] > key; j--){arr[j + 1] = arr[j]; // 向右移動元素}arr[j + 1] = key; // 插入元素到正確位置}
}void InsertionSortWhile(int arr[], int length)
{int i, j, key;for (i = 1; i < length; i++){key = arr[i];j = i - 1;// 將比 key 大的元素向右移動while (j >= 0 && arr[j] > key){arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}
}void PrintArray(int arr[], int length)
{int i;for (i = 0; i < length; i++){printf("%d ", arr[i]);}printf("\n");
}
