亲宝软件园·资讯

展开

C#插入排序

Darren Ji 人气:0

在选择排序中,从第一个元素开始,依次遍历数组中的元素,找出当前遍历元素之后的最小元素,与当前遍历元素交换位置,依此类推,是一种由前往后的排序。而在插入排序中,从第二个元素开始,依次遍历数组中的元素,把当前遍历元素与之前的元素进行比较,并插入到之前的某个位置,是一种由后往前的排序。

自定义一个类,里面维护着一个int[]类型数组,通过构造函数定义数组长度并初始化,并提供了打印和插入排序的相关方法。

    public class MyArray
    {
        private static int[] arr;
        private static Random r = new Random();
        public MyArray(int size)
        {
            arr = new int[size];
            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = r.Next(10, 100);
            }
        }
        //插入排序
        public void Sort()
        {
            int insert;
            for (int i = 1; i < arr.Length; i++) //从第二个元素开始遍历
            {
                insert = arr[i];//把当前遍历元素视为插入元素,放到临时变量insert中
                int moveItem = i;//movieItem可以理解为一个动态索引,初始位置在当前遍历元素的索引
                while (moveItem > 0 && arr[moveItem -1] > insert) //如果前面一个元素比插入元素大
                {
                    arr[moveItem] = arr[moveItem - 1];//那就把前面这个元素赋值给后面位置,相当于往后移一位
                    moveItem--;//再把动态索引位置向前移动一位
                }
                arr[moveItem] = insert;
                Print();
            }
        }
        //打印数组元素
        public void Print()
        {
            foreach (var item in arr)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
        }
    }

以上,大致过程是:从数组中第二个元素开始,先把当前遍历元素赋值给一个临时变量,比如说是insert,insert这个变量肯定要插入到当前遍历元素之前的某个位置,如何确定插入位置呢?假设用moveItem变量表示最终要插入的索引位置,先把当前遍历元素的索引赋值给moveItem,如果moveItem-1位置上的元素大于insert,那就把moveItem-1位置上的元素向后移动一位,并把moveItem-1位置的索引赋值给moveItem,insert是要插入到当前的这个moveItem位置吗?不一定。再继续拿当前moveItem位置的前面一个位置上的元素与insert比较,只要是比insert大,就把该位置上的元素向后移动一位,并重新设置moveItem的值,直到停止循环。此时moveItem的值就是insert需要插入的位置。

客户端调用。

    class Program
    {
        static void Main(string[] args)
        {
            MyArray myArray = new MyArray(8);
            Console.WriteLine("排序前:");
            myArray.Print();
            Console.WriteLine("排序后:");
            myArray.Sort();
            Console.ReadKey();
        }
    }

对于插入排序,当依次遍历数组元素时,进行了n-1次迭代,当把第二个元素插入到之前某个位置时进行了1次迭代,当把第三个元素插入到之前某个位置时进行了2次迭代......第n个元素进行了n-1次迭代,以时间复杂度来说,忽略小项和常数项,插入排序基本上是一个平方阶,写成O(n²)。 

到此这篇关于C#实现插入排序的文章就介绍到这了。希望对大家的学习有所帮助,也希望大家多多支持。

加载全部内容

相关教程
猜你喜欢
用户评论