java - 将较大的数字向右移动，将较小的数字向左移动给定值

Question

我有一个家庭作业问题，给了我这个数组:

[3、22、1、5、6、10、4]

我需要将所有大于最后一个值 4 的数字移至该值的右侧，并将所有小于该值的值移至左侧。

数字不一定需要按顺序排列。因此，程序的输出将是:

[3、1、4、22、5、6、10]

出于某种原因，我真的很难想出一种算法来实现这种情况。我尝试创建一个循环，将最后一个值与较大的数字交换，但是如果最小值混合在数组中的某个奇怪位置，它将位于不正确的值的右侧。

谁能帮我解决这个问题吗？

Answer 1

我不会帮你完成作业。但我会引导你思考你的这个例子的走向。这是快速排序的第一步——对数组进行分区。

public class QuickSortImpl {

    private static void swap(int[] array, int l, int h) {
        int temp = array[h];
        array[h] = array[l];
        array[l] = temp;
    }

    public static int partition(int[] array, int low, int high) {
        int pivot = high;
        int firsthigh = low;
        int x,y;

        for (int i = low; i < high; i++) {
            x = array[i];
            y = array[pivot];
            if (array[i] < array[pivot]) {
                swap(array, i, firsthigh);
                firsthigh++;
            }
        }
        swap(array, pivot, firsthigh);
        return firsthigh;
    }

    private static void printArray(int[] arr ) {
        for ( int i =0; i < arr.length; i++ ) {
            System.out.print(" " + arr[i]);
        }
        System.out.println();
    }

    public static void quickSort(int[] array, int low, int high) {
        if ( low < high ) {
            int pivot = partition(array, low, high);
            quickSort(array, low, pivot - 1);
            quickSort(array, pivot + 1, high); 
        }
    }

    public static void main(String[] args) {
        int[] arr = { 3, 22, 1, 5, 6, 10, 4};
        quickSort(arr, 0, arr.length -1 );
        printArray(arr);
    }
}