首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >排序一个数组,其中多个接续的索引号形成一个条目,应该保持在一起

排序一个数组,其中多个接续的索引号形成一个条目,应该保持在一起
EN

Stack Overflow用户
提问于 2015-05-04 09:23:30
回答 3查看 63关注 0票数 1

我有一个长度超过100万的数组,其中3个后续索引是1个数据输入。数据集应该是这样的,其中2.01.0是数组数据输入的起点:

代码语言:javascript
运行
复制
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的结果:

代码语言:javascript
运行
复制
sortedDataEntries = {1.0, 1.2, 1.1, 2.0, 2.2, 2.1, ...};

我希望有人知道一个好办法。

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2015-05-04 09:45:28

下面是复杂性O(n*log(n))

我只是把每个第三个元素放入新的数组中,在对其排序时,我记得它所处的位置。然后根据分组阵列的位置变化,构造了一种新的分组阵列。您可以看到,在最后的方法“合并”我只需要位置数组和原始数组,“分组”一个不再需要。

代码语言:javascript
运行
复制
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;
    }
}

产出如下:

代码语言:javascript
运行
复制
[1.0, 1.2, 1.1, 2.0, 2.2, 2.1, 7.0, 7.1, 7.5]
票数 1
EN

Stack Overflow用户

发布于 2015-05-04 09:27:16

最安全和最简单的方法是将双倍数组转换为List<SomeClass>,其中SomeClass是一个包含3个双倍的类,并且还实现了Comparable。然后,您可以随意排序,包括使用内置的排序支持,然后在最后将其转换为一个双重数组。

票数 2
EN

Stack Overflow用户

发布于 2015-05-04 09:32:58

不考虑性能注,O(n^2)。假设数组长度为3*n

代码语言:javascript
运行
复制
 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);
    }
   }

交换方法就行了

代码语言:javascript
运行
复制
 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;
   }
  }   
票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/30026653

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档