Explication détaillée des algorithmes de tri Java couramment utilisés

1. Tri par sélection (SelectSort)

Principe de base : Pour un ensemble d'enregistrements donné, après le premier tour de comparaison, le plus petit enregistrement est obtenu, puis l'enregistrement est comparé à la position du premier enregistrement ; puis effectuez une deuxième comparaison sur d'autres enregistrements en excluant le premier enregistrement pour obtenir le plus petit enregistrement et échangez les positions avec le deuxième enregistrement ; répétez ce processus jusqu'à ce qu'il n'y ait qu'un seul enregistrement à comparer.

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. Tri par insertion (InsertSort)

Principe de base : Pour un ensemble de données donné, supposez initialement le premier Chaque enregistrement forme une séquence ordonnée et les enregistrements restants forment une séquence non ordonnée. Ensuite, à partir du deuxième enregistrement, l'enregistrement en cours de traitement est inséré dans la séquence ordonnée qui le précède dans l'ordre en fonction de la taille de l'enregistrement, jusqu'à ce que le dernier enregistrement soit inséré dans la séquence ordonnée.

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. Bubble Sort (BubbleSort)

Principe de base : Pour un n enregistrements donné, commencer par le premier L'enregistrement démarre pour comparer deux enregistrements adjacents en séquence. Lorsque l'enregistrement précédent est plus grand que l'enregistrement ultérieur, les positions sont permutées. Après un tour de comparaison et de transposition, l'enregistrement le plus grand parmi les n enregistrements sera situé à la nième position. les premiers (n-1) enregistrements subissent un deuxième cycle de comparaison ; le processus est répété jusqu'à ce qu'il ne reste qu'un seul enregistrement à comparer.

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)

Principe de base : utiliser la récursivité et la technologie diviser pour régner pour diviser la séquence de données. en de plus en plus Plus la demi-sous-liste est petite, la demi-sous-liste est triée, et enfin la demi-sous-liste triée est fusionnée en une séquence ordonnée de plus en plus grande en utilisant une méthode récursive. Pour un ensemble d'enregistrements donné (en supposant un total de n enregistrements), fusionnez d'abord toutes les deux sous-séquences adjacentes de longueur 1 pour obtenir n/2 (arrondies à l'unité supérieure) sous-séquences ordonnées de longueur 2 ou 1. sous-séquences, puis fusionnez-les deux par deux. , et répétez ce processus jusqu'à ce qu'une séquence ordonnée soit obtenue.

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. Tri rapide (QuickSort)

Principe de base : Pour un ensemble d'enregistrements donné, après une passe de tri, divisez la séquence originale en deux parties, où tous les enregistrements de la première partie sont plus petits que tous les enregistrements de la dernière partie, puis triez rapidement les enregistrements des deux parties tour à tour et répétez le processus jusqu'à ce que tous les enregistrements de la la séquence est en ordre jusqu'à.

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)

Principe de base : divisez d'abord les éléments du tableau à trier en plusieurs sous-séquences, Le le nombre d'éléments dans chaque sous-séquence est relativement réduit, puis un tri par insertion directe est effectué sur chaque sous-séquence une fois que la séquence entière à trier est « fondamentalement ordonnée », tous les éléments sont ensuite directement insérés et triés.

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. Tri minimum du tas (MinHeapSort)

Principe de base : Pour un n enregistrements donnés, placez-les initialement L'enregistrement est considéré comme un arbre binaire stocké séquentiellement, puis ajusté dans un petit tas supérieur, puis après avoir échangé le dernier élément du tas avec l'élément supérieur du tas, le dernier élément du tas est alors l'enregistrement minimum (n - ; 1) les éléments sont réajustés dans un petit tas supérieur, puis l'élément supérieur du tas est échangé avec le dernier élément du tas actuel pour obtenir le plus petit enregistrement suivant. Répétez ce processus jusqu'à ce qu'il ne reste qu'un seul élément dans le tas. tas ajusté L'élément est l'enregistrement maximum, et une séquence ordonnée peut être obtenue à ce moment.

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] + " ");
 }
 }
}

Ce qui précède est l'intégralité du contenu de cet article. J'espère que le contenu de cet article pourra apporter une certaine aide aux études ou au travail de chacun, et. J'espère également votre soutien. Site Web PHP chinois !

Pour des explications plus détaillées sur les algorithmes de tri Java couramment utilisés et les articles connexes, veuillez faire attention au site Web PHP chinois !