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