`
阿尔萨斯
  • 浏览: 4109158 次
社区版块
存档分类
最新评论

算法 - 插入排序(C#)

 
阅读更多

// --------------------------------------------------------------------------------------------------------------------
// <copyright file="Program.cs" company="Chimomo's Company">
//
// Respect the work.
//
// </copyright>
// <summary>
//
// The insertion sort.
//
// 直接插入排序(straight insertion sort)的做法是:
// 每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。
// 第一趟比较前两个数,然后把第二个数按大小插入到有序表中;第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
// 直接插入排序属于稳定的排序,最坏时间复杂性为O(n^2),空间复杂度为O(1)。
// 直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值插入其后一位置,结束该次循环。
// 值得注意的是,我们必需用一个存储空间来保存当前待比较的数值,因为当一趟比较完成时,我们要将待比较数值插入比它小的数值的后一位。插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是:每步将一个待排序的记录按其关键字的大小插入到前面已经排序的序列中的适当位置,直到全部记录插入完毕为止。
//
// </summary>
// --------------------------------------------------------------------------------------------------------------------

namespace CSharpLearning
{
    using System;

    /// <summary>
    /// The program.
    /// </summary>
    public static class Program
    {
        /// <summary>
        /// The main.
        /// </summary>
        public static void Main()
        {
            int[] a = { 1, 4, 6, 2, 8, 7, 9, 3, 5, 10 };
            Console.WriteLine("Before Insertion Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }

            Console.WriteLine("\r\n\r\nIn Insertion Sort:");
            InsertionSort(a);
            Console.WriteLine("\r\nAfter Insertion Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }

            Console.WriteLine(string.Empty);
        }

        /// <summary>
        /// The insertion sort.
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        public static void InsertionSort(int[] a)
        {
            // 从第二个元素开始迭代。
            for (int i = 1; i < a.Length; i++)
            {
                int tmp = a[i]; // 存储待插入的元素。
                int j = i - 1;

                // 从当前元素往右边寻找插入点。
                while (a[j] > tmp)
                {
                    a[j + 1] = a[j]; // 后移。
                    j--;
                    if (j == -1)
                    {
                        break;
                    }
                }

                a[j + 1] = tmp; // 在前面,该后移的元素已经后移了,会留下一个空位置,这个位置就是待插入元素的插入点。

                // 打印数组。
                foreach (int k in a)
                {
                    Console.Write(k + " ");
                }

                Console.WriteLine(string.Empty);
            }
        }
    }
}

// Output:
/*
Before Insertion Sort:
1 4 6 2 8 7 9 3 5 10

In Insertion Sort:
1 4 6 2 8 7 9 3 5 10
1 4 6 2 8 7 9 3 5 10
1 2 4 6 8 7 9 3 5 10
1 2 4 6 8 7 9 3 5 10
1 2 4 6 7 8 9 3 5 10
1 2 4 6 7 8 9 3 5 10
1 2 3 4 6 7 8 9 5 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

After Insertion Sort:
1 2 3 4 5 6 7 8 9 10
*/
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics