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);
    
    
}
    
    
}