Le tri par insertion binaire est une amélioration de l'algorithme de tri par insertion. Pendant l'algorithme de tri, les éléments sont continuellement insérés dans la séquence précédemment triée. Puisque la première moitié est une séquence triée, nous n'avons pas besoin de rechercher le point d'insertion dans l'ordre. Nous pouvons utiliser la méthode de demi-recherche pour accélérer la recherche du point d'insertion.
public static void halfSort(int[] array) { int low, high, mid; int tmp, j; for (int i = 1; i < array.length; i++) { tmp = array[i]; low = 0; high = i - 1; while (low <= high) { mid = low + (high - low) / 2; if (array[mid] > tmp) high = mid - 1; else low = mid + 1; } for (j = i - 1; j > high; j--) { array[j + 1] = array[j]; } array[high + 1] = tmp; } }
Schéma schématique de l'algorithme de demi-tri :
Ce qui précède est le résumé de cet article. C'est tout. J'espère qu'il sera utile à tout le monde d'apprendre l'algorithme de tri de moitié en Java.
Pour plus d'articles liés à l'implémentation Java de l'algorithme de demi-tri, veuillez faire attention au site Web PHP chinois !