# Q：重新排序的数组元素是有序的，远第一

I have an array A of size n. I want to reorder the elements of A into another array B in such a way that elements that lie far apart in A are ordered first in B. For example, if n = 9, the two first elements of B should be A[0] and A[8], since these are the two elements furthest apart in A (distance 8). B[2] should be A[4], since that element is farthest from A[0] and A[8] (distance 4). Next we get B[3] = A[2] and B[4] = A[6], since A[2] and A[6] are farthest from A[0], A[4], and A[8] (minimum distance 2). Finally A[1], A[3], A[5], A[7] in the last four positions of B (minimum distance 1 from the already added elements).

What is a fast algorithm for doing this, and handling arrays for arbitrary size n?

This will work for any arbitrary size. It uses a breadth first search http://en.wikipedia.org/wiki/Breadth-first_search

``````static List<Integer> maxDistance(int _start, int _end) {
List<Integer> result = new ArrayList<>(Arrays.asList(_start, _end - 1));
List<List<Integer>> ranges = Arrays.asList(Arrays.asList(_start + 1, _end - 1));

while(!ranges.isEmpty()) {
List<List<Integer>> ranges2 = ranges;
ranges = new ArrayList<>();
for(List<Integer> range: ranges2) {
int start = range.get(0),
end = range.get(1);
if(end - start == 1) {
} else if(end > start) {
int mid = (start + end)/2;
}
}
}

return result;
}
``````

``````static List<Integer> maxDistance(int _start, int _end) {
List<Integer> result = new ArrayList<>(Arrays.asList(_start, _end - 1));
List<List<Integer>> ranges = Arrays.asList(Arrays.asList(_start + 1, _end - 1));

while(!ranges.isEmpty()) {
List<List<Integer>> ranges2 = ranges;
ranges = new ArrayList<>();
for(List<Integer> range: ranges2) {
int start = range.get(0),
end = range.get(1);
if(end - start == 1) {
} else if(end > start) {
int mid = (start + end)/2;
}
}
}

return result;
}
``````

Something like this should do it: You copy the first element. Take the length of the array as a step size, and copy the odd multiples of this. Halve the step size, then repeat until all the elements have been copied (and the step size is 1). Implementing this in Java might look like this:

``````public static int[] farApartSort(int[] A) {

// Set up
int[] B = new int[A.length];
int i = 0;

// First value
B[i++] = A[0];

// Loop through the array in increments which halve each time
int chunkLength = A.length - 1;
do {
// Take the odd multiples of the current increment
for (int j = 1; chunkLength * j < A.length; j += 2) {
// Copy the values into the sorted array
B[i++] = A[chunkLength * j];
}
chunkLength /= 2;
} while (chunkLength > 0);

return B;
``````

}

Something like this should do it: You copy the first element. Take the length of the array as a step size, and copy the odd multiples of this. Halve the step size, then repeat until all the elements have been copied (and the step size is 1). Implementing this in Java might look like this:

``````public static int[] farApartSort(int[] A) {

// Set up
int[] B = new int[A.length];
int i = 0;

// First value
B[i++] = A[0];

// Loop through the array in increments which halve each time
int chunkLength = A.length - 1;
do {
// Take the odd multiples of the current increment
for (int j = 1; chunkLength * j < A.length; j += 2) {
// Copy the values into the sorted array
B[i++] = A[chunkLength * j];
}
chunkLength /= 2;
} while (chunkLength > 0);

return B;
``````

}

algorithm  sorting