使用多維數組的InsertionSort

Question

在我的代碼中，我在第一行收到值n和d。 N將是我想要寫入的值的數量，d是每個位置n中的數字的數量。 因此，在接下來的n個值中，我引入了d值。這個練習的要點是使用插入排序，但如果第一個座標相等，則比較第二個，如果再次發生，則比較第三個，依此類推。例如： 輸入：

5 3 
1 1 1 
1 0 1 
1 1 0 
0 1 1 
0 1 0 

輸出：

0 1 0 
0 1 1 
1 0 1 
1 1 0 
1 1 1 

這是我的代碼：

public static void main(String[] args) { 
    int n,d,aux; 
    Scanner sc = new Scanner(System.in); 

    n = sc.nextInt(); 
    d = sc.nextInt(); 
    int tab [][] = new int[n][d]; 
    for(int i=0;i<n;i++){ 
     for(int j=0;j<d;j++){ 
      aux = sc.nextInt(); 
      tab[i][j] = aux; 
     } 
    } 
    insertionSort(tab,d); 
    System.out.println("---"); 
    for(int u=0;u<tab.length;u++){ 
     for(int y=0;y<d;y++){ 
      System.out.print(tab[u][y]+" "); 
     } 
     System.out.println(); 
    } 
} 
public static void insertionSort(int tab[][],int d){ 
    int i,j; 
    int pos = 0; 
    int tmp [][] = new int[1][d]; 
    for(i = 1;i < tab.length;i++) 
    { 
     for(int k=0;k<d;k++) 
      tmp[0][k] = tab[i][k]; 

     for(j = i; j>0 && tmp[0][0] <= tab[j-1][0];j--) 
     { 
      while(tmp[0][pos] == tab[j-1][pos] && pos+1<d){ 
       pos++; 
       if(tmp[0][pos] < tab[j-1][pos]){ 
        pos=0; 
        break; 
       } 
      } 
      if(pos==0){ 
       for(int k=0;k<d;k++) 
        tab[j][k] = tab[j-1][k]; 
      } 
     } 
     for(int k=0;k<d;k++) 
      tab[j][k] = tmp[0][k]; 
     pos = 0; 
    } 
} 

的問題是，我的輸出是錯誤的：

0 1 0 
0 1 1 
1 1 0 
1 1 1 
1 1 1 

Answer 1

我爲喲找到了解決方案ü用遞歸，用下面的代碼，你可以整理你的多維二元陣列，以二進制排序格式（我這裏使用常量數組，您可以將您的掃描儀，以獲取來自控制檯輸入）：

public static void main(String[] args) 
    { 
    int n, d; 

    int tab[][] = new int[][] { { 1, 1, 1, 1 }, { 1, 0, 1, 1 }, { 1, 1, 0, 0 }, { 0, 0, 0, 1 }, 
     { 0, 1, 0, 1 }, { 0, 0, 0, 1 } }; 
    n = 6; 
    d = 4; 
    System.out.println("---"); 
    for (int u = 0; u < tab.length; u++) 
    { 
     for (int y = 0; y < d; y++) 
     { 
     System.out.print(tab[u][y] + " "); 
     } 
     System.out.println(); 
    } 

    insertionSort(tab, n); 

    System.out.println("---"); 
    for (int u = 0; u < tab.length; u++) 
    { 
     for (int y = 0; y < d; y++) 
     { 
     System.out.print(tab[u][y] + " "); 
     } 
     System.out.println(); 
    } 
    } 

    public static void insertionSort(int tab[][], int n) 
    { 
    doSort(tab, 0, n, 0); 
    } 

    /** 
    * Recurring Method for Insertion Sort in MulitDimentional array. 
    * 
    * @param tab mulitidiamentional array. 
    * @param rowsStart the rows start index 
    * @param rowEnd the row end index 
    * @param column the current column 
    */ 
    public static void doSort(int tab[][], int rowsStart, int rowEnd, int column) 
    { 
    int totalColumn = tab[0].length; 
    for (int j = rowsStart; j < rowEnd; j++) 
    { 
     for (int k = j + 1; k < rowEnd; k++) 
     { 
     if (tab[j][column] > tab[k][column]) 
     { 
      for (int l = column; l < totalColumn; l++) 
      { 
      int t = tab[j][l]; 
      tab[j][l] = tab[k][l]; 
      tab[k][l] = t; 
      } 
     } 
     } 
    } 

    int value = tab[rowsStart][column]; 
    if (rowEnd - rowsStart > 2) 
    { 
     for (int i = rowsStart; i < rowEnd; i++) 
     { 
     if (value != tab[i][column]) 
     { 
      doSort(tab, rowsStart, i, column + 1); 
      value = tab[i][column]; 
      rowsStart = i; 
     } 
     } 
    } 
    if (column < totalColumn - 1) 
    { 
     doSort(tab, rowsStart, rowEnd, column + 1); 
    } 
    }