前面三章已经讨论过一下排序方法——冒泡排序、选择排序和插入排序,这些都容易实现,但是比较慢,另外还提到了递归排序,这种排序方式比简单排序要快,但是它需要的空间是原始数组空间的两倍,通常这是一个严重的缺点。
本章包含了两个高级的排序算法:希尔排序和快速排序。这两种排序时间比简单排序算法快得多。希尔排序大约需要O(N*(logN)^2)时间,快速排序需要O(N*logN)时间,这两种排序算法和归并排序不同,不需要大量的辅助存储空间,希尔排序几乎和归并排序一样容易实现,而快速排序是所有通用排序算法中最快的一种排序算法。本章最后还简要的介绍了基数排序,它是一种不常用但是很有趣的排序算法。
1 希尔排序
希尔排序是由计算机科学家希尔发明的,希尔排序基于插入排序,但是增加了一个新的特性,大大地提高了插入排序的效率。
依靠这个特别的实现机制,希尔排序对于多达几千个数据项的,中等大小规模的数组排序表现良好,希尔排序不像快速排序那样快,因此对于非常大的文件排序,它不是最优选择。希尔排序很容易实现,希尔排序算法代码简短简单。
它在最坏的情况下的执行效率和平均情况下差不多,后面会提到,除非采取了预防措施,否则快速排序在最坏情况下执行效率很差,一些专家比如Sedgwick提倡差不多任何排序工作在开始时都可以使用希尔排序,若在实际中证明它不够快,再改换诸如快速排序这样更高级的排序算法。
1.1 n-增量排序
希尔排序通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项能大跨度地移动,当这些数据项排过一趟序后,希尔排序算法减小数据项的间隔再进行排序,依次进行下去。进行这些排序时数据项之间的间隔被称为增量,并且习惯上用字母h来表示。下面显示一个增量为4对包含10个数据项的数组进行排序的情况。经过排序0,4和8号位的元素已经有序。
当对0,4,8排序完成后,算法右移一步,对1,5,9号元素排序。这个过程持续进行,直到完成4-增量排序,也就是说,间隔为4的数据都会有序。完成4-增量的希尔排序之后,数组可以看出是由4个子数组组成:(0,4,8),(1,5,9),(2,6)和(3,7)
完成4增量排序之后,所有元素离它最终有序序列中的位置都相差不远,这就是数组基本有序的含义,也是希尔排序的奥秘所在。通过创建这种交错的内部有序的数据项集合,把完成排序所必须的工作量降到了最小。
回到插入排序上来,插入排序对基本有序的数组排序是非常有效的,如果插入排序只需要把数据项移动一位或两位,那么算法大概需要O(N)时间,完成4增量排序后,可以进行普通的插入排序,即1增量排序,1-增量和4-增量排序结合起来使用,比仅仅只需普通插入排序快得多。
1.2 减小间隔
上面演示的是是4增量排序,对于更大的数组,开始的间隔应该更大,然后间隔不断减小,直到间隔变成1.这些间隔并不是随意的,而是由一个公式来确定的,即Knuth递归表达式:
h = 3*h + 1 也就是1,4,13,40,121,364,1093.....
显然当间隔超过数组本身的长度的时候,代码是无效的。当确定一个最大的间隔后,就可以用改公式的倒推式来进一步减小间隔:
h = (h - 1)/3
希尔排序比插入排序快很多,原因是:当h值很大时候,数据项每一趟排序需要移动元素的个数很少,但数据项移动的距离很长。这是非常有效率的,当h减小时,每一趟排序需要移动的元素个数增多,但是此时数据项已经接近于它们排序后最终的位置,这对于插入排序可以更有效率。整数这两种情况的结合才使希尔排序效率那么高。
1.3 希尔排序现
希尔排序和插入排序代码差不多,只是在插入排序的开始部分,在合适的位置把h赋值为1,并且添加生成间隔序列的公式。
package chapter7; class ArraySh{ private long[] array; private int nElems; public ArraySh(int max){ array = new long[max]; nElems = 0; } //将值插入数组 public void insert(long value){ array[nElems++] = value; } //输出数组 public void display(){ System.out.print("A:"); for(int i = 0; i < nElems; i++){ System.out.print(array[i] + " "); } System.out.println(); } //希尔排序 public void shellSort(){ int inner, outer; long temp; int h = 1; //将h拉到最大值 while(h <= nElems/3){ h = h*3 + 1; } while(h > 0){ for(outer = h; outer < nElems; outer++){ temp = array[outer]; inner = outer; while(inner > h-1 && array[inner - h] >= temp){ array[inner] = array[inner - h]; inner -= h; } array[inner] = temp; } h = (h - 1)/3; } } }; public class ShellSortApp { public static void main(String[] args){ int maxSize = 10; ArraySh arr; arr = new ArraySh(maxSize); for(int i = 0; i < maxSize; i++){ long n = (int)(java.lang.Math.random()*99); arr.insert(n); } arr.display(); //shell排序 arr.shellSort(); //输出排序结果 arr.display(); } };
输出结果:
A:72 76 21 97 40 33 65 27 65 95
A:21 27 33 40 65 65 72 76 95 97
1.4 其他间隔序列
除了上面介绍的序列外,还有其他序列,只有一个绝对的条件,就是逐渐减小的间隔最后一定要等于1,因此最后一趟排序是一次普通的插入排序。间隔序列中的数字互质通常被认为很重要,也就是说除了1之外没有别的公约数。
1.5 希尔排序的效率
迄今为止还没有人从理论上分析希尔排序的效率,基于各种实验的评估,估计它的时间级在O(N^(3/2))到O(N^(7/6))
2 快速排序
快速排序是最流行的排序算法,在大多数情况下,快速排序都是最快的,执行时间为O(N*logN)级。快速排序算法本质上通过把一个数组划分为两个子数组,然后递归调用自身为每个子数组进行快速排序来实现的。寻找划分数组的基准值也就是中枢值是这个算法的核心。基准值理论上任意一个均可,但最好选取一个数组的中位数,此时的排序效率是最高的。
package chapter7; class ArrayIns{ private long[] array; private int nElems; public ArrayIns(int max){ array = new long[max]; nElems = 0; } //插入数组值 public void insert(long value){ array[nElems] = value; nElems++; } //输出数组 public void display(){ System.out.print("A:"); for(int i = 0; i < nElems; i++){ System.out.print(array[i] + " "); } System.out.println(); } public void quickSort(){ recQuickSort(0, nElems - 1); } public void recQuickSort(int left, int right){ if(right - left <= 0){ return; }else{ //以右边的为基准值 long pivot = array[right]; int partition = partitionIt(left, right, pivot); recQuickSort(left, partition - 1); recQuickSort(partition + 1, right); } } //确定基准值 public int partitionIt(int left, int right, long pivot){ int leftPtr = left - 1; int rightPtr = right; while(true){ //寻找左边大于基准值的 while(array[++leftPtr] < pivot){ ; } //寻找右边小于基准值的 while(array[--rightPtr] > pivot){ ; } if(leftPtr >= rightPtr){ break; }else{ swap(leftPtr, rightPtr); } } swap(leftPtr, right); return leftPtr; } //交换两个值 public void swap(int dex1, int dex2){ long temp = array[dex1]; array[dex1] = array[dex2]; array[dex2] = temp; } }; public class QuickSortApp { public static void main(String[] args){ int maxSize = 16; ArrayIns arr; arr = new ArrayIns(maxSize); for(int i = 0; i < maxSize; i++){ long n = (int)(java.lang.Math.random()*99); arr.insert(n); } //未排序的数组输出 arr.display(); //对数组进行排序 arr.quickSort(); //输出排好序的数组 arr.display(); } };