java實現歸並排序和樹形排序（錦標賽制）：java字符串分隔或的形式

String[] b=str.split("query|,");//query分隔或者逗號分隔
    
歸並排序，遞歸實現
public class MergeSort2 {
// 對data數組中的 [a,b) 區間的數據進行歸並排序，
// 排序結束後，[a,b)間數據處於升序有序狀態
static void mergeSort(int[] data, int a,int b)
{
if (a >= b) return;
int mid=(a+b)/2;//拆分排序
mergeSort(data,a,mid);
    
mergeSort(data,mid+1,b);
    
//前面兩個拍好了或者只有個一個元素時執行下面
merge(data,a,mid,b);
}
// data中的數據, [low,mid), [mid,high) 是兩段待歸並數據。歸並後，[low,high) 整體有序
static void merge(int[] data, int low,int mid,int high)
{
int[] tmp = new int[high-low+1];
int[] a=new int[mid-low+1];
    
int[] b=new int[high-mid];
    
//給兩半數組賦值
for (int i = 0; i < a.length; i++) {
a[i]=data[low+i-1];
}
for (int i = 0; i < b.length; i++) {
b[i]=data[mid+i];
}
int ai=0;//只要能表達其位置的都可以稱為指針，不一定是指向內存地址，C可能是指向內存地址
int bi=0;
int ci=0;
while (ai<a.length&&bi<high-mid) {
//誰小就先添加誰
if (a[ai]<=b[bi]) {
tmp[ci++]=a[ai++];
}
else {
tmp[ci++]=b[bi++];
}
}
//判斷剩余,將剩余的添加到尾部
while (ai<a.length)tmp[ci++]=a[ai++];
    
while (bi<b.length)tmp[ci++]=b[bi++];
    
//把排好的值賦給數組
int i=0;
    
int k=low-i-1;
while (i<ci) {
data[k++]=tmp[i++];
    
}
}
    
//上面的操作針對數組，所以數組發生了變化，若是變量，只是在方法中改變值，出了方法值不變，除非設成引用類型
public static void main(String[] args) {
int[] a = { 26, 29, 60, 60, 11, 15, 20, 75, 100, 500, 1000, 3, 5, 6, 8,9 };
//int[] a={3,2,1};
mergeSort(a, 1,a.length);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
}
    
    
}

查看本欄目

樹形排序

public class TreeSort {
public static int[] treeAgain(int[] a) {
// 樹排序挺浪費空間的，數值16個，排序完全二叉樹，需要31個節點
int[] allCode = new int[2 * a.length - 1];
for (int i = allCode.length - 1; i >= 0; i--) {
if (i - a.length + 1 >= 0) {
allCode[i] = a[i - a.length + 1];
} else {
if (allCode[i * 2 + 1] <= allCode[i * 2 + 2]) {
allCode[i] = allCode[i * 2 + 1];
} else {
allCode[i] = allCode[i * 2 + 2];
}
}
}
return allCode;
}
    
    
public static void treeSort(int[] a) {
int allCode[] = null;
while (true) {
    
//重新賦值後再排序
allCode = treeAgain(a);
if (allCode[0]==Integer.MAX_VALUE) {
break;
}
System.out.print(allCode[0] + " ");
for (int i = 0; i < a.length; i++) {
if (a[i] == allCode[0]) {
a[i] = Integer.MAX_VALUE;
}
}
    
}
//樹形顯示
/*
 * int n = 1;
 * 
 * for (int i = 0; i < allCode.length; i++) {
 * System.out.print(allCode[i] + " ");
 * 
 * int x = (int) Math.pow(2, n) - 2; if (i == x) { System.out.println();
 * n++; }
 * 
 * }
 */
    
    
}
    
    
/**
 * @param args
 */
public static void main(String[] args) {
int[] a = { 26, 29, 60, 60, 11, 15, 20, 75, 100, 500, 1000, 3, 5, 6, 8,
9 };
    
    
treeSort(a);
    
    
}
    
    
}