我有一个长度超过100万的数组,其中3个后续索引是1个数据输入。数据集应该是这样的,其中2.0
和1.0
是数组数据输入的起点:
double[] dataEntries = {2.0, 2.2, 2.1, 1.0, 1.2, 1.1, ...};
现在我想对它们进行排序,但我必须把它们作为条目放在一起。我考虑过交换bubble-sort
这样的位置,但这是O(n^2)
的复杂性。我也考虑过Array.sort()
,但这只适用于没有分组索引的数组。我可以使用%3
并获得每个数据集的所有起点,然后对此应用Array.sort()
,但是如果以后我试图构建三个后续索引的关系,我不知道是否能够正确地构建这些关系。
上面排序的dataEntries
的结果:
sortedDataEntries = {1.0, 1.2, 1.1, 2.0, 2.2, 2.1, ...};
我希望有人知道一个好办法。
发布于 2015-05-04 09:45:28
下面是复杂性O(n*log(n))
。
我只是把每个第三个元素放入新的数组中,在对其排序时,我记得它所处的位置。然后根据分组阵列的位置变化,构造了一种新的分组阵列。您可以看到,在最后的方法“合并”我只需要位置数组和原始数组,“分组”一个不再需要。
import java.util.Arrays;
public class JavaApplication39 {
public static void main(String[] args) {
double[] dataEntries = {2.0, 2.2, 2.1, 1.0, 1.2, 1.1, 7.0,7.1,7.5};
double[] dataGrouped = new double[dataEntries.length/3];
int[] positions = new int[dataGrouped.length];
int j=0;
for (int i = 0; i < dataEntries.length; i+=3) {
dataGrouped[j] = dataEntries[i];
positions[j] = j;
j++;
}
quickSort(dataGrouped,positions,0,dataGrouped.length-1);
double[] merged = merge(dataEntries,positions);
System.out.println(Arrays.toString(merged));
}
private static double[] merge(double[] dataEntries,int[] positions){
double[] toReturn = new double[dataEntries.length];
for (int i = 0; i < positions.length; i++) {
toReturn[i*3] = dataEntries[positions[i]*3];
toReturn[i*3+1] = dataEntries[positions[i]*3+1];
toReturn[i*3+2] = dataEntries[positions[i]*3+2];
}
return toReturn;
}
private static void quickSort(double[] array, int[] positions, int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
double pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two arrays
while (i <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a number
* from right side which is less then the pivot value. Once the search
* is done, then we exchange both numbers.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(array,positions, i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(array,positions, lowerIndex, j);
if (i < higherIndex)
quickSort(array,positions, i, higherIndex);
}
private static void exchangeNumbers(double[] array, int[] positions, int i, int j) {
double temp = array[i];
array[i] = array[j];
array[j] = temp;
int postemp = positions[i];
positions[i] = positions[j];
positions[j] = postemp;
}
}
产出如下:
[1.0, 1.2, 1.1, 2.0, 2.2, 2.1, 7.0, 7.1, 7.5]
发布于 2015-05-04 09:27:16
最安全和最简单的方法是将双倍数组转换为List<SomeClass>
,其中SomeClass
是一个包含3个双倍的类,并且还实现了Comparable
。然后,您可以随意排序,包括使用内置的排序支持,然后在最后将其转换为一个双重数组。
发布于 2015-05-04 09:32:58
不考虑性能注,O(n^2)。假设数组长度为3*n
for(int i = 0;i<length_of_array-3;i+=3){
for(int j = i+3; j<length_of_array-3;j+=3){
if(arr[i] > arr[j]{
swap(i,j);
}
}
交换方法就行了
swap(int i, int j){
for(int k=i;k<i+3;k++,j++){
double temp = arr[k];
arr[k]=arr[j];
arr[j]=temp;
}
}
https://stackoverflow.com/questions/30026653
复制相似问题