存储桶排序算法代码问题

Question

我需要在java中实现以下内容。

输入：整数数组

输出：重新排列数组以具有以下内容：

假设原始数组中的第一个元素的值为x在新数组中，假设 x 位于位置 I，即data[I] = x。然后，为所有x和所有j > Idata[j] <= x.这意味着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。

问题源于我尝试创建一个名为bucket的新数组的第一行。我将不胜感激任何建议！谢谢！

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

您可以使用的另一种方法是使用快速排序的标准分区算法。

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

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 

希望对您有所帮助！