桶排序算法代码问题

Question

我需要用java实现以下内容。

输入:整数数组

输出:重新排列数组，使其具有以下内容：

假设原始数组中的第一个元素在新数组中有值x，假设x位于位置I，即data[I] = x。然后，data[j] <= x代表所有的x和所有的j > I。这意味着x“左”的所有值都小于或等于x，而“右边”的所有值都大于x。

一个示例如下:假设数组的元素按这个初始顺序排列: 4、3、9、2、7、6、5。应用算法后，您应该得到:3、2、4、5、9、7、6。也就是说，最左边的元素4位于结果数组中，因此所有小于4 (2和3)的元素都位于其左侧(没有特别的顺序)，大于4的所有元素都位于其右侧(没有特别的顺序)。

该算法不需要空间，只需在O(n)时间内求解。我已经实现了一个桶类，但是在代码方面遇到了一些困难。

public class Problem4 
{
    public static void partition(int[] A)
    {
        int x = A[0];
        int l = A.length;
        int[] bucket = int [];      
        for(int i=0; i<bucket.length; i++){
            bucket[i]=0;
        }
        for (int i=0; i<l; i++){
            bucket[x[i]]++;
        }
        int outPos=0;
        for(int i=0; i<bucket.length; i++){
            for(int j=0; j<bucket[i]; j++){
                x[outPos++]=i;
            }
        }
     }



    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = {4,3,9,2,7,6,5};

        System.out.println("Before partition:");
        for(int i = 0; i < A.length; i++)
        {
            System.out.print(A[i] + " ");
        }       
        partition(A);

        System.out.println("After partition:");

        System.out.println("Before partition:");
        for(int i = 0; i < A.length; i++)
        {
            System.out.print(A[i] + " ");           
        }           
    }
}

台词：

• int[] bucket = int[]，
• bucket[x[i]]++;，和
• x[outpost++] = i；

给我带来麻烦。我收到错误了

表达式的类型必须是数组类型，但被解析为int。

这个问题源于我正在尝试创建一个名为桶的新数组的第一行。如有任何建议，我将不胜感激！谢谢!

Answer 1

我不认为你需要用水桶。相反，您可以简单地遍历数组，在前面放置小于拆分值的元素，在后面放置大于拆分值的元素。我们可以使用两个变量，front和back来跟踪数组前后的插入位置。从数组中的位置1开始，如果值小于我们放置在front和增量front和当前索引中的拆分值。如果值更大，我们将其与back和递减back的值交换，但保留当前索引。

下面是一些代码来说明：

public static void main(String[] args)
{
    int[] A = {4,3,9,2,7,6,5};      
    sort(A);        
    System.out.println(Arrays.toString(A));
}

public static void sort(int[] arr)
{
    int split = arr[0];

    int front = 0;
    int back = arr.length-1;
    for(int i=1; front != back; )
    {
        if(arr[i] <= split)
        {
            arr[front] = arr[i];
            front += 1;
            i++;
        }
        else
        {
            swap(arr, i, back);
            back -= 1;
        }
    }
    arr[front] = split;
}

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

输出：

[3, 2, 4, 7, 6, 5, 9]

Answer 2

可以使用的另一种方法是使用QuickSort的标准分区算法。

我已经修改了您的代码和下面的代码

public class Problem4 
{

    /* This function takes last element as pivot,
       places the pivot element at its correct
       position in sorted array, and places all
       smaller (smaller than pivot) to left of
       pivot and all greater elements to right
       of pivot */
    public static int partition(int arr[], int low, int high)
    {
        int pivot = arr[high]; 
        int i = (low-1); // index of smaller element
        for (int j=low; j<high; j++)
        {
            // If current element is smaller than or
            // equal to pivot
            if (arr[j] <= pivot)
            {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;

        return i+1;
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = {4,3,9,2,7,6,5};

        System.out.println("Before partition:");
        for(int i = 0; i < A.length; i++)
        {
            System.out.print(A[i] + " ");
        }       

        // swap and call the standard partition algo of QuickSort 
        // on last element pivot. swap arr[low] and arr[high]
        int low = 0;
        int high = A.length-1;

        int temp = A[low];
        A[low] = A[high];
        A[high] = temp;

        partition(A, low, high);

        System.out.println("\nAfter partition:");

        for(int i = 0; i < A.length; i++)
        {
            System.out.print(A[i] + " ");           
        }   
    }
}

输出

Before partition:
4 3 9 2 7 6 5 
After partition:
3 2 4 5 7 6 9 

希望能帮上忙！