当前位置: 首页 > 知识库问答 >
问题:

带置换数组的Insertionsort(Java)

东门清夷
2023-03-14
( 4 1 2 3 )= arr[0] ,
( 1 2 3 4 )=arr[1] ,
( 4 3 2 1 ) = arr[2], 
( 3 1 2 4 )= arr[3] ,
( 4 3 1 2 ) = arr[4] ,
( 2 1 3 4 ) = arr[5] ,
( 4 1 3 2 ) = arr[6] ,
( 1 4 2 3 )= arr[7] 
(3,1,2,4) < (4,1,2,3) < (1,4,2,3) < (2,1,3,4) < (4,1,3,2) < (4,3,1,2) < (1,2,3,4) < (4,3,2,1)
public int insertionsort(permutation[] arr, int gap) {
            int count = 0;
                for (int i = gap; i<arr.length-1; i++) {
                    count++;
                    permutation new = arr[i];
                    int k = i;
                    System.out.println("K: " + k);
                    System.out.println("gap: "+ gap);
                    while(Math.abs(arr[i].value(1)-arr[i].value(4)) > Math.abs(arr[i-gap].value(1) - 
                    arr[i-gap].value(4))) {
                        arr[k] = arr[k-gap];
                        k = k-gap;
                        System.out.println("k-gap: " + (k-gap));
                    }
                    arr[k] = new;
                }

        return count;
        } 

共有1个答案

隆兴修
2023-03-14

我不清楚gap参数的用途,希望您可以在需要时将其合并,但这里有一个标准插入排序方法的Java直接转换。

static void sort(permutation[] perms)
{
    for(int i=1; i<perms.length; i++)
    {
        permutation fixed = perms[i];
        int j = i - 1;
        while(j >= 0 && perms[j].compareTo(fixed) > 0)
        {
            perms[j+1] = perms[j];
            j -= 1;
        }
        perms[j+1] = fixed;
    }
}

猜测置换类可能是什么样子:

static class permutation
{
    int len;
    int[] arr;

    public permutation(int... vals)
    {
        len = vals.length;
        arr = vals.clone();
    }

    int value(int pos) 
    {
        return arr[pos-1];
    }

    public int compareTo(permutation p)
    {
        int cmp = Math.abs(value(1)-value(len)) - Math.abs(p.value(1)-p.value(len));
        if(cmp == 0)
            for(int i=1; cmp==0 && i<=len; i++)
                cmp = value(i)-p.value(i);
        return cmp;
    }
}

测试:

permutation[] perms = {
        new permutation(4,1,2,3),
        new permutation(1,2,3,4),
        new permutation(4,3,2,1),
        new permutation(3,1,2,4),
        new permutation(4,3,1,2),
        new permutation(2,1,3,4),
        new permutation(4,1,3,2),
        new permutation(1,4,3,2)
};

sort(perms);

for(permutation p : perms)
    System.out.println(Arrays.toString(p.arr));
[1, 4, 3, 2]
[3, 1, 2, 4]
[4, 1, 2, 3]
[2, 1, 3, 4]
[4, 1, 3, 2]
[4, 3, 1, 2]
[1, 2, 3, 4]
[4, 3, 2, 1]
 类似资料:
  • 问题内容: 例如我有这个数组: 我需要列出所有排列,以便如果一个像这样,则其他排列一定不能相同。我知道,如果数组的长度为n,那么就有n!可能的组合。该算法如何编写? 更新:谢谢,但是我需要一个伪代码算法,例如: 只是算法。是的,API函数很好,但是对我没有太大帮助。 问题答案: 如果使用的是C ++,则可以std::next_permutation从头文件使用:

  • 我试图用arraylist创建一个插入排序程序,但在其中的一些内容上出现了错误。 每当我尝试运行我的程序时,它都会说: 异常在线程"main"java.lang.IndexOutOfBounds异常:索引: 5,大小: 5在java.util.ArrayList.range检查(ArrayList.java:635)在java.util.ArrayList.get(ArrayList.java:4

  • 如果你以前遇到过这些问题,请给我一些建议。 提前感谢!

  • 设置-Javascript|MDN 示例:迭代集 第16行 上产生错误< code >未捕获的语法错误:意外的令牌 < code >定制和控制Google Chrome 是我做错了什么还是这个功能不被支持? 更新: 我进入< code>chrome://flags并勾选了< code >启用实验性JavaScript。然后重新启动我的浏览器,但我仍然得到同样的错误。我想我只能等到那个特性被正确添加

  • 此时,我使用的开关盒如下: 我想做的是有一个这样的数组或字符串: 这可能吗? 如果是怎样?