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