Bucket-Sortierung in Java

Die Sortiertechnik, mit der die Elemente des gegebenen Arrays auf viele Buckets verteilt werden, um jeden Bucket mithilfe verschiedener Sortieralgorithmen oder durch rekursive Verwendung des Bucket-Sortieralgorithmus zu sortieren, wird in Java Bucket-Sortierung genannt, dessen Raumkomplexität O ist (1), die Komplexität im ungünstigsten Fall ist O(n^2), die Komplexität im besten Fall ist Omega(n+k) und die durchschnittliche Komplexität ist Theta(n+k), und die Bucket-Sortiertechnik zum Sortieren der gegebenen Elemente des Arrays funktioniert eine höhere Geschwindigkeit im Vergleich zu anderen Sortieralgorithmen und die Elemente des Arrays, die mit dem Bucket-Sortieralgorithmus sortiert werden sollen, müssen gleichmäßig verteilt sein.

Starten Sie Ihren kostenlosen Softwareentwicklungskurs

Webentwicklung, Programmiersprachen, Softwaretests und andere

Die Funktion zum Durchführen einer Bucket-Sortierung in Java lautet wie folgt:

public static int[] bucketsort(int[] array, int maximum_value)
{
int[] newbucket = new int[maximum_value + 1];
int[] sorted_array = new int[array.length];
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}

wobei array das Eingabearray ist, das mit dem Bucket-Sortieralgorithmus sortiert werden soll, Maximum_value der im gegebenen Array vorhandene Maximum_value und sorted_array das resultierende Array ist, das aus sortierten Elementen besteht.

Funktionsweise des Bucket-Sort-Algorithmus in Java

Der Bucket-Sortieralgorithmus in Java funktioniert wie folgt:

• Der erste Schritt im Bucket-Sortieralgorithmus besteht darin, ein leeres Array zu erstellen, das als Buckets betrachtet wird.
• Der zweite Schritt besteht darin, das gesamte Eingabearray zu durchlaufen, dessen Elemente sortiert werden sollen, und jedes Element dem Bucket hinzuzufügen.
• Der dritte Schritt besteht darin, jedes Element in den Buckets zu sortieren.
• Der vierte Schritt besteht darin, alle Elemente in den Buckets zu durchlaufen und jedes einzelne davon in sortierter Reihenfolge zum ursprünglichen Eingabearray hinzuzufügen.

Beispiele für Bucket Sort in Java

Im Folgenden finden Sie Beispiele:

Beispiel #1

Java-Programm zum Sortieren der Elemente des angegebenen Arrays durch Implementierung des Bucket-Sortieralgorithmus und anschließende Anzeige der sortierten Elemente des Arrays als Ausgabe auf dem Bildschirm:

 Code:

import java.util.*;
public class Main
{
public static int[] bucketsort(int[] array, int maximum_value)
{
//creating an empty array called newbucket which is considered as bucket array
int[] newbucket = new int[maximum_value + 1];
//creating another empty array called sorted_array to store the result array
int[] sorted_array = new int[array.length];
//traversing through the input array to add each element to the bucket array
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
//sorting each element in the bucket array and adding each sorted element in order to the original input array
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}
//function to find the maximum value in the input array in order to sort the given array using bucket sort technique
static int maximumValue(int[] array)
{
int maximum_value = 0;
for (int d = 0; d < array.length; d++)
if (array[d] > maximum_value)
maximum_value = array[d];
return maximum_value;
}
//main function is called within which we display the resulting array
public static void main(String args[])
{
int[] array ={100, 90, 80, 70, 60, 50, 40, 30, 20, 10};
int maximum_value = maximumValue(array);
System.out.print("\nThe elements of the array to be sorted are:\n ");
System.out.println(Arrays.toString(array));
System.out.print("\nThe elements of the sorted array sorted using bucket sort algorithm are:\n ");
System.out.println(Arrays.toString(bucketsort(array,maximum_value)));
}
}

Ausgabe:

Im obigen Programm erstellen wir ein leeres Array namens newbucket, das als Bucket-Array betrachtet wird. Dann erstellen wir ein weiteres leeres Array namens sorted_array, um das Ergebnisarray zu speichern. Dann durchlaufen wir das Eingabearray, um jedes Element zum Bucket-Array hinzuzufügen. Dann sortieren wir jedes Element im Bucket-Array und fügen jedes sortierte Element der Reihe nach zum ursprünglichen Eingabearray hinzu. Dann definieren wir eine Funktion, um den Maximalwert im Eingabearray zu finden, um das gegebene Array mithilfe der Bucket-Sortiertechnik zu sortieren. Dann wird die Hauptfunktion aufgerufen, innerhalb derer wir das resultierende Array anzeigen. Die Ausgabe ist im Schnappschuss oben dargestellt.

Beispiel #2

Java-Programm zum Sortieren der Elemente des angegebenen Arrays durch Implementierung des Bucket-Sortieralgorithmus und anschließende Anzeige der sortierten Elemente des Arrays als Ausgabe auf dem Bildschirm:

Code:

import java.util.*;
public class Main
{
public static int[] bucketsort(int[] array, int maximum_value)
{
//creating an empty array called newbucket which is considered as bucket array
int[] newbucket = new int[maximum_value + 1];
//creating another empty array called sorted_array to store the result array
int[] sorted_array = new int[array.length];
//traversing through the input array to add each element to the bucket array
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
//sorting each element in the bucket array and adding each sorted element in order to the original input array
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}
//function to find the maximum value in the input array in order to sort the given array using bucket sort technique
static int maximumValue(int[] array)
{
int maximum_value = 0;
for (int d = 0; d < array.length; d++)
if (array[d] > maximum_value)
maximum_value = array[d];
return maximum_value;
}
//main function is called within which we display the resulting array
public static void main(String args[])
{
int[] array ={ 60, 80, 50, 90, 30, 70, 20 };
int maximum_value = maximumValue(array);
System.out.print("\nThe elements of the array to be sorted are:\n ");
System.out.println(Arrays.toString(array));
System.out.print("\nThe elements of the sorted array sorted using bucket sort algorithm are:\n ");
System.out.println(Arrays.toString(bucketsort(array,maximum_value)));
}
}

Ausgabe:

Im obigen Programm erstellen wir ein leeres Array namens „Neuer Bucket“, der als Bucket-Array betrachtet wird. Dann erstellen wir ein weiteres leeres Array namens sorted_array, um das Ergebnisarray zu speichern. Dann durchlaufen wir das Eingabearray, um jedes Element zum Bucket-Array hinzuzufügen. Dann sortieren wir jedes Element im Bucket-Array und fügen jedes sortierte Element der Reihe nach zum ursprünglichen Eingabearray hinzu. Dann definieren wir eine Funktion, um den Maximalwert im Eingabearray zu finden, um das gegebene Array mithilfe der Bucket-Sortiertechnik zu sortieren. Dann wird die Hauptfunktion aufgerufen, innerhalb derer wir das resultierende Array anzeigen. Die Ausgabe ist im Schnappschuss oben dargestellt.

Das obige ist der detaillierte Inhalt vonBucket-Sortierung in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!