c# - 什么是插入排序？

Question

我是编程新手，刚刚听说过排序。我浏览了排序的基础知识，发现插入排序是最简单的。但问题是我不明白它是什么！你能详细解释一下什么是插入排序以及如何实现它。在 c# 中的实现将不胜感激。

任何帮助将不胜感激！:)

Answer 1

在维基百科上掠夺

插入排序的算法是

 int temp, j;

 for (int i=1; i < vector.length; i++){
   temp = vector[i];
   j = i-1;

   while (j >= 0 && vector[j] > temp){
     vector[j + 1] = vector[j];
     j--;
   }

   vector[j+1] = temp;
 }

Answer 2

对于小数据集的排序，插入排序比我们之前实现的算法（冒泡排序和选择排序）效率更高。当列表部分排序时，主要使用插入排序。我们假设第一个元素已排序。然后我们检查相邻索引的值是否更小或更大。如果值更小，我们将它插入到 index[0] 的左侧，这意味着现在更小的值位于 index[0] 处，如果它大于 index[0] 的原始值，那么我们得到一个 2 的排序列表元素。我们对相邻元素实施相同的方法。然后将其与之前的元素进行比较以创建排序列表。所以基本上 - 你最终会在数组的左侧得到排序列表，而在一个阶段在右侧未排序。

这是插入排序的 C# 实现：

class Program
    {
        static void Main(string[] args)
        {
            int i, j;
            int[] unsortedarrayed = new int[] { 34, 36, 2, 7, 8, 3, 6, 5 };

            for (i = 0; i < unsortedarrayed.Length; i++)
            {
                Console.WriteLine(unsortedarrayed[i]);
            }

            int[] sortedarray = InsertionSorted(unsortedarrayed);

            for (i = 0; i < sortedarray.Length; i++)    
            {
                Console.WriteLine(sortedarray[i]);
            }

            Console.Read();
        }

        public static int[] InsertionSorted(int[] unsortedarrayed)
        {
            for (int i = 1; i < unsortedarrayed.Length; i++)
            {
                int temp = unsortedarrayed[i];
                int j = i - 1;

                while ((j > -1) && (unsortedarrayed[j] > temp))
                {
                    int tempo = unsortedarrayed[j + 1];
                    unsortedarrayed[j + 1] = unsortedarrayed[j];
                    unsortedarrayed[j] = tempo;

                    j = j - 1;
                }
            }

            return unsortedarrayed;
        }
    }

来源：有关更多详细信息，请单击以下链接：1）链接 1 2）链接 2