如何将数组的元素移动到我想要的顺序？

Question

我正在解决一个问题，它说“给定一个包含 N 个项目的数组，从第一个位置取出该项目并排列该数组，使得该项目处于其最终排序位置并且所有项目 <=该项目在它之前，所有项目 >= 在它之后。列表未排序。只有一个项目处于最终顺序。”我想要做的是对一个数组进行排序，这样我得到的元素小于或等于数组 [0] 中的元素，首先在数组中，然后是 a[0]，在数组的末尾应该大于或等于数组 [0] 的元素。例如，如果我有一个包含 10 个数字的数组，像这样“[3, 2, 8, 1, 9, 5, 1, 9, 5, 9]” 我的新数组应该是“[2, 1, 1, 3 , 8, 9, 5, 9, 5, 9]”。我试过编写下面的代码，但它不能正常工作。我得到的输出是 [3, 5, 1, 2, 9, 9, 1, 9, 8, 5]。有人可以帮我弄清楚如何解决这个问题吗？

import java.util.Arrays;
import java.util.Random;

public class Q1 {
    public static void main(String[] args) {
        int[] d = createRandomIntArray(10);
        System.out.println("Original Array: " + Arrays.toString(d));
        changeOrder(d);
        System.out.println("New Array: " + Arrays.toString(d));
    }

    public static int[] createRandomIntArray(int n) {
        Random random = new Random();

        int[] result = new int[n];

        for (int i = 0; i < n; i++)
            result[i] = random.nextInt(n);

        return result;
    }

    public static void swap(int[] x, int i, int j) {
        int temp = x[i];
        x[i] = x[j];
        x[j] = temp;
    }

    public static void changeOrder(int[] array) {
        int count = 0;
        for (int i = 0; i < array.length - 1; i++) {
            if (array[0] <= array[i + 1]) {
                swap(array, array[0], array[count++]);
            } else if (array[0] >= array[i + 1]) {
                swap(array, array[i + 1], array[array.length - 1]);
            }
        }
    }
}

Answer 1

似乎应该重新考虑该算法只是为了将较低的元素移动到之前head元素从位置0开始：

如果当前元素小于head，旋转从head到当前位置的所有元素向右移动1。

示例实现：

static void arrange(int[] arr) {
    int head = 0;
    for (int i = head + 1; i < arr.length; i++) {
        if (arr[i] < arr[head]) {
            rotate(arr, head, i);
            head++;
        }
    }
}

static void rotate(int[] arr, int head, int i) {
    int tmp = arr[i];
    for (int j = i; j > head; j--) {
        arr[j] = arr[j - 1];
    }
    arr[head] = tmp;
}

测试：

int[] arr = {3, 2, 8, 1, 9, 5, 1, 9, 5, 9};
System.out.println("before: " + Arrays.toString(arr));
arrange(arr);
System.out.println("after:  " + Arrays.toString(arr));

输出：

before: [3, 2, 8, 1, 9, 5, 1, 9, 5, 9]
after:  [2, 1, 1, 3, 8, 9, 5, 9, 5, 9]

int[] arr = {9, 2, 8, 1, 9, 5, 1, 9, 5, 9};
System.out.println("before: " + Arrays.toString(arr));
arrange(arr);
System.out.println("after:  " + Arrays.toString(arr));

输出：

before: [9, 2, 8, 1, 9, 5, 1, 9, 5, 9]
after:  [2, 8, 1, 5, 1, 5, 9, 9, 9, 9]

如何将数组的元素移动到我想要的顺序？

How can I shift the elements of an Array to the order I desire?

java

arrays

swap