我担心为每个递归步骤创建 3 个数组可能会占用太多空间,但我真的想不出另一种方法。请告诉我它有什么问题。
public static int[] split(int [] vector){
if(vector.length <= 1 || vector == null)
return vector;
int len = vector.length;
int[] list1 = new int[len / 2];
// If the number of elements is odd the second list will be bigger
int[] list2 = new int[len / 2 + (len % 2)];
// Here we assign the elements to 2 separate lists
for(int x = 0; x < len / 2; x++)
list1[x] = vector[x];
for(int j = 0, i = len / 2; j < list2.length; i++, j++)
list2[j]=vector[i];
// Apply the recursion, this will eventually order the lists
list1 = split(list1);
list2 = split(list2);
// Here we take the 2 ordered lists and merge them into 1
int i = 0, a = 0, b = 0;
int[] listfinal = new int[len];
while(i < len){
if(a >= list1.length){
listfinal[i] = list2[b];
b++;
} else if(b >= list2.length){
listfinal[i] = list1[a];
a++;
} else if(list1[a] <= list2[b]){
listfinal[i] = list1[a];
a++;
} else if(list1[a] > list2[b]){
listfinal[i] = list2[b];
b++;
}
i++;
}
return listfinal; // Return the merged and ordered list
}