首页 > > 程序设计 > C/C++ >

算法是如何影响程序编码方式的 - 基本排序算法

2018-06-18 03:44:49来源：未知阅读 ()

我们的目标是从一个int的Array中，找出最小值。

作为demo程序，我们先增加一个类，用来模拟Array，如下定义：

class CArray
    {
        const int DefaultCapacity = 100;

        private int[] array;
        private int curPosition = -1;


        public CArray()
        { 
            this.array=new int[DefaultCapacity];
            curPosition = -1;
        }
        public CArray(int capacity)
        {
            this.array = new int[capacity];
            curPosition = -1;
        }
        public void Insert(int value)
        {
            if (curPosition + 1 >= array.Length)
                throw new Exception("数组已经达到最大长度，无法再插入了。");

            curPosition++;
            array[curPosition] = value;
        }
        public void Clear()
        {
            curPosition = -1;
            this.array=new int[this.array.Length];
        }

        public void Display()
        {
            Console.WriteLine();
            for (var i = 0; i < this.curPosition; i++)
                Console.Write(string.Format("{0}, ", this.array[i]));
        }

        #region 统计函数
        public int Max()
        { 
            int maxValue=this.array[0];
            for (var i = 1; i <= this.curPosition; i++)
                if (maxValue < this.array[i])
                    maxValue = this.array[i];
            return maxValue;
        }
        public int Min()
        {
            int minValue = this.array[0];
            for (var i = 1; i <= this.curPosition; i++)
                if (minValue > this.array[i])
                    minValue = this.array[i];
            return minValue;
        }
        #endregion

再加入一个计算所用时间的类，用来计算Min/Max函数所运行的时间

class Timing
    {
        Stopwatch tm = new Stopwatch();

        public void Start()
        { 
            GC.Collect();
            GC.WaitForPendingFinalizers();

            tm.Reset();
            tm.Start();
        }

        public void Stop()
        {
            tm.Stop();
        }

        public void Display(string msg)
        {
            Console.WriteLine(msg + ", 共花费了 " + tm.Elapsed.TotalMilliseconds + " 毫秒");
        }
    }

我们先来写个最简单的，没有排序功能的demo程序，来看看当没有排序时的性能：

int count = 19999;

CArray aryObj = new CArray(count);

Random rnd = new Random(DateTime.Now.Second);
for (var i = 0; i < count; i++)
        aryObj.Insert((int)(rnd.NextDouble() * 100000) + 1);

Timing t = new Timing();
t.Start();
aryObj.Min();
t.Stop();
t.Display("排序前Min值");

运行结果：

然后，我们再为这个CArray编写一个排序功能，如下：

public void BubbleSort()
        {
            int temp;
            for (var i = this.curPosition; i >= 1; i--)
            {
                for (var j = 0; j <= i-1; j++)
                {
                    if (this.array[j] > this.array[i])
                    { 
                        temp=this.array[i];
                        this.array[i] = this.array[j];
                        this.array[j]=temp;
                    }
                }
            }
            sorted = true;//新增加的一个私有成员
        }

public int Min()//修改
        {
            if (sorted)
                return this.array[0];

            int minValue = this.array[0];
            for (var i = 1; i <= this.curPosition; i++)
                if (minValue > this.array[i])
                    minValue = this.array[i];
            return minValue;
        }

然后修改主程序如下

int count = 19999;

                CArray aryObj = new CArray(count);

                Random rnd = new Random(DateTime.Now.Second);
                for (var i = 0; i < count; i++)
                    aryObj.Insert((int)(rnd.NextDouble() * 100000) + 1);

                Timing t = new Timing();
                t.Start();
                aryObj.Min();
                t.Stop();
                t.Display("排序前Min值");

                t.Start();
                aryObj.BubbleSort();
                t.Stop();
                t.Display("冒泡排序");

                t.Start();
                aryObj.Min();
                t.Stop();
                t.Display("排序后Min值");