使用插入排序对二维数组进行排序

Question

我想使用插入排序按特定列对二维整数数组进行排序。以下代码适用于一维数组。

private static void InsertionSort(int[] a, int n) {

    int key, j;
    for (int i = 1; i < n; i++){
            key = a[i];
            j = i - 1;
            while ((j >= 0) && (a[j] > key)){
                a[j+1] = a[j];
                j = j - 1;
            }
            a[j+1] = key;
    }
}

对于二维数组，我为数组的排序依据列指定了一个整数 c。例如，如果我按第一列排序，

{4, 1, 3},
{6, 0, 2},
{5, 9, 8}

变成

{4, 1, 3},
{5, 9, 8},
{6, 0, 2}

这是我到目前为止按指定列对二维数组进行排序的结果

private static void InsertionSort(int[][] a, int n, int c) {

    in key, j;
    for (int i = 1; i < n; i++){
        key = a[i][c];
        j = i - 1;
        while ((j >= 0) && (a[j][c] > key)){
            a[j+1][c] = a[j][c];
            j = j - 1;
        }
        a[j+1][c] = key;
    }
}

但是按第一列排序的结果是

{4, 1, 3}
{5, 0, 2}
{6, 9, 8}

它对第一列的元素进行排序，而不将它们与各自的行放在一起。我该如何解决这个问题？

Answer 1

您需要交换数据行，而不仅仅是数据元素。

private static void sort(int[][] a, int n, int c) {
    int key, j;
    for (int i = 1; i < n; i++){
        key = a[i][c];
        int[] keyRow = a[i];
        j = i - 1;
        while ((j >= 0) && (a[j][c] > key)){
            //a[j+1][c] = a[j][c];
            a[j+1] = a[j];
            j = j - 1;
        }
        //a[j+1][c] = key;
        a[j+1] = keyRow;
    }
}

Answer 2

从Java8开始，一行就可以了。

Arrays.sort(data, (a, b) -> a[COL] - b[COL]);

其中 COL 是要排序的列。

使用插入排序对二维数组进行排序

Sort 2D array using insertion sort

java

sorting

multidimensional-array

insertion-sort