算法初探 之 排序算法

摘《李开复：算法的力量》 : 算法是计算机科学领域最重要的基石之一，但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解，认为学计算机就是学各种编程语言，或者认为，学习最新的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学，但是学习计算机算 法和理论更重要，因为计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等 。

许多计算机科学家认为，排序算法是算法学习中最基本的问题。那么我们就从排序这类算法开始，去看看算法究竟是什么。

排序算法解决的是一类什么具体问题呢？

输入 :n 个数的序列 <a1,a2,a3,...,an>

输出 : 输入序列的一个重排 <a'1,a'2,a'3,...,a'n>, 使得 a'1<=a'2<=a'3<=...<=a'n

输入序列通常是一个 n 元数组，但也可能由其他形式来表示，如链表。

对于这个问题，我们可以很容易联想到日常生活中的许多例子。那么我们解决这个问题的第一个思路便可以从日常生活中获得。

插入排序，这是一个对少量元素进行排序的有效算法。其工作机理和很多人打牌时，整理手中牌时的做法差不多。在开始摸牌时，我们的左手是空的，牌面朝下的放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌合适的位置，要将它与手中已有的每一张牌从右向左地进行比较。无论在什么时候，左手中的牌都是排好序的，而这些牌原先都是桌上那副牌里最顶上的一些牌。

// 主方法

INSERTION-SORT(A)

    // 从桌面上一次次取牌

     for j ← 2 to length[A]

    do

                    // 取一张牌到右手 key

                       key ← A[j]

                                // 眼睛注意的位置（将要比较的位置）

                                i ← j – 1

                                // 开始寻找合适的位置

                                while i > 0 and A[i] > key

                                do

                                        // 微调左手中的已经排好顺序的牌

          A[i + 1] ← A[i]

          // 移动眼睛，转换比较的对象

                                        i ← i – 1

                                        // 将右手中的牌放在左手牌中合适的位置上

                                 A[i + 1] ← key

 

大概的思路已经在脑子中形成了，剩下的是简单的工作：将思路转化为实实在在的代码。在这里我用 java 编写了一个静态方法。关于这个算法的具体证明过程详见《 Introduction to Algorithms 》 .

  /** */ /**

*InsertionSort

*The time limit of this sort is O(n^2)

*<strong>O(n^2)</strong>

* @param  element will be sorted

*在这段代码中使用了java的范型以及一个对象接口，详细情况可以参见java相关教材

*/

public   static   < Type  extends  Comparable >   void  insertionSort(Type element[]) ... {

for ( int  j = 1 ;j < element.length;j ++ ) ... {

Type key  =  element[j];

int  i  =  j - 1 ;

while ( (i >= 0 ) && (element[i].compareTo(key) > 0 )) ... {

element[i + 1 ]  =  element[i];

i -- ;

}

element[i + 1 ]  =  key;

}

}

 

如同大家打牌一样，很多人熟能生巧整理手中的牌时又准又快，而有些人却费时费力。那么一个算法也是友好有坏，在这里我只给出相关的评价指数，至于具体规定可参见相关书籍。

这个算法的时间复杂度为 O(n^2) ，空间复杂度为 O(n). 关于“ O” 符号可以在微积分类书籍上找到更为详尽的解释。

科学技术不断进步，很多新的算法应运而生。在这里再介绍一种排序算法。它在时间复杂度上有了具大提高，空间上却付出了两倍的代价。

合并排序，一种利用了“分治策略”的排序方法。分治策略：将原问题划分成 n 个规模较小而结构简单与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。排序算法就是借助了这种思想，本质是：从中间把数组分成元素个数尽量相等的两半，分别对他们进行排序，然后再合并两个有序表。整个问题最困难的地方便是合并两个有序表，在这里我们着重看看这个过程。

再举打牌这个例子 , 假设有两堆牌正 面朝上地放在桌上，每一堆都是已经排好顺序的，最小的牌在最上面。我们希望把这两堆牌合并成一个排好序的输出堆，面朝下地放在桌上。基本步骤包括在面朝上的两堆牌中，选取顶上两张牌中较小的一张，将其取出后面朝下地放入输出堆中。重复这个步骤，直到某一堆为空为止。

     /** */ /**

     *Merge used in the mergeSort

     *<strong>O(n)</strong>

     * @param  element Type[] the elements to be merged

     * @param  p int the begin of the  first elements

     * @param  q int the end of the first elements

     * @param  r int the end of the second elements

      */

     private   static   < Type  extends  Comparable >   void  merge(Type element[], int  p, int  q, int  r) ... {

            // 确定两堆牌的起始位置
         int  nl     =     q - p + 1 ;

         int  nr     =     r - q;

        

            // 新建两个输入堆用于存放待组合牌
        Type[] lElement,rElement;

        lElement     =     (Type[])java.lang.reflect.Array.newInstance(element.getClass().getComponentType(),nl);

        rElement     =     (Type[])java.lang.reflect.Array.newInstance(element.getClass().getComponentType(),nr);

                

            // 做记录处理
         for ( int  i = 0 ;i < nl;i ++ ) ... {

            lElement[i]     =     element[p + i];

        }

         for ( int  i = 0 ;i < nr;i ++ ) ... {

            rElement[i]     =     element[q + i + 1 ];

        }

        

            // 开始取牌
         int  i = 0 ,j = 0 ;

         int  k     =     p;

            // 逐个比较，一直到一个堆为空
         while ((i < nl) && (j < nr)) ... {

             if (lElement[i].compareTo(rElement[j]) <= 0 ) ... {

                element[k]     =     lElement[i];

                i ++ ;

            } else ... {

                element[k]     =     rElement[j];

                j ++ ;

            }

            k ++ ;

        }

        

            // 处理某一堆中 剩下的牌
         while (i < nl) ... {

            element[k]     =     lElement[i];

            i ++ ;

            k ++ ;

        }

         while (j < nr) ... {

            element[k]     =     rElement[j];

            j ++ ;

            k ++ ;

        }

    }

 

这个算法的时间复杂度为 O(n log2 n), 空间复杂度为 O(2n) ＝ O(n).

至此两个算法的介绍结束，我们将这类算法扩大化，从中取出根本的东西。

数据信息中的逆序对