使用选择排序的java排序2D数组

Question

我使用了以下代码-

x[][]是要排序的数组

    void sort() {
    int max1, max2, s;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < column; j++) {
            max1 = i;
            max2 = j;
            for (int k = i; k < row; k++) {
                if (k == i) {   // need to improve this part
                    for (int l = j; l < column; l++) {
                        if (x[k][l] > x[max1][max2]) {
                            max1 = k;
                            max2 = l;
                        }
                    }
                } else {
                    for (int l = 0; l < column; l++) {
                        if (x[k][l] > x[max1][max2]) {
                            max1 = k;
                            max2 = l;
                        }
                    }
                }
            }
            s = x[max1][max2];
            x[max1][max2] = x[i][j];
            x[i][j] = s;
        }
    }
}

我想删除if{}语句，或者这是使用选择排序的另一种方法

（我知道有更简单的方法可以做到这一点，但我正在尝试使用选择排序）

Answer 1

我真的不喜欢你命名变量的方式。我建议对行和列使用r、c作为前缀，对值使用v，然后对数组上的两个循环使用外部和内部作为后缀，对最大值使用Max

使用vMax可以增加算法的内存局部性——通过避免查找内存中较远的部分，它在处理大型数组时应该执行得更快一些。并不是说，与快速排序相比，选择排序永远都不会有竞争力：渐进复杂性仍然很可怕

这使得一切都更容易阅读：

for (int rOuter = 0; rOuter < rows; rOuter++) {
    for (int cOuter = 0; cOuter < cols; cOuter++) {
        // find max value, and swap with rOuter, cOuter            
        int rMax = rOuter;
        int cMax = cOuter;
        int vMax = x[rOuter][cOuter];
        // finish the row current row
        for (int cInner = cOuter+1; cInner < cols; cInner++) {
            if (x[rOuter][cInner] > vMax) {
                rMax = rOuter; 
                cMax = cInner; 
                vMax = x[rOuter][cInner];
            }
        }
        // evaluate remaining rows
        for (int rInner = rOuter+1; rInner < rows; rInner++) {
            for (int cInner = 0; cInner < cols; cInner++) {
                if (x[rInner][cInner] > vMax) {
                   rMax = rInner; 
                   cMax = cInner; 
                   vMax = x[rInner][cInner];
                }
            }
        }            
        // swap. No aux needed, as vMax contains value of max
        x[rMax][cMax] = x[rOuter][cOuter];
        x[rOuter][cOuter] = vMax;
    }
 }

请注意，我已经删除了最里面的条件：它应该执行一次，而且只能执行一次，以在计算所有剩余行之前完成当前行

还要注意的是，我还没有测试过这段代码。这看起来是正确的，但要谨慎对待

Answer 2

就像我提到的，我目前没有测试这个的媒介，但我相信这应该有效。如果不让我知道，我会相应地修改

以下是我的解决方案：

void sort() {
 int max1, max2, count, minValue, rowHold, colHold;
 int[][] tempArr = new int[row][column]; 
 while(count != (row*column)) 
 {
    for (int i = 0; i < row; i++) 
    {
            for (int j = 0; j < column; j++) 
        {
                max1 = i;
                max2 = j;
            if(minValue>x[i][j] && x[i][j] != tempArry[i][j])
            {
                minvalue= x[i][j];
            }



        }

    }

    tempArr[rowHold][colHold] = minVlaue;
    if(colHold<column)
    {
    colHold++;
    }
    else if(colHold=column)
    {
        colHold = 0;
        rowHold++;
    }
    count++;
}   
x = tempArry;

}

此解决方案执行选择排序，效率是当前解决方案的数倍。当前解决方案的问题是嵌套循环太多。嵌套循环会在效率方面产生巨大的问题，因此您希望尽量减少它们的使用和深度

希望这能起作用，如果不能，请发表评论，我会修复它！还有任何关于我做了什么的问题，我会评论和解释我做了什么