Java排序算法（桶排序，基数排序等）

排序算法复习（Java 实现）(一）： 插入，冒泡，选择，Shell,快速排序

为了便于管理，先引入个基础类：

package algorithms;

/**

* @author yovn

*

*/

public abstract class Sorter<E extends Comparable<E>> {

}

protected 'nal void swap(E[] array,int from ,int to)

{

E tmp=array[from];

array[from]=array[to];

array[to]=tmp;

}

}

一 插入排序

该算法在数据规模小的时候十分高效，该算法每次插入第 K+1 到前 K 个有序数组中一个合

/* (non-Javadoc)

* @see algorithms.Sorter#sort(E[], int, int)

*/

public void sort(E[] array, int from, int len) {

E tmp=null;

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

{

tmp=array[i];

int j=i;

for(;j>from;j--)

}

array[j]=tmp;

}

}

}

二 冒泡排序

这可能是最简单的排序算法了，算法思想是每次从数组末端开始比较相邻两元素，把第 i

小的冒泡到数组的第 i 个位置。i 从 0 一直到 N-1 从而完成排序。（当然也可以从数组开始

*/

public class BubbleSorter<E extends Comparable<E>> extends Sorter<E> {

private static boolean DWON=true;

public 'nal void bubble_down(E[] array, int from, int len)

{

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

{

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

{

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

{

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

{

swap(array,j,j+1);

}

}

}

}

@Override

public void sort(E[] array, int from, int len) {

if(DWON)

{

bubble_down(array,from,len);

else

}

}

package algorithms;

/**

* @author yovn

int j=i+from;

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

{

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

{

smallest=j;

}

}

swap(array,i,smallest);

}

}

}

1）当数据规模小的时候非常高效

2）当给定数据已经有序时的时间代价为 O(N)

所以，Shell 排序每次把数据分成若个小块，来使用插入排序，而且之后在这若个小块排好

序的情况下把它们合成大一点的小块，继续使用插入排序，不停的合并小块，知道最后成

一个块，并使用插入排序。

O(N^1.5)

所以我在实现 Shell 排序的时候采用该增量序列

package algorithms;