现在再回过头理解，结合自己的体会， 选用最佳的方式描述这些算法，以方便理解它们的工作原理和程序设计技巧。本文适合做java面试准备的材料阅读。
先附上一个测试报告：
Array length: 20000
bubbleSort : 766 ms
bubbleSortAdvanced : 662 ms
bubbleSortAdvanced2 : 647 ms
selectSort : 252 ms
insertSort : 218 ms
insertSortAdvanced : 127 ms
insertSortAdvanced2 : 191 ms
binaryTreeSort : 3 ms
shellSort : 2 ms
shellSortAdvanced : 2 ms
shellSortAdvanced2 : 1 ms
mergeSort : 3 ms
quickSort : 1 ms
heapSort : 2 ms
通过测试，可以认为，冒泡排序完全有理由扔进垃圾桶。它存在的唯一理由可能是最好理解。希尔排序的高效性是我没有想到的；堆排序比较难理解和编写，要有宏观的思维。
复制代码 代码如下:
package algorithm.sort;
import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Date;
public class SortUtil {
// 被测试的方法集合
static String[] methodNames = new String[]{
"bubbleSort",
"bubbleSortAdvanced",
"bubbleSortAdvanced2",
"selectSort",
"insertSort",
"insertSortAdvanced",
"insertSortAdvanced2",
"binaryTreeSort",
"shellSort",
"shellSortAdvanced",
"shellSortAdvanced2",
"mergeSort",
"quickSort",
"heapSort"
};
public static void main(String[] args) throws Exception{
//correctnessTest();
performanceTest(20000);
}
public static void correctnessTest() throws Exception{
int len = 10;
int[] a = new int[len];
for(int i=0; i
}
Method sortMethod = null;
sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());
Object o = sortMethod.invoke(null, a);
System.out.print(methodNames[i] + " : ");
if(o==null){
System.out.println(Arrays.toString(a));
}
else{
//兼顾mergeSort，它的排序结果以返回值的形式出现；
System.out.println(Arrays.toString((int[])o));
}
}
}
public static void performanceTest(int len) throws Exception{
int[] a = new int[len];
int times = 20;
System.out.println("Array length: " + a.length);
for(int i=0; i
sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());
int totalTime = 0;
for(int j=0; j
}
long start = new Date().getTime();
sortMethod.invoke(null, a);
long end = new Date().getTime();
totalTime +=(end-start);
}
System.out.println(methodNames[i] + " : " + (totalTime/times) + " ms");
//System.out.println(Arrays.toString(a));
}
}
public static void bubbleSort(int[] a){
for(int i=0; i for(int j=0; j if(a[j]>a[j+1]){
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
public static void bubbleSortAdvanced(int[] a){
int k = a.length-1;
boolean flag = true;
while(flag){
flag = false;
for(int i=0;i
int tmp = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
//有交换则继续保持标志位；
flag = true;
}
}
k--;
}
}
public static void bubbleSortAdvanced2(int[] a){
int flag = a.length - 1;
int k;
while(flag>0){
k = flag;
flag = 0;
for(int i=0; i
int tmp = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
//有交换则记录该趟最后发生比较的地点；
flag = i+1;
}
}
}
}
public static void insertSort(int[] a){
//从无序表头开始遍历；
for(int i=1; i int j;
//拿a[i]和有序表元素依次比较，找到一个恰当的位置；
for(j=i-1;j>=0; j--){
if(a[j] < a[i]){
break;
}
}
//如果找到恰当的位置，则从该位置开始，把元素朝后移动一格，为插入的元素腾出空间；
if(j!=(i-1)){
int tmp = a[i];
int k;
for(k = i-1; k>j;k--){
a[k+1] = a[k];
}
a[k+1] = tmp;
}
}
}
public static void insertSortAdvanced(int[] a){
//遍历无序表；
for(int i=1; i //如果无序表头元素小于有序表尾，说明需要调整；
if(a[i] int tmp = a[i];
int j;
//从有序表尾朝前搜索并比较，并把大于a[i]的元素朝后移动以腾出空间；
for(j=i-1; j>=0&&a[j]>tmp;j--){
a[j+1] = a[j];
}
a[j+1] = tmp;
}
}
}
public static void insertSortAdvanced2(int[] a){
//遍历无序表
for(int i=1; i //拿a[i]从有序表尾开始冒泡；
for(int j=i-1; j>=0 && a[j] > a[j+1]; j--){//a[j+1]就是a[i]
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
public static void quickSort(int[] a, int low, int high){
if(low>=high){
return;
}
int low0 = low;
int high0 = high;
boolean forward = false;
while(low0!=high0){
if(a[low0]>a[high0]){
int tmp = a[low0];
a[low0] = a[high0];
a[high0] = tmp;
forward = !forward;
}
if(forward){
low0++;
}
else{
high0--;
}
}
low0--;
high0++;
quickSort(a, low, low0);
quickSort(a, high0, high);
}
public static void quickSort(int[] a){
quickSort(a, 0, a.length-1);
}
public static int[] merge(int[] a, int[] b){
int result[] = new int[a.length+b.length];
int i=0,j=0,k=0;
while(i if(a[i]
i++;
}
else{
result[k++] = b[j];
j++;
}
}
while(i result[k++] = a[i++];
}
while(j
}
return result;
}
public static int[] mergeSort(int[] a){
if(a.length==1){
return a;
}
int mid = a.length/2;
int[] leftPart = new int[mid];
int[] rightPart = new int[a.length-mid];
System.arraycopy(a, 0, leftPart, 0, leftPart.length);
System.arraycopy(a, mid, rightPart, 0, rightPart.length);
leftPart = mergeSort(leftPart);
rightPart = mergeSort(rightPart);
return merge(leftPart, rightPart);
}
public static void selectSort(int[] a){
for(int i=0; i int minIndex = i;
for(int j=i+1; j if(a[j] minIndex = j;
}
}
int tmp = a[i];
a[i] = a[minIndex];
a[minIndex]= tmp;
}
}
public static void shellSort(int[] a){
// 控制间距；间距逐渐减小，直到为1；
for(int gap = a.length/2; gap>0; gap/=2){
// 扫描每个子数组
for(int i=0; i
// a[i]是初始有序区；
for(int j=i+gap; j // 无序区首元素小于有序区尾元素，说明需要调整
if(a[j] int tmp = a[j];
int k = j-gap;
//从有序区尾向前搜索查找适当的位置；
while(k>=0&&a[k]>tmp){
a[k+gap] = a[k];
k-=gap;
}
a[k+gap] = tmp;
}
}
}
}
}
public static void shellSortAdvanced(int[] a){
// 控制步长
for(int gap = a.length/2; gap>0; gap/=2){
// 从无序区开始处理，把多个子数组放在一起处理；
for(int j=gap; j // 下面的逻辑和上面是一样的；
if(a[j] int tmp = a[j];
int k = j-gap;
while(k>=0&&a[k]>tmp){
a[k+gap] = a[k];
k-=gap;
}
a[k+gap] = tmp;
}
}
}
}
public static void shellSortAdvanced2(int[] a){
for(int gap = a.length/2; gap>0; gap/=2){
for(int i=gap; i if(a[i] for(int j=i-gap; j>=0&&a[j+gap]>a[j]; j-=gap){
int tmp = a[j];
a[j] = a[j+gap];
a[j+gap] = tmp;
}
}
}
}
}
public static void heapSort(int[] a){
// 先从最后一个非叶子节点往上调整，使满足堆结构；
for(int i=(a.length-2)/2; i>=0; i--){
maxHeapAdjust(a, i, a.length);
}
// 每次拿最后一个节点和第一个交换，然后调整堆；直到堆顶；
for(int i=a.length-1; i>0; i--){
int tmp = a[i]; a[i] = a[0]; a[0] = tmp;
maxHeapAdjust(a, 0, i);
}
}
public static void maxHeapAdjust(int[] a, int i, int len){
int tmp = a[i];
// j是左孩子节点
int j = i*2+1;
//
while(j
// j+1是右孩子节点
if((j+1)
j++;
}
// 找到恰当的位置就不再找
if(a[j]
}
// 否则把较大者沿着树往上移动；
a[i] = a[j];
// i指向刚才的较大的孩子；
i = j;
// j指向新的左孩子节点；
j = 2*i + 1;
}
// 把要调整的节点值下沉到适当的位置；
a[i] = tmp;
}
public static void binaryTreeSort(int[] a){
// 构造一个二叉树节点内部类来实现二叉树排序算法；
class BinaryNode{
int value;
BinaryNode left;
BinaryNode right;
public BinaryNode(int value){
this.value = value;
this.left = null;
this.right = null;
}
public void add(int value){
if(value>this.value){
if(this.right!=null){
this.right.add(value);
}
else{
this.right = new BinaryNode(value);
}
}
else{
if(this.left!=null){
this.left.add(value);
}
else{
this.left = new BinaryNode(value);
}
}
}
public void iterate(){
if(this.left!=null){
this.left.iterate();
}
// 在测试的时候要把输出关掉，以免影响性能；
// System.out.print(value + ", ");
if(this.right!=null){
this.right.iterate();
}
}
}
BinaryNode root = new BinaryNode(a[0]);
for(int i=1; i root.add(a[i]);
}
root.iterate();
}
}
