算法是如何影響程序編碼方式的 - 基本排序算法

昵稱10504424 2013-12-02

展開全文

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("數(shù)組已經(jīng)達(dá)到最大長(zhǎng)度，無法再插入了。");

            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 統(tǒng)計(jì)函數(shù)
        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

再加入一個(gè)計(jì)算所用時(shí)間的類，用來計(jì)算Min/Max函數(shù)所運(yùn)行的時(shí)間

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 + ", 共花費(fèi)了 " + tm.Elapsed.TotalMilliseconds + " 毫秒");
        }
    }

我們先來寫個(gè)最簡(jiǎn)單的，沒有排序功能的demo程序，來看看當(dāng)沒有排序時(shí)的性能：

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值");

運(yùn)行結(jié)果：

然后，我們?cè)贋檫@個(gè)CArray編寫一個(gè)排序功能，如下：

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;//新增加的一個(gè)私有成員
        }

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值");

運(yùn)行結(jié)果圖：

Min函數(shù)的執(zhí)行效率在排序前后相差了379倍。

其實(shí)到這里大家都懂了，但是又出現(xiàn)了另外一個(gè)話題：排序函數(shù)怎么花了這么長(zhǎng)時(shí)間？

這就牽涉到各種排序算法的比較了，以后再講。

有人肯定會(huì)說，這些排序算法在C#中都已經(jīng)被ms實(shí)現(xiàn)了，所以沒用！

對(duì)，是被實(shí)現(xiàn)了，但本篇是講現(xiàn)實(shí)項(xiàng)目中，算法是如何影響程序的
ms實(shí)現(xiàn)的是一些常用算法，要是遇到了非常用，非標(biāo)準(zhǔn)的算法才能解決的問題呢？比如各種算法的變種，你不會(huì)要等ms出一個(gè)更新才用吧

自省推動(dòng)進(jìn)步，視野決定未來。
心懷遠(yuǎn)大理想。
為了家庭幸福而努力。
A2D科技，服務(wù)社會(huì)。
A2D Framework(Alpha)

1. Cache System(本地緩存與分布式緩存共存、支持Memcache和Redis、支持貼標(biāo)簽形式(類似Spring 3.x的Cache形式))
2. Event System(本地事件與分布式事件分發(fā))
3. IoC(自動(dòng)匹配功能，實(shí)例數(shù)量限制功能)
4. Sql Dispatcher System(支持ADO.NET及EF)
5. Session System(分布式Session系統(tǒng))
6. 分布式Command Bus(MSMQ實(shí)現(xiàn)，解決4M限制，支持Session的讀取)
7. 規(guī)則引擎

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自：昵稱10504424 > 《工作》

舉報(bào)/認(rèn)領(lǐng)