使用快速排序按列对二维数组进行排序

Question

我想使用快速排序按特定列对二维数组进行排序。我已经能够对一维数组实现快速排序。

public class QuickSort1D {

    public static void main(String[] args) {
        int[] A = {9, 3, 10, 4, 1, 44, 12, 2, 90, 0};
        int l = 0;
        int r = A.length-1;
        QuickSort(A, l, r);
        for (int i = 0; i < A.length; i++){
            System.out.print(A[i] + " ");
        }
    }

    private static void QuickSort(int[] a, int l, int r) {
        int i;
        if (r > l){
            i = partition(a, l, r);
            QuickSort(a, l, i-1);
            QuickSort(a, i+1, r);
        }
    }

    private static int partition(int[] a, int l, int r) {
        int v = a[r];
        int i = l;
        int j = r;
        int temp;
        while (i < j){
            while (a[i] < v){
                i = i + 1;
            }
            while ((i < j) && (a[j] >= v)){
                j = j - 1;
            }
            temp = a[i];
            if (i < j){
                a[i] = a[j];
                a[j] = temp;
            }else{
                a[i] = a[r];
                a[r] = temp;
            }
        }
        return i;
    }
}

为了对二维数组进行此操作，我需要在QuickSort方法中包含指定列的参数。但我不知道该如何继续执行。

例如，初始数组为：

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

第二列排序后的数组应该是

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

- Saiyan

Answer 1

你在快速排序方法中加入了一个参数int column。

然后只需将每个a[x]替换为a[x][column]，而交换方法（带有temp的if else）保持不变。只需将temp更改为int[]而不是int。当然，a的类型必须是int[][]而不是int[]。

完成 :)

- Sibbo

---

如果我理解正确，int[] temp然后temp = a[i]会使temp存储整个行？ - Saiyan

Answer 2

修改了您的代码以对二维数组进行排序。您可以更改columnToSort的值以更改要排序的列。享受吧

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class QuickSort1D {
private static HashMap<Integer, List<Object>> array = new HashMap<Integer, List<Object>>();

public static void main(String[] args) {
    int[][] A = { { 4, 1, 3 }, 
                { 6, 0, 2 }, 
                { 5, 9, 8 }, 
                { 5, 9, 8 },
                { 0, 1, 2 } };
    int l = 0;
    int columnToSort = 0;
    buildarray(A, columnToSort);
    int r = array.keySet().size() - 1;
    Integer[] sorted = QuickSort(array.keySet().toArray(new Integer[array.keySet().size()]), l, r);
    for (int i = 0; i < sorted.length; i++) {
        List<Object> k = array.get(sorted[i]);
        for (Object object : k) {
            int[] ar = (int[]) object;
            for (int j : ar) {
                System.out.print(j);
            }
            System.out.println();
        }
        array.get(sorted[i]).remove(array.get(sorted[i]).size() - 1);
    }
}

private static void buildarray(int[][] a, int columnToSort) {
    for (int[] is : a) {
        List<Object> ls = array.get(is[columnToSort]);
        if (ls != null) {
            ls.add(is);
            continue;
        }
        ls = new ArrayList<Object>();
        ls.add(is);
        array.put(is[columnToSort], ls);
    }

}

private static Integer[] QuickSort(Integer[] a, int l, int r) {
    int i;
    if (r > l) {
        i = partition(a, l, r);
        QuickSort(a, l, i - 1);
        QuickSort(a, i + 1, r);
    }
    return a;
}

private static int partition(Integer[] a, int l, int r) {
    int v = a[r];
    int i = l;
    int j = r;
    int temp;
    while (i < j) {
        while (a[i] < v) {
            i = i + 1;
        }
        while ((i < j) && (a[j] >= v)) {
            j = j - 1;
        }
        temp = a[i];
        if (i < j) {
            a[i] = a[j];
            a[j] = temp;
        } else {
            a[i] = a[r];
            a[r] = temp;
        }
    }
    return i;
}
}

- Jithin Kunjachan