基于JAVA的经典排序算法的程序实现

基于JAVA的经典排序算法的程序实现

李继连

李继连（黑龙江司法警官职业学院黑龙江哈尔滨150060）

摘要：对排序算法的分析可以从以下几个方面进行：排序算法的稳定性、平均时间、最坏情况、辅助存储空间。从稳定性来说，稳定的排序算法有直接插入排序、冒泡排序、归并排序，其它排序算法都是不稳定的。对这几种经典排序算法进行研究练习，对我们编程思路的开拓是大有裨益的。

关键词：JAVA算法排序程序

一、几种经典算法的程序实现

为了便于说明，先引入基础类：

packagealgorithms;

publicabstractclassSorter<EextendsComparable<E>>{

publicabstractvoidsort(E[]array,intfrom,intlen);

publicfinalvoidsort(E[]array)

{

sort(array,0,array.length);

}

protectedfinalvoidswap(E[]array,intfrom,intto)

{

Etmp=array[from];

array[from]=array[to];

array[to]=tmp;

}

}

1.冒泡排序（BubbleSort）

这可能是最简单的排序算法了，算法思想是每次从数组末端开始比较相邻两元素，把第i小的冒泡到数组的第i个位置，i从0一直到N-1从而完成排序。当然也可以从数组开始端开始比较相邻两元素，把第i大的冒泡到数组的第N-i个位置，i从0一直到N-1从而完成排序。

程序实现：

packagealgorithms;

publicclassBubbleSorter<EextendsComparable<E>>extendsSorter<E>{

privatestaticbooleanDWON=true;

publicfinalvoidbubble_down(E[]array,intfrom,intlen)

{

for(inti=from;i<from+len;i++)

{

for(intj=from+len-1;j>i;j--)

{

if(array[j].compareTo(array[j-1])<0)

{

swap(array,j-1,j);

}

}

}

}

publicfinalvoidbubble_up(E[]array,intfrom,intlen)

{

for(inti=from+len-1;i>=from;i--)

{

for(intj=from;j<i;j++)

{

if(array[j].compareTo(array[j+1])>0)

{

swap(array,j,j+1);

}

}

}

}

publicvoidsort(E[]array,intfrom,intlen){

if(DWON)

{

bubble_down(array,from,len);

}

else

{

bubble_up(array,from,len);

}

}

}

2.选择排序（SelectionSort）

选择排序相对于冒泡来说，它不是每次发现逆序都交换，而是在找到全局第i小的时候记下该元素位置，最后跟第i个元素交换，从而保证数组最终的有序。相对于插入排序来说，选择排序每次选出的都是全局第i小的，不会调整前i个元素了。

程序实现：

packagealgorithms;

publicclassSelectSorter<EextendsComparable<E>>extendsSorter<E>{

publicvoidsort(E[]array,intfrom,intlen){

for(inti=0;i<len;i++)

{

intsmallest=i;

intj=i+from;

for(;j<from+len;j++)

{

if(array[j].compareTo(array[smallest])<0)

{

smallest=j;

}

}

swap(array,i,smallest);

}

}

}

3.插入排序（InsertionSort）

该算法在数据规模小的时候十分高效。该算法每次插入第K+1到前K个有序数组中一个合适位置，K从0开始到N-1,从而完成排序。

程序实现：

packagealgorithms;

publicclassInsertSorter<EextendsComparable<E>>extendsSorter<E>{

publicvoidsort(E[]array,intfrom,intlen){

Etmp=null;

for(inti=from+1;i<from+len;i++)

{

tmp=array[i];

intj=i;

for(;j>from;j--)

{

if(tmp.compareTo(array[j-1])<0)

{

array[j]=array[j-1];

}

elsebreak;

}

array[j]=tmp;

}

}

}

4.堆排序

堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。堆是一种完全二叉树，一般使用数组来实现。建堆以及删除堆定节点使用shiftDwon,而在插入节点时一般结合两种操作一起使用。堆排序借助最大值堆来实现，第i次从堆顶移除最大值放到数组的倒数第i个位置，然后shiftDown到倒数第i+1个位置,一共执行N次调整，即完成排序。显然，堆排序也是一种选择性的排序，每次选择第i大的元素。

程序实现：

packagealgorithms;

publicclassHeapSorter<EextendsComparable<E>>extendsSorter<E>{

publicvoidsort(E[]array,intfrom,intlen){

build_heap(array,from,len);

for(inti=0;i<len;i++)

{

swap(array,from,from+len-1-i);

shift_down(array,from,len-1-i,0);

}

}

privatefinalvoidbuild_heap(E[]array,intfrom,intlen){

intpos=(len-1)/2;

for(inti=pos;i>=0;i--)

{

shift_down(array,from,len,i);

}

}

privatefinalvoidshift_down(E[]array,intfrom,intlen,intpos)

{

Etmp=array[from+pos];

intindex=pos*2+1;

while(index<len)

{

if(index+1<len&&array[from+index].compareTo(array[from+index+1])<0)

{

index+=1;

}

if(tmp.compareTo(array[from+index])<0)

{

array[from+pos]=array[from+index];

pos=index;

index=pos*2+1;

}

else

{

break;

}

}

array[from+pos]=tmp;

}

}

5.快速排序

快速排序可能是目前使用最广泛的排序算法了。

程序实现：

packagealgorithms;

publicclassQuickSorter<EextendsComparable<E>>extendsSorter<E>{

publicvoidsort(E[]array,intfrom,intlen){

q_sort(array,from,from+len-1);

}

privatefinalvoidq_sort(E[]array,intfrom,intto){

if(to-from<1)return;

intpivot=selectPivot(array,from,to);

pivot=partion(array,from,to,pivot);

q_sort(array,from,pivot-1);

q_sort(array,pivot+1,to);

}

privateintpartion(E[]array,intfrom,intto,intpivot){

Etmp=array[pivot];

array[pivot]=array[to];

while(from!=to)

{

while(from<to&&array[from].compareTo(tmp)<=0)from++;

if(from<to)

{

array[to]=array[from];

to--;

}

while(from<to&&array[to].compareTo(tmp)>=0)to--;

if(from<to)

{

array[from]=array[to];

from++;

}

}

array[from]=tmp;

returnfrom;

}

privateintselectPivot(E[]array,intfrom,intto){

return(from+to)/2;

}

}

二、结束语

对排序算法的分析可以从以下几个方面进行：排序算法的稳定性、平均时间、最坏情况、辅助存储空间。从稳定性来说，稳定的排序算法有直接插入排序、冒泡排序、归并排序，其它排序算法都是不稳定的。对常见的这几种排序算法的练习，对我们的思路的规范化是很好的。

参考文献

1.[美]C.ThomasWu著候国峰等译AnIntroductiontoObject-OrientedProgrammingwithJava.中文版：面向对象程序设计导论，北京：电子工业出版社，2002，06。

2.[美]BruceEckel著ThinginginJavaThirdEdition.PearsonEducation，北京：机械工业出版社，2005，07。

3.毕广吉Java程序设计实例教程[M].北京：冶金工业出版社，2007年。

4.BruceEckel《ThinkinginJava4》.American：PrenticeHallPTR.

5.O’reilly《JavaServletProgramming》.American：SernniYey.