import java.util.Random;
/**
* Sortiertestklasse
*
* Die Klassifizierung der Sortieralgorithmen ist wie folgt: 1. Einfügungssortierung (direkte Einfügungssortierung, halbe Einfügungssortierung, Hill-Sortierung); 2. Austauschsortierung (Blasensortierung, schnelle Sortierung);
* 3. Auswahlsortierung (Direktauswahlsortierung, Heap-Sortierung); 4. Zusammenführungssortierung; 5. Radix-Sortierung.
*
* Zur Wahl der Sortiermethode: (1) Wenn n klein ist (z. B. n ≤ 50), kann die Sortierung durch direkte Einfügung oder direkte Auswahl verwendet werden.
* Wenn die Datensatzgröße klein ist, ist die direkte Einfügungssortierung besser. Andernfalls ist die direkte Auswahlsortierung besser, da die Anzahl der durch direkte Auswahl verschobenen Datensätze geringer ist als bei der direkten Einfügung.
* (2) Wenn der Anfangszustand der Datei grundsätzlich in Ordnung ist (bezogen auf die positive Reihenfolge), sollte Direkteinfügung, Blasensortierung oder zufällige Schnellsortierung verwendet werden;
* (3) Wenn n groß ist, sollte eine Sortiermethode mit einer Zeitkomplexität von O(nlgn) verwendet werden: schnelle Sortierung, Heap-Sortierung oder Zusammenführungssortierung.
*
*/
öffentliche Klasse Sortieren {
/**
* Methode zum Initialisieren des Testarrays
*
* @return ein initialisiertes Array
*/
public int[] createArray() {
Zufällig random = new Random();
int[] array = new int[10];
for (int i = 0; i < 10; i++) {
array[i] = random.nextInt(100) - random.nextInt(100); // Erzeuge zwei Zufallszahlen und subtrahiere sie, um sicherzustellen, dass die generierten Zahlen negative Zahlen enthalten.
}
System.out.println("==========original sequence==========");
printArray(array);
Array zurückgeben;
}
/**
* Drucken Sie die Elemente im Array auf der Konsole
*
* @param-Quelle
*/
public void printArray(int[] data) {
for (int i : data) {
System.out.print(i + " ");
}
System.out.println();
}
/**
* Tauschen Sie die Positionen der beiden angegebenen Elemente im Array aus
*
* @param-Daten
* @param x
* @param y
*/
private void swap(int[] data, int x, int y) {
int temp = data[x];
Daten[x] = Daten[y];
data[y] = temp;
}
/**
* Blasensortierung – eine Art Austauschsortierung
* Methode: Vergleichen Sie zwei benachbarte Elemente und tauschen Sie sie bei Bedarf aus. Nach Abschluss jedes Zyklus wird das größte Element als letztes eingestuft (z. B. Sortieren von klein nach groß). Der nächste Zyklus führt ähnliche Operationen für andere Zahlen aus.
* Leistung: Anzahl der Vergleiche O(n^2),n^2/2; Anzahl der Austausche O(n^2),n^2/4
*
* @param-Daten
* Zu sortierendes Array
* @param sortType
* Sortierart
* @zurückkehren
*/
public void bubbleSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Positive Sortierung, von klein nach groß
// Anzahl der Vergleichsrunden
for (int i = 1; i < data.length; i++) {
// Vergleiche zwei benachbarte Zahlen und die größere Zahl wird angezeigt.
for (int j = 0; j < data.length - i; j++) {
if (Daten[j] > Daten[j + 1]) {
// Zwei benachbarte Zahlen vertauschen
swap(data, j, j + 1);
}
}
}
} else if (sortType.equals("desc")) { // In umgekehrter Reihenfolge sortieren, von groß nach klein
// Anzahl der Vergleichsrunden
for (int i = 1; i < data.length; i++) {
// Vergleiche zwei benachbarte Zahlen und die größere Zahl wird angezeigt.
for (int j = 0; j < data.length - i; j++) {
if (data[j] < data[j + 1]) {
// Zwei benachbarte Zahlen vertauschen
swap(data, j, j + 1);
}
}
}
} anders {
System.out.println("Der von Ihnen eingegebene Sortiertyp ist falsch!");
}
printArray(data);//Gib den Array-Wert nach der Blasensortierung aus
}
/**
* Direktauswahl-Sortiermethode ---- eine Art Auswahlsortierung
* Methode: In jedem Durchgang wird das kleinste (oder größte) Element aus den zu sortierenden Datenelementen ausgewählt und die Reihenfolge wird am Ende des sortierten Arrays platziert, bis alle zu sortierenden Datenelemente angeordnet sind.
* Leistung: Anzahl der Vergleiche O(n^2),n^2/2
* Anzahl der Austausche O(n),n
* Die Anzahl der Austausche ist viel geringer als bei der Blasensortierung. Da der Austausch mehr CPU-Zeit erfordert als der Vergleich, ist die Auswahlsortierung schneller als die Blasensortierung.
* Wenn N jedoch relativ groß ist, dominiert die für den Vergleich erforderliche CPU-Zeit, sodass sich die Leistung zu diesem Zeitpunkt nicht wesentlich von der der Blasensortierung unterscheidet, aber zweifellos schneller ist.
*
* @param-Daten
* Zu sortierendes Array
* @param sortType
* Sortierart
* @zurückkehren
*
*/
public void selectSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Positive Sortierung, von klein nach groß
int-Index;
for (int i = 1; i < data.length; i++) {
Index = 0;
for (int j = 1; j <= data.length - i; j++) {
if (Daten[j] > Daten[Index]) {
index = j;
}
}
// Tauschen Sie die beiden Zahlen an Position data.length-i und index aus (Maximalwert)
swap(data, data.length - i, index);
}
} else if (sortType.equals("desc")) { // In umgekehrter Reihenfolge sortieren, von groß nach klein
int-Index;
for (int i = 1; i < data.length; i++) {
Index = 0;
for (int j = 1; j <= data.length - i; j++) {
if (data[j] < data[index]) {
index = j;
}
}
// Tauschen Sie die beiden Zahlen an Position data.length-i und index aus (Maximalwert)
swap(data, data.length - i, index);
}
} anders {
System.out.println("Der von Ihnen eingegebene Sortiertyp ist falsch!");
}
printArray(data);//Gib den Array-Wert nach direkter Auswahlsortierung aus
}
/**
*
* Einfügungssortierung
*
* Methode: Fügen Sie einen Datensatz in eine sortierte geordnete Liste (möglicherweise eine leere Liste) ein und erhalten Sie so eine neue geordnete Liste mit einer um 1 erhöhten Anzahl von Datensätzen.
* Leistung: Anzahl der Vergleiche O(n^2),n^2/4
* Anzahl der Kopien O(n),n^2/4
* Die Anzahl der Vergleiche ist der Durchschnitt zwischen den ersten beiden und das Kopieren erfordert weniger CPU-Zeit als das Auslagern, sodass die Leistung mehr als doppelt so hoch ist wie die der Blasensortierung und schneller als die der Auswahlsortierung.
*
* @param-Daten
* Zu sortierendes Array
* @param sortType
* Sortierart
*/
public void insertSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Positive Sortierung, von klein nach groß
// Anzahl der Vergleichsrunden
for (int i = 1; i < data.length; i++) {
// Stellen Sie sicher, dass die ersten i+1 Zahlen sortiert sind
for (int j = 0; j < i; j++) {
if (Daten[j] > Daten[i]) {
// Vertausche die beiden Zahlen an den Positionen j und i
swap(data, i, j);
}
}
}
} else if (sortType.equals("desc")) { // In umgekehrter Reihenfolge sortieren, von groß nach klein
// Anzahl der Vergleichsrunden
for (int i = 1; i < data.length; i++) {
// Stellen Sie sicher, dass die ersten i+1 Zahlen sortiert sind
for (int j = 0; j < i; j++) {
if (data[j] < data[i]) {
// Vertausche die beiden Zahlen an den Positionen j und i
swap(data, i, j);
}
}
}
} anders {
System.out.println("Der von Ihnen eingegebene Sortiertyp ist falsch!");
}
printArray(data);//Gib den Array-Wert nach der Einfügungssortierung aus
}
/**
*
* Methode zum Umkehren eines Arrays
*
* @param-Daten
* Quellarray
*/
public void reverse(int[] data) {
int length = data.length;
int temp = 0;//temporäre Variable
for (int i = 0; i < length / 2; i++) {
temp = data[i];
data[i] = data[length - 1 - i];
Daten[Länge - 1 - i] = temp;
}
printArray(data);//Gib den Wert an das konvertierte Array aus
}
/**
*
* Schnelle Sortierung
*
* Die Schnellsortierung verwendet die Divide-and-Conquer-Strategie, um eine Sequenz (Liste) in zwei Untersequenzen (Unterlisten) zu unterteilen.
*
*Die Schritte sind:
* 1. Wählen Sie ein Element aus der Sequenz aus, das als „Pivot“ bezeichnet wird.
* 2. Ordnen Sie die Reihenfolge neu an, sodass alle Elemente, die kleiner als der Basiswert sind, vor der Basis platziert werden und alle Elemente, die größer als der Basiswert sind, hinter der Basis platziert werden (die gleiche Zahl kann auf beiden Seiten platziert werden). Nach dieser Aufteilung befindet sich das Datum an seiner endgültigen Position. Dies wird als Partitionsvorgang bezeichnet.
* 3. Sortieren Sie das Subarray der Elemente, die kleiner als der Basiswert sind, und das Subarray der Elemente, die größer als der Basiswert sind, rekursiv.
*
* Der unterste Fall einer Rekursion liegt vor, wenn die Größe des Arrays Null oder Eins ist, das heißt, es wurde immer sortiert. Obwohl er ständig rekursiv ist, endet dieser Algorithmus immer, da er in jeder Iteration (Iteration) mindestens ein Element an seine endgültige Position verschiebt.
*
* @param-Daten
* Zu sortierendes Array
* @param niedrig
* @param hoch
* @see SortTest#qsort(int[], int, int)
* @see SortTest#qsort_desc(int[], int, int)
*
*/
public void quickSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Positive Sortierung, von klein nach groß
qsort_asc(data, 0, data.length - 1);
} else if (sortType.equals("desc")) { // In umgekehrter Reihenfolge sortieren, von groß nach klein
qsort_desc(data, 0, data.length - 1);
} anders {
System.out.println("Der von Ihnen eingegebene Sortiertyp ist falsch!");
}
}
/**
*
* Spezifische Implementierung der Schnellsortierung, Sortierung in der richtigen Reihenfolge
*
* @param-Daten
* @param niedrig
* @param hoch
*/
private void qsort_asc(int data[], int low, int high) {
int i, j, x;
if (low < high) { // Diese Bedingung wird verwendet, um die Rekursion zu beenden
i = niedrig;
j = hoch;
x = Daten[i];
while (i < j) {
while (i < j && data[j] > x) {
j--; // Finde die erste Zahl kleiner als x von rechts nach links
}
wenn (i < j) {
Daten[i] = Daten[j];
i++;
}
while (i < j && data[i] < x) {
i++; // Finde die erste Zahl größer als x von links nach rechts
}
wenn (i < j) {
Daten[j] = Daten[i];
J--;
}
}
Daten[i] = x;
qsort_asc(data, low, i - 1);
qsort_asc(data, i + 1, high);
}
}
/**
*
* Spezifische Implementierung der Schnellsortierung, Sortierung in umgekehrter Reihenfolge
*
* @param-Daten
* @param niedrig
* @param hoch
*
*/
private void qsort_desc(int data[], int low, int high) {
int i, j, x;
if (low < high) { // Diese Bedingung wird verwendet, um die Rekursion zu beenden
i = niedrig;
j = hoch;
x = Daten[i];
while (i < j) {
while (i < j && data[j] < x) {
j--; // Finde die erste Zahl kleiner als x von rechts nach links
}
wenn (i < j) {
Daten[i] = Daten[j];
i++;
}
while (i < j && data[i] > x) {
i++; // Finde die erste Zahl größer als x von links nach rechts
}
wenn (i < j) {
Daten[j] = Daten[i];
J--;
}
}
Daten[i] = x;
qsort_desc(data, low, i - 1);
qsort_desc(data, i + 1, high);
}
}
/**
*
* Binäre Suche nach der Position einer bestimmten Ganzzahl in einem Ganzzahl-Array (rekursiv)
*
* Die lineare Suchliste muss eine geordnete Liste sein
*
* @paramdataset
* @paramdata
* @parambeginIndex
* @paramendIndex
* @returnindex
*
*/
public int binarySearch(int[] dataset, int data, int beginIndex,int endIndex) {
int midIndex = (beginIndex + endIndex) >>> 1; // Entspricht mid = (low + high)
// / 2, aber die Effizienz wird höher sein
if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex)
return -1;
if (data < dataset[midIndex]) {
return binarySearch(dataset, data, beginIndex, midIndex - 1);
} else if (data > dataset[midIndex]) {
return binarySearch(dataset, data, midIndex + 1, endIndex);
} anders {
return midIndex;
}
}
/**
*
* Binäre Suche nach der Position einer bestimmten Ganzzahl in einem Ganzzahl-Array (nicht rekursiv)
*
* Die lineare Suchliste muss eine geordnete Liste sein
*
* @paramdataset
* @paramdata
* @returnindex
*
*/
public int binarySearch(int[] dataset, int data) {
int beginIndex = 0;
int endIndex = dataset.length - 1;
int midIndex = -1;
if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex)
return -1;
while (beginIndex <= endIndex) {
midIndex = (beginIndex + endIndex) >>> 1; // Entspricht midIndex =
// (beginIndex +
// endIndex) / 2, aber die Effizienz wird höher sein
if (data < dataset[midIndex]) {
endIndex = midIndex - 1;
} else if (data > dataset[midIndex]) {
beginIndex = midIndex + 1;
} anders {
return midIndex;
}
}
return -1;
}
public static void main(String[] args) {
Sortieren sortTest = new Sort();
int[] array = sortTest.createArray();
System.out.println("==========Nach Blasensortierung (positive Reihenfolge)==========");
sortTest.bubbleSort(array, "asc");
System.out.println("==========Nach Blasensortierung (umgekehrte Reihenfolge)==========");
sortTest.bubbleSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========Nach dem Umkehren des Arrays==========");
sortTest.reverse(array);
array = sortTest.createArray();
System.out.println("==========Nach der Auswahlsortierung (positive Reihenfolge)==========");
sortTest.selectSort(array, "asc");
System.out.println("==========Nach der Auswahlsortierung (umgekehrte Reihenfolge)==========");
sortTest.selectSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========Nach dem Einfügen sortieren (positive Sequenz)==========");
sortTest.insertSort(array, "asc");
System.out.println("==========Nach dem Einfügen sortieren (umgekehrte Reihenfolge)==========");
sortTest.insertSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========Nach schneller Sortierung (positive Reihenfolge)==========");
sortTest.quickSort(array, "asc");
sortTest.printArray(array);
System.out.println("==========Nach schneller Sortierung (umgekehrte Reihenfolge)==========");
sortTest.quickSort(array, "desc");
sortTest.printArray(array);
System.out.println("==========Binäre Suche im Array==========");
System.out.println("Die gesuchte Nummer ist bei" + sortTest.binarySearch(array, 74)
+ „Sitze. (Index berechnet von 0)“);
}
}