Detaillierte Erläuterung häufig verwendeter Java-Sortieralgorithmen

1. Auswahlsortierung (SelectSort)

Grundprinzip: Für einen bestimmten Datensatzsatz wird nach der ersten Vergleichsrunde der kleinste Datensatz ermittelt und dann der Datensatz mit der Position des Datensatzes verglichen Führen Sie dann einen zweiten Vergleich mit anderen Datensätzen durch, mit Ausnahme des ersten Datensatzes, und tauschen Sie die Positionen mit dem zweiten Datensatz aus.

public class SelectSort {
 public static void selectSort(int[] array) {
 int i;
 int j;
 int temp;
 int flag;
 for (i = 0; i < array.length; i++) {
 temp = array[i];
 flag = i;
 for (j = i + 1; j < array.length; j++) {
 if (array[j] < temp) {
  temp = array[j];
  flag = j;
 }
 }
 if (flag != i) {
 array[flag] = array[i];
 array[i] = temp;
 }
 }
 }
 public static void main(String[] args) {
 int[] a = { 5, 1, 9, 6, 7, 2, 8, 4, 3 };
 selectSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}

2. Sortierung einfügen (InsertSort)

Grundprinzip: Für einen gegebenen Datensatz wird zunächst der erste Datensatz angenommen bildet eine geordnete Reihenfolge, und die übrigen Datensätze bilden eine ungeordnete Reihenfolge. Dann wird ausgehend vom zweiten Datensatz der aktuell verarbeitete Datensatz entsprechend der Größe des Datensatzes davor in die geordnete Reihenfolge eingefügt, bis der letzte Datensatz in die geordnete Reihenfolge eingefügt wird.

public class InsertSort {
 public static void insertSort(int[] a) {
 if (a != null) {
 for (int i = 1; i < a.length; i++) {
 int temp = a[i];
 int j = i;
 if (a[j - 1] > temp) {
  while (j >= 1 && a[j - 1] > temp) {
  a[j] = a[j - 1];
  j--;
  }
 }
 a[j] = temp;
 }
 }
 }
 public static void main(String[] args) {
 int[] a = { 5, 1, 7, 2, 8, 4, 3, 9, 6 };
 // int[] a =null;
 insertSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}

3. Blasensortierung (BubbleSort)

Grundprinzip: Beginnen Sie für gegebene n Datensätze mit dem ersten Der Datensatz beginnt Um zwei benachbarte Datensätze nacheinander zu vergleichen, werden die Positionen vertauscht. Nach einer Vergleichs- und Transpositionsrunde befindet sich der größte Datensatz an der n-ten Position Die ersten (n-1) Datensätze werden einer zweiten Vergleichsrunde unterzogen. Der Vorgang wird wiederholt, bis nur noch ein Datensatz zum Vergleich übrig bleibt.

public class BubbleSort {
 public static void bubbleSort(int array[]) {
 int temp = 0;
 int n = array.length;
 for (int i = n - 1; i >= 0; i--) {
 for (int j = 0; j < i; j++) {
 if (array[j] > array[j + 1]) {
  temp = array[j];
  array[j] = array[j + 1];
  array[j + 1] = temp;
 }
 }
 }
 }
 public static void main(String[] args) {
 int a[] = { 45, 1, 21, 17, 69, 99, 32 };
 bubbleSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}

4. MergeSort (MergeSort)

Grundprinzip: Verwenden Sie Rekursion und Divide-and-Conquer-Technologie, um die Datensequenz zu teilen in immer mehr Je kleiner die Halb-Unterliste, desto sortierter wird die Halb-Unterliste und schließlich wird die sortierte Halb-Unterliste mithilfe einer rekursiven Methode zu einer immer größeren geordneten Sequenz zusammengeführt. Führen Sie für einen bestimmten Satz von Datensätzen (unter der Annahme einer Gesamtzahl von n Datensätzen) zunächst alle zwei benachbarten Teilsequenzen der Länge 1 zusammen, um n/2 (aufgerundete) geordnete Teilsequenzen der Länge 2 oder 1 zu erhalten. Teilsequenzen, und führen Sie sie dann jeweils zwei zusammen , und wiederholen Sie diesen Vorgang, bis eine geordnete Sequenz erhalten wird.

public class MergeSort {
 public static void merge(int array[], int p, int q, int r) {
 int i, j, k, n1, n2;
 n1 = q - p + 1;
 n2 = r - q;
 int[] L = new int[n1];
 int[] R = new int[n2];
 for (i = 0, k = p; i < n1; i++, k++)
 L[i] = array[k];
 for (i = 0, k = q + 1; i < n2; i++, k++)
 R[i] = array[k];
 for (k = p, i = 0, j = 0; i < n1 && j < n2; k++) {
 if (L[i] > R[j]) {
 array[k] = L[i];
 i++;
 } else {
 array[k] = R[j];
 j++;
 }
 }
 if (i < n1) {
 for (j = i; j < n1; j++, k++)
 array[k] = L[j];
 }
 if (j < n2) {
 for (i = j; i < n2; i++, k++) {
 array[k] = R[i];
 }
 }
 }
 public static void mergeSort(int array[], int p, int r) {
 if (p < r) {
 int q = (p + r) / 2;
 mergeSort(array, p, q);
 mergeSort(array, q + 1, r);
 merge(array, p, q, r);
 }
 }
 public static void main(String[] args) {
 int a[] = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
 mergeSort(a, 0, a.length - 1);
 for (int j = 0; j < a.length; j++) {
 System.out.print(a[j] + " ");
 }
 }
}

5. Schnellsortierung (QuickSort)

Grundprinzip: Für einen bestimmten Satz von Datensätzen gilt nach einem Sortierdurchgang: Teilen Sie die ursprüngliche Sequenz in zwei Teile, wobei alle Datensätze im ersten Teil kleiner sind als alle Datensätze im zweiten Teil. Sortieren Sie dann die Datensätze in den beiden Teilen schnell nacheinander und wiederholen Sie den Vorgang, bis alle Datensätze im zweiten Teil vorhanden sind Reihenfolge sind in der Reihenfolge bis.

public class QuickSort {
 public static void sort(int array[], int low, int high) {
 int i, j;
 int index;
 if (low >= high)
 return;
 i = low;
 j = high;
 index = array[i];
 while (i < j) {
 while (i < j && index <= array[j])
 j--;
 if (i < j)
 array[i++] = array[j];
 while (i < j && index > array[i])
 i++;
 if (i < j)
 array[j--] = array[i];
 }
 array[i] = index;
 sort(array, low, i - 1);
 sort(array, i + 1, high);
 }
 public static void quickSort(int array[]) {
 sort(array, 0, array.length - 1);
 }
 public static void main(String[] args) {
 int a[] = { 5, 8, 4, 6, 7, 1, 3, 9, 2 };
 quickSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}

6. Shell Sort (ShellSort)

Grundprinzip: Teilen Sie zunächst die zu sortierenden Array-Elemente in mehrere Teilsequenzen auf Die Anzahl der Elemente in jeder Teilsequenz wird relativ reduziert, und dann wird für jede Teilsequenz eine direkte Einfügungssortierung durchgeführt. Nachdem die gesamte zu sortierende Sequenz „grundlegend geordnet“ ist, werden alle Elemente direkt eingefügt und sortiert.

public class ShellSort {
 public static void shellSort(int[] a) {
 int len = a.length;
 int i, j;
 int h;
 int temp;
 for (h = len / 2; h > 0; h = h / 2) {
 for (i = h; i < len; i++) {
 temp = a[i];
 for (j = i - h; j >= 0; j -= h) {
  if (temp < a[j]) {
  a[j + h] = a[j];
  } else
  break;
 }
 a[j + h] = temp;
 }
 }
 }
 public static void main(String[] args) {
 int a[] = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
 shellSort(a);
 for (int j = 0; j < a.length; j++) {
 System.out.print(a[j] + " ");
 }
 }
}

7. Minimale Heap-Sortierung (MinHeapSort)

Grundprinzip: Für gegebene n Datensätze legen Sie zunächst diese fest Der Datensatz ist Wird als binärer Baum betrachtet, der sequentiell gespeichert und dann in einen kleinen oberen Heap angepasst wird. Nach dem Austausch des letzten Elements des Heaps mit dem oberen Element des Heaps ist das letzte Element des Heaps dann der minimale Datensatz (n - 1) Elemente werden in einem kleinen oberen Heap neu angepasst, und dann wird das oberste Element des Heaps mit dem letzten Element des aktuellen Heaps ausgetauscht, um den nächstkleineren Datensatz zu erhalten. Wiederholen Sie diesen Vorgang, bis nur noch ein Element im Heap vorhanden ist Angepasster Heap Das Element ist der maximale Datensatz, und zu diesem Zeitpunkt kann eine geordnete Sequenz abgerufen werden.

public class MinHeapSort {
 public static void adjustMinHeap(int[] a, int pos, int len) {
 int temp;
 int child;
 for (temp = a[pos]; 2 * pos + 1 <= len; pos = child) {
 child = 2 * pos + 1;
 if (child < len && a[child] > a[child + 1])
 child++;
 if (a[child] < temp)
 a[pos] = a[child];
 else
 break;
 }
 a[pos] = temp;
 }
 public static void myMinHeapSort(int[] array) {
 int i;
 int len = array.length;
 for (i = len / 2 - 1; i >= 0; i--) {
 adjustMinHeap(array, i, len - 1);
 }
 for (i = len - 1; i >= 0; i--) {
 int tmp = array[0];
 array[0] = array[i];
 array[i] = tmp;
 adjustMinHeap(array, 0, i - 1);
 }
 }
 public static void main(String[] args) {
 int[] a = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
 myMinHeapSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}

Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, dass der Inhalt dieses Artikels jedem beim Lernen oder bei der Arbeit helfen kann Ich hoffe auch auf Ihre Unterstützung.

Ausführlichere Erklärungen häufig verwendeter Java-Sortieralgorithmen und verwandte Artikel finden Sie auf der chinesischen PHP-Website!