{ Snake @ NET } 废寝忘食的程序工作者.

作为计算机应用专业的学生,个人觉得这个专业在未来是绝对要饿死的.所以如果对计算机研究不深,咱们还是老老实实回家卖香鸡排(注1)都比搞IT赚钱.

自学了1年10个月的ASP.NET平台和C#语言的开发,期间被魔兽世界和各种公务打断了半年多,学了个大概懂得不少架构方面和程序设计方面上的知识.自己也可以算是个超越了"新手上路"级别的程序员了.可是当有一天博客园的大牛之一老赵(注2)在招聘北大青鸟(注:专业IT技能培训学校)毕业的学生时要求他们写一个数组反转的代码,结果令他很失望.老赵一失望,我就快绝望了.

立马要离校实习的我目前虽然看法和这些北大青鸟毕业的学生不一样,但是自己同他们还是有很大的相似之处--能盖空中楼阁.光有花拳绣腿,真正那些底子是一点也没有.最终悲剧的还不是自己.要有浓厚的底蕴你才会洋溢出耐人寻味的芳香.花拳绣腿在专业人士看来就像村姑抹法国香水一样可笑.

所以在老赵的"开化"之下,我开始认真的研究起计算机科学这一门学科与计算机编程有关的科目.其中就包括--算法.(当然还有好多与本次笔记无关的东西)

当然在学习算法之前得熟悉一下基本的数据结构.好在上个学期老师已经教过我们,并且前些日子我也认真的复习了一遍.不过由于它太过简单.个人认为就没必要写一份关于数据结构的笔记了.

关于算法的基本常识,包括时间复杂度,空间复杂度那些我就不罗嗦了,直接上链接.

记得大一学C语言的时候老师教我们用循环控制语法的时候有一个题目就是关于排序的.题目如下:给定一个数组,根据对比数组的某两个元素的大小,有序的重新排列数组.

答案也很简单.就是两个for循环遍历整个数组,对比当前所选的两个元素的大小让他们交换位置.最终完成排序.后来老师告诉我们这叫冒泡排序.这个排序算法的名字很形象.最小的那个数字回像冒泡泡一样从某一个位置慢慢得浮上来.

main()
{
    int a[] = {5,6,2,3,1,9,7,4,8};
    int l=9;
    int i=0,j=0;
    int temp;
    for(;i<l;i++)
    {
        for(;j<l;j++)
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    for(i=0;i<l;i++)
    {
        printf("%d ",a[i]);
    }
    getch();
}

以上为C语言的实现方法.核心代码不多,也就那么11行.但是明显可以看出它的不高效.

上面的2个for表明这个代码要运行"l"的平方次,也就是81次.而且是必须执行81次.

程序就是程序,人可以通过眼睛的观察然后判断,最终的对边的移动最多也不过20次.

那么有什么办法让数字的遍历次数变少呢?一个1962年提出的古老的排序算法(其实一点都不古老,好多现用的算法都是已经诞生了几十年并且历经时间的磨砺)但依旧是世界上最快的算法,它的名字果真名副其实--QuickSort(快速排序),让我有必要与它会一会面.

快速算法是基于分治算法的理论而设计出来的一种排序方法.基本思想是这样的.

(1)在将要排序的数组arr中随便一个位置抽取一个元素作为对比项key.

(2)定义2个变量low,high分别为数组的最低下标和最高下标.

(3)对比key与最高下标的值hiVal.如果hiVal小于key,那么hiVal与key调换位置,否则high-1

(4)对比key与高低下标的值loVal.如果loVal大于key,那么loVal与key调换位置,否则low+1

(5)重复(3)(4)2步,直到所有比key小的元素都在key的左边,比key打的元素都在key的右边.此时整个数组以key为基准分为了2组暂且名为lPart和rPart.

(6)这时再递归(1)~(5)的操作,当然此次递归的数组不是原来我们执行操作的数组arr,而是分组之后lPart和rPart.

由上面的的步骤看来快速排序会将原本的一个数组分割成为2个,2个变为4个,4个变为8个,直到排序完毕.

那么快速算法的时间复杂度是什么呢?教科书上写着:

最糟糕的情况下它与冒泡排序是一样的时间复杂度O(n的平方)

最良好好的情况下它的时间复杂度是O(nlogn)

平均下来它的时间复杂度是O(nlogn)

由于本人高中时期的无知.数学一直没有好好学习.以至于对数学的理解非常吃力.(真是对不起我们可爱的阿满老师)

但是操起计算器计算下这两种算法的耗时量是多少就非常明白了.

假设对比或排序一次总共耗时1秒.并且数组的长度为20,那么

冒泡排序耗时:20*20=400秒

快速排序耗时:20*log20=26秒.

当然实际相差有的时候不是那么明显.我将我的这次对比用C#写成一个小程序并且进行了一次对比(在学校机房里偷偷做的.用的是奢侈的INTEL CPU).结果我也记录了下来那么我就贴在低下.这是一个真实的INTEL核心计算机运行了一千万次冒泡排序和快速排序所耗费的时间统计报告:

-----------------------------------------------------------------------------

Platform Configuration

--CPU: Pentium Dual-Core E5300 @2.60GHz

--MEM: 2GB DDR2

--.NET Framework Version: 2.0

--IDE: SharpDevelop v2.2

Introduction:

--All of the Excute file is the RELEASE version.

--The QuickSort is the original version.

*****10 Million Times of 10 numbers to sort*****

--The Array Elements are: {1,8,7,9,6,5,4,2,10,3}

1     bs10     2626ms

2     bs10     2618ms

3     bs10     2620ms

1     qs10     2650ms

2     qs10     2647ms

3     qs10     2647ms

*****10 Million Times of 20 numbers to sort*****

--The Array Elements are:

{5,7,9,4,6,8,3,1,2,10,14,16,15,13,12,17,19,18,20,11}

1     bs20     8473ms

2     bs20     8468ms

3     bs20     8467ms

1      qs20     6972ms

2     qs20     6971ms

3     qs20     6974ms

*****10 Million Times of 30 numbers to sort*****

--The Array Elements are:

{3,5,8,6,7,9,1,2,4,14,11,18,16,12,15,13,19,17,21,10,20,25,27,23,29,28,22,24,26,30}

1      bs30     18164ms

2      bs30     18164ms

3     bs30      18165ms

-----------------------------------------------------------------------------

不知道够不够严谨.我将会把这次测试的源代码,程序和报告提供下载

最后您可能会问:快速算法的代码在哪里啊!

google百度一大堆呢.不过为了赚点吆喝,我放上微软核心的快速排序代码.这也是我深入了解ASP.NET平台的一个举措.代码如下:

internal static void QuickSort(T[] keys, int left, int right, IComparer<T> comparer)
{
    do
    {
        int a = left;
        int b = right;
        int num3 = a + ((b - a) >> 1);
        ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, a, num3);
        ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, a, b);
        ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, num3, b);
        T y = keys[num3];
        do
        {
            while (comparer.Compare(keys[a], y) < 0)
            {
                a++;
            }
            while (comparer.Compare(y, keys[b]) < 0)
            {
                b--;
            }
            if (a > b)
            {
                break;
            }
            if (a < b)
            {
                T local2 = keys[a];
                keys[a] = keys[b];
                keys[b] = local2;
            }
            a++;
            b--;
        }
        while (a <= b);
        if ((b - left) <= (right - a))
        {
            if (left < b)
            {
                ArraySortHelper<T>.QuickSort(keys, left, b, comparer);
            }
            left = a;
        }
        else
        {
            if (a < right)
            {
                ArraySortHelper<T>.QuickSort(keys, a, right, comparer);
            }
            right = b;
        }
    }
    while (left < right);
}

private static void SwapIfGreaterWithItems(T[] keys, IComparer<T> comparer, int a, int b)
{
    if ((a != b) && (comparer.Compare(keys[a], keys[b]) > 0))
    {
        T local = keys[a];
        keys[a] = keys[b];
        keys[b] = local;
    }
}

最后维基百科上有更完备的快速排序的只是,只是需要你有足够的英语基础:http://en.wikipedia.org/wiki/Quicksort

好了.我的文章写完了.希望能帮到你

---------------------------------------

注1:蔡学镛先生写过一套文章,叫做香鸡排三部曲.我这里随便给一个链接吧,原文链接真的不好找.http://chechunhui.bokee.com/2841263.html

注2:博客园大梁之一:赵劼,个人最为喜欢的程序员之一.非常有学术味道的钻研精神.http://blog.zhaojie.me http://cnblogs.com/jeffreyzhao