C#中的插入排序

插入排序是一种排序算法,它一次获取一个元素并将其插入到数组中的正确位置。继续此过程,直到对数组进行排序为止。

给出了一个用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] + " ");
}