插入排序是一种排序算法,它一次获取一个元素并将其插入到数组中的正确位置。继续此过程,直到对数组进行排序为止。
给出了一个用C#演示插入排序的程序,如下所示。
using System; namespace InsertionSortDemo { class Example { static void Main(string[] args) { int[] arr = new int[10] { 23, 9, 85, 12, 99, 34, 60, 15, 100, 1 }; int n = 10, i, j, val, flag; Console.WriteLine("Insertion Sort"); Console.Write("Initial array is: "); for (i = 0; i < n; i++) { Console.Write(arr[i] + " "); } for (i = 1; i < n; i++) { val = arr[i]; flag = 0; for (j = i - 1; j >= 0 && flag != 1; ) { if (val < arr[j]) { arr[j + 1] = arr[j]; j--; arr[j + 1] = val; } else flag = 1; } } Console.Write("\nSorted Array is: "); for (i = 0; i < n; i++) { Console.Write(arr[i] + " "); } } } }
输出结果
上面程序的输出如下。
Insertion Sort Initial array is: 23 9 85 12 99 34 60 15 100 1 Sorted Array is: 1 9 12 15 23 34 60 85 99 100
现在,让我们了解以上程序。
首先,初始化数组,并使用for循环打印其值。可以在以下代码片段中看到-
int[] arr = new int[10] { 23, 9, 85, 12, 99, 34, 60, 15, 100, 1 }; int n = 10, i, j, val, flag; Console.WriteLine("Insertion Sort"); Console.Write("Initial array is: "); for (i = 0; i < n; i++) { Console.Write(arr[i] + " "); }
嵌套的for循环用于实际的排序过程。在外部for循环的每次通过中,当前元素都将插入到其在数组中的正确位置。该过程一直持续到对数组排序为止。在下面的代码片段中可以看到。
for (i = 1; i < n; i++) { val = arr[i]; flag = 0; for (j = i - 1; j >= 0 && flag != 1; ) { if (val < arr[j]) { arr[j + 1] = arr[j]; j--; arr[j + 1] = val; } else flag = 1; } }
最后,显示排序后的数组。在下面的代码片段中可以看到。
Console.Write("\nSorted Array is: "); for (i = 0; i < n; i++) { Console.Write(arr[i] + " "); }