一、算法简介
插入排序（Insertion Sort）是一种简单直观的排序算法，它将待排序列表分为已排序和未排序两部分，每次从未排序部分中取出一个元素，依次插入到已排序部分的适当位置。
插入排序的基本思想是将未排序部分的第一个元素与已排序部分进行比较，并找到它在已排序部分中的正确位置。然后将其插入到适当位置后，已排序部分的长度增加1，未排序部分的长度减少1。不断重复该过程，直到未排序部分为空，整个序列排序完成。
插入排序的实现通常使用一个for循环和一个while循环嵌套。外层for循环用于遍历未排序部分，内层while循环用于将选中的元素与已排序部分进行比较并找到合适的插入位置。
插入排序是一种稳定的排序算法，它对于小规模数据或基本有序的数据表现良好，但在处理大量乱序数据时，效率较低。由于它的实现简单、易于理解，插入排序也常被用作其他高级排序算法中的子过程。
二、算法实现
以下是插入排序算法的C#实现示例：
public static void InsertionSort(int[] array) { int n = array.Length; for (int i = 1; i < n; i++) { int key = array[i]; int j = i - 1; // 从已排序部分向后比较，寻找插入位置 while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; j--; } array[j + 1] = key; } } public static void InsertionSort(int[] array) { int n = array.Length; for (int i = 1; i < n; i++) { int key = array[i]; int j = i - 1; // 从已排序部分向后比较，寻找插入位置 while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; j--; } array[j + 1] = key; } }
调用示例：
int[] array = { 64, 34, 25, 12, 22, 11, 90 }; InsertionSort(array); Console.WriteLine("排序后的数组："); foreach (int element in array) { Console.Write(element + " "); } int[] array = { 64, 34, 25, 12, 22, 11, 90 }; InsertionSort(array); Console.WriteLine("排序后的数组："); foreach (int element in array) { Console.Write(element + " "); }
这段代码实现了插入排序算法。它使用一个for循环遍历未排序部分，内部的while循环则将选中的元素与已排序部分进行比较，并找到合适的插入位置。将元素插入到正确位置后，已排序部分长度增加，未排序部分长度减小，直到整个序列排序完成。
上述实现只是一种基本示例，未包含额外的优化措施。在实际应用中，可以根据具体需求进行一些优化改进，如改进比较操作、减少元素的移动次数等。
