2007年3月的归档

五．归并排序
　　归并排序比前面讲到的排序方法要有效的多．冒泡排序，插入排序和选择排序要用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()