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

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);

    }

}

Answer 2

看看这个简单的例子：

public static void main(String[] args) {

        Integer[] listOfNumbers = {1,4,5,6,74,2,7,8,5,2,6,989,3};

        //sort by number 6

        FirstCustomComparator comparator = new FirstCustomComparator(6);

        Arrays.sort(listOfNumbers, 0, listOfNumbers.length, comparator);

        for (int number : listOfNumbers) {

            System.out.print(number+" ");

        }

    }

第一定制比较器类：

public class FirstCustomComparator implements Comparator<Integer> {

    private final int exception;

    public FirstCustomComparator(int i)

    {

        exception = i;

    }

    @Override

    public int compare(Integer a, Integer b)

    {

        if (a < exception)

        {

                return -1;

        }

        return a.compareTo(b);

    }

}