java面试题 各种排序

用Java语言实现的各种排序，包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。
插入排序：
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class InsertSort implements SortUtil.Sort{
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int temp;
for(int i=1;i0)&&(data[j]i;j–){
if(data[j]1) quickSort(data,i,k-1);
if((j-k)>1) quickSort(data,k+1,j);

}
/**
* @param data
* @param i
* @param j
* @return
*/
private int partition(int[] data, int l, int r,int pivot) {
do{
while(data[++l]pivot);
SortUtil.swap(data,l,r);
}
while(l0){
int j=stack[top–];
int i=stack[top–];

pivotIndex=(i+j)/2;
pivot=data[pivotIndex];

SortUtil.swap(data,pivotIndex,j);

//partition
l=i-1;
r=j;
do{
while(data[++l]pivot));
SortUtil.swap(data,l,r);
}
while(lTHRESHOLD){
stack[++top]=i;
stack[++top]=l-1;
}
if((j-l)>THRESHOLD){
stack[++top]=l+1;
stack[++top]=j;
}

}
//new InsertSort().sort(data);
insertSort(data);
}
/**
* @param data
*/
private void insertSort(int[] data) {
int temp;
for(int i=1;i0)&&(data[j]r)
data[cur]=temp[i1++];
else if(temp[i1]= THRESHOLD)
mergeSort(data, temp, l, mid);
else
insertSort(data, l, mid – l + 1);
if ((r – mid) > THRESHOLD)
mergeSort(data, temp, mid + 1, r);
else
insertSort(data, mid + 1, r – mid);
for (i = l; i <= mid; i++) { temp = data; } for (j = 1; j <= r - mid; j++) { temp[r - j + 1] = data[j + mid]; } int a = temp[l]; int b = temp; for (i = l, j = r, k = l; k <= r; k++) { if (a < b) { data[k] = temp; a = temp; } else { data[k] = temp[j--]; b = temp[j]; } } } /** * @param data * @param l * @param i */ private void insertSort(int[] data, int start, int len) { for(int i=start+1;istart) && data[j]queue[j]) //不用交换
break;
SortUtil.swap(queue,j,k);
k = j;
}
}
private void fixUp(int k) {
while (k > 1) {
int j = k >> 1;
if (queue[j]>queue[k])
break;
SortUtil.swap(queue,j,k);
k = j;
}
}
}