排序研究二 | iJohn.org
12th
三月 2007

排序研究二
爱因万江斯坦@2007年03月12日 23:46 Post in 性能 评论 »

五.归并排序
归并排序比前面讲到的排序方法要有效的多.冒泡排序,插入排序和选择排序要用O(N^2)时间,而归并只要O(N*logN).如果N是10000,那么N^2就是100000000,而N*logN只是40000,如果为这么多数据项排序用并归排序的话需要40秒,那么用插入排序则需要将近28个小时.
但归并排序有个最大的缺点,就是它需要在内存能装下一个大小等于被排序的数据项数目的数组.

在研究归并排序前,先要说说什么是归并.
假设有两个有序数组,数组A有4个数据,数组B有6个数据,它们要归并到数组C中,那么我们就要为C初始10个空的存储空间.

然后,对A的第一个数据,和B的第一个数据进行比较,把较小的数据项被复制到数组C中.再把未复制的数据与另一个数组的第二个数据进行比较,再把比较小的数据复制到C中,依次类推.

                                  // 把数组A和B归并到数组C
     public static void merge( int[] arrayA, int sizeA,
                               int[] arrayB, int sizeB,
                               int[] arrayC )
      {
      int aDex=0, bDex=0, cDex=0;

      while(aDex < sizeA && bDex < sizeB)  // 两个数组均不为空时
         if( arrayA[aDex] < arrayB[bDex] )
            arrayC[cDex++] = arrayA[aDex++];
         else
            arrayC[cDex++] = arrayB[bDex++];

      while(aDex < sizeA)                  // 数组B空了,
         arrayC[cDex++] = arrayA[aDex++];  // 数组A还没空

      while(bDex < sizeB)                  // 数组A空了,
         arrayC[cDex++] = arrayB[bDex++];  // 数组B还没空
      }  // end merge()

现在来看看归并排序的思想,是把一个数组分成两半,排序每一半,然后用上面的归并思想把数组的两半归并成一个有序的数组.但如何对每一部分排序呢,就要用到递归了,把每一半都分成两个1/4,对每个1/4部分排序,然后把它们归并成一个有序的一半,再以此类推不停的分解问题,直到得到了基值条件:只有一个数据项的数组是有序的.

public void mergeSort()          // 归并排序组程序,theArray是待排序数组,nElems是其长度
{                              // 建一个存放有序结果的初始数组
      long[] workSpace = new long[nElems];
      recMergeSort(workSpace, 0, nElems-1);
      }

 private void recMergeSort(long[] workSpace, int lowerBound,
                                               int upperBound)
      {
      if(lowerBound == upperBound)            // 如果就一个了,没
         return;                              // 必要排序了
      else
         {                                    // 找到中间点
         int mid = (lowerBound+upperBound) / 2;
                                              // 对左边的一半排序
         recMergeSort(workSpace, lowerBound, mid);
                                              // 对右边的一半排序
         recMergeSort(workSpace, mid+1, upperBound);
                                             // 合并两个排好序的一半
         merge(workSpace, lowerBound, mid+1, upperBound);
         }
      }  

 //-----------------------------------------------------------
   private void merge(long[] workSpace, int lowPtr,     //lowPtr:前半部分的子数组的开始;
                           int highPtr, int upperBound) //highPtr:后半部分子数组的开始位置;
      {                                                 //upperBound:后半部分子数组的上界
      int j = 0;
      int lowerBound = lowPtr;
      int mid = highPtr-1;
      int n = upperBound-lowerBound+1; 

      while(lowPtr <= mid && highPtr <= upperBound) //把theArray数组中前半部分和后半部分
         if( theArray[lowPtr] < theArray[highPtr] ) //中小的数据复制到workSpace中
            workSpace[j++] = theArray[lowPtr++];
         else
            workSpace[j++] = theArray[highPtr++];

      while(lowPtr <= mid)
         workSpace[j++] = theArray[lowPtr++];

      while(highPtr <= upperBound)
         workSpace[j++] = theArray[highPtr++];

      for(j=0; j<n; j++)
         theArray[lowerBound+j] = workSpace[j];
      }  // end merge()
   //-----------------------------------------------------------

workspace数组的创建在mergeSort()中实现,是因为如果在recMergeSort()中创建数组会在每一次递归调用中都创建新数组,这是没有效率的.

但是一个算法作为一个递归的方法通常从概念上很容易理解,但是,在实际的运用中证明递归算法的效率不太高,有时可以用一个基于栈的方法来替代它,有兴趣的朋友可以继续研究.

六,希尔排序
希尔排序不像快速排序和其他时间复杂度为O(N*logN)的排序算法那么快,因此对非常大的文件排序,它不是最优的.但是希尔排序比选择排序和插入排序这种时间复杂度为O(N^2)的排序算法还是要快得多.另外 ,希尔排序算法的代码既短又简单.
我们先看看插入排序带来的问题.假设一个很小的数据项在很靠近右端的位置上,这里本来应该是值比较大的数据项所在的位置.把这个小数据项移动到在左边的正确位置上,所有的中间数据都必须向右移一位.这个步骤对每一个数据项都执行了将近N次的复制.

希尔排序是通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项能大跨度地移动.
进行希尔排序时数据项之间的间隔被称为增量,并且习惯上用字母h来表示.
如对包含10个数据项的数组进行排序,我们设h=4,我们则先对0,4,8位置上的元素排序,然后再对1,5,9号数据项进行排序.这个排序过程持续进行,直到所有的数据项都已经完成了4增量排序,也就是说所有间隔为4的数据项之间都已经有序.
然后我们就可以进行普通的插入排序,即1-增量排序.
在完成以h为增量的希尔排序后,所有元素离它在最终有序序列中的位置都比较近,这就是数据"基本有序"的含义.这也正是希尔排序的奥秘所在.
接着上面的例子4-增量排序和1-增量排序结合起来应用,比前面只用普通的插入排序要快得多.
那对于希尔排序中的h间隔如何取呢,一般我们选用Knuth序列:h初值为1,然后应用h=h*3+1生成序列:1,4,13,40,121,364,…当间隔大于数组大小时,这个过程停止.

 public void shellSort(int []a)
      {
      int inner, outer;
      long temp;

      int h = 1;                     // 间隔h的初始值是1
      while(h <= a.length/3)
         h = h*3 + 1;                // (1, 4, 13, 40, 121, 等等)

      while(h>0)                     // h递减,直到h=1
         {
                                     // h-增量排序
         for(outer=h; outer<a.length; outer++)  //即插入排序
            {
            temp = a[outer];
            inner = outer;
            while(inner > h-1 && a[inner-h] >=  temp)
               {
               a[inner] = a[inner-h];
               inner -= h;
               }
            a[inner] = temp;
            }  // end for
         h = (h-1) / 3;              // h递减
         }  // end while(h>0)
      }  // end shellSort()

迄今为止,除了在一些特殊情况下,还没有人能够从理论上分析希尔排序的效率,有各种各样基于试验的评估,估计它的时间级从O(N^3/2)到O(N^7/6).

七,快速排序
讲快速排序,就要先说一下划分,因为划分是快速排序的根本机制.
划分就是把数组分为两组,使所有关键字大于特定值的数据项在一组,使所有关键字小于特定值的数据项在另一组.
完成划分,数据还不能称为有序,也只是比没有划分前更接近有序了.同时划分也是不稳定的,因为它往往会颠倒数组中一些数据的顺序.

 public int partitionIt(int left, int right, long pivot)
       {
       int leftPtr = left - 1;           // 左边
       int rightPtr = right + 1;         // 右边
       while(true)
          {
          while(leftPtr < right &&       // 找出左边比pivot大的元素时停止
                theArray[++leftPtr] < pivot)
             ;  // (nop)

          while(rightPtr > left &&       // 找出右边比pivot小的元素时停止
                theArray[--rightPtr] > pivot)
             ;  // (nop)
          if(leftPtr >= rightPtr)        // 左右相逢
             break;                      // 划分结束
          else                           // 左右未逢
             swap(leftPtr, rightPtr);    // 交换元素
          }  // end while(true)
	  swap(leftPtr, rightPtr);        //将pivot放到正确点
       return leftPtr;                   //返回相逢点
       }

划分算法主要是两个指针,分别指向数组的两头.在左边的指针,leftPtr向右移动,而在右边的rightPtr则向左移动.实际上,leftPtr初始化时是在第一数据的左边一位,rightPtr是在最后一个数据项的右边一位,这是因为它们在执行前都要分别的加一和减一.
当leftPtr遇到比待比较数据小的数据项时,它继续右移,但遇到比待比较数大时,它就停止.类似的,当rightPtr遇到大于待比较数的数据项时,它继续左移,但是当遇到比待比较数小时,也停止.两个内层while循环,第一个用于leftPtr,第二个用于rightPtr,控制左右两部分的扫描过程.
当这两个循环都退出之后,也就是leftPtr与rightPtr都指向左右两边位置不对的数据项上,所以交换这两个数据.交换结束之后,继续移动两个指针,再停止,再交换.这一切都包含在一个外部循环中.

快速排序是最流行的算法,在大多数情况下,快速排序都是最快的,执行时间为O(N*logN)级.这也只是对内部排序而言,对于在磁盘文件中的数据进行排序,其他的排序算法可能更好.
快速排序算法本质上是通过把一个数组划分为两个子数组,然后递归地调用自身为每一个子数组进行快速排序.

 public void recQuickSort(int left, int right)
      {
      if(right-left <= 0)              // if size <= 1,
          return;                      //    already sorted
      else                             // size is 2 or larger
         {
         long pivot = theArray[right];      // 选择最右端的元素为待比较数
                                            // 划分
         int partition = partitionIt(left, right, pivot);
         recQuickSort(left, partition-1);   // 排序左边
         recQuickSort(partition+1, right);  // 排序右边
         }
      }  // end recQuickSort()

Leave a Reply