Java排序算法(四)
obj, left, center, right);
}
}
private void merge(double[] obj, int left,
int center, int right){
int mid = center + 1;
int third = left;
int tmp = left;
while(left <= center && mid <= right){
// 从两个数组中取出小的放入中间数组
if(obj[left]-obj[mid]<=10e-6){
bridge[third++] = obj[left++];
} else{
bridge[third++] = obj[mid++];
}
}
//剩余部分依次置入中间数组
while(mid <= right){
bridge[third++] = obj[mid++];
}
while(left <= center){
bridge[third++] = obj[left++];
}
//将中间数组的内容拷贝回原数组
copy(obj, tmp, right);
}
private void copy(double[] obj, int left, int right)
{
while(left <= right){
obj[left] = bridge[left];
left++;
}
}
public static void main(String[] args) {
Random random = new Random(6);
int arraysize = 10;
double[]sorted = new double[arraysize];
System.out.print("Before Sort:");
for (int j = 0; j < arraysize; j++) {
sorted[j] = (int) (random.nextDouble() * 100);
System.out.print((int) sorted[j] + " ");
}
System.out.println();
MergeSort sorter = new MergeSort();
sorter.sort(sorted);
System.out.print("After Sort:");
for (int j = 0; j < sorted.length; j++) {
System.out.print((int) sorted[j] + " ");
}
System.out.println();
}
}
8）基数排序：
使用10个辅助队列，假设最大数的数字位数为 x， 则一共做 x次，从个位数开始往前，以第i位数字的大小为依据，将数据放进辅助队列，搞定之后回收。下次再以高一位开始的数字位为依据。
以Vector作辅助队列，基数排序的Java代码：
public class RadixSort {
private int keyNum=-1;
private Vector
>util;
public void distribute(double [] sorted, int nth){
if(nth<=keyNum && nth>0){
util=new Vector>();
for(int j=0;j<10;j++){
Vector temp= new Vector ();
util.add(temp);
}
for(int j=0;j
int index=getNthDigit(sorted[j],nth);
util.get(index).add(sorted[j]);
}
}
}
public int getNthDigit(double num,int nth){
String nn= Integer.toString((int)num);
int len= nn.length();
if(len>=nth){
returnCharacter.getNumericValue(nn.charAt(len-nth));
}else{
return0;
}
}
public void collect(double [] sorted){
int k=0;
for(int j=0;j<10;j++){
int len= util.get(j).size();
if(len>0){
for(int i=0;i
sorted[k++]= util.get(j).get(i);
}
}
}
util=null;
}
public int getKeyNum(double [] sorted){
doublemax= Double.MIN_VALUE;
for(int j=0;j
if(sorted[j]>max){
max= sorted[j];
}
}
returnInteger.toString((int)max).length();
}
public void radixSort(double [] sorted){
if(keyNum==-1){
keyNum= getKeyNum(sorted);
}
for(int i=1;i<=keyNum;i++){
distribute(sorted,i);
collect(sorted);
}
}
public static void main(String[] args) {
Random random = new Random(6);
int arraysize = 21;
double[]sorted = new double[arraysize];
System.out.print("Before Sort:");
for (int