Explication détaillée d'exemples de tri Java Hill

Cet article présente principalement la structure des données Java et l'algorithme du tri Hill, et analyse le concept, le principe, la méthode de mise en œuvre et les précautions associées du tri Hill sous forme d'exemples. Les amis dans le besoin peuvent s'y référer

Les exemples de cet article décrivent le tri Hill des structures de données et des algorithmes Java. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Ce que je veux présenter ici, c'est le tri Hill (méthode de tri incrémentiel par réduction).

Tri par colline : fonctionne en comparant des éléments distants d'une certaine distance ; la distance (incrément) utilisée dans chaque comparaison diminue à mesure que l'algorithme progresse jusqu'à ce que seuls les éléments adjacents soient comparés jusqu'au dernier tri. passe d'éléments. Il s'agit d'un type de tri par insertion et d'une amélioration de l'algorithme de tri par insertion directe.

Idée algorithmique : Divisez d'abord la séquence à trier en plusieurs sous-séquences selon un certain incrément d, effectuez un tri par insertion directe sur tous les éléments de chaque sous-séquence, puis utilisez un regroupez-le par incrément, puis triez-le dans chaque groupe. Lorsque l'incrément est réduit à 1, le nombre entier à trier est divisé en un groupe et le tri est terminé. Remarque : La valeur de l'incrément - généralement la moitié de la séquence est prise comme incrément pour la première fois, puis divisée par deux à chaque fois jusqu'à ce que l'incrément soit 1. Le code d'implémentation de l'algorithme est le suivant :

package exp_sort;
public class ShellSort {
  public static void shell(int array[]) {
    int j;
    int average;
    //设置增量的值
    for (average = array.length / 2; average > 0; average /= 2) { //步长
      for (int i = average; i < array.length; i++) { //子序列进行直接插入排序
        int temp = array[i];
        for (j = i; j >= average && temp < array[j - average]; j -= average) {
          array[j] = array[j - average];
        }
        array[j] = temp;
      }
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    shell(array);
  }
}

Analyse de l'algorithme :

Cet algorithme insère et trie les éléments selon différents tailles de pas , lorsque les éléments sont très désordonnés au début, la taille du pas est la plus grande, donc le nombre d'éléments de tri par insertion est très petit et la vitesse est très rapide lorsque les éléments sont essentiellement ordonnés, la taille du pas est ; très petit et le tri par insertion est très efficace pour les séquences ordonnées élevées. Par conséquent, la complexité temporelle du tri Hill sera meilleure que O(n^2), qui est O(n^1,5), et l'efficacité du tri est bien supérieure à tri par insertion . En raison de plusieurs tris par insertion, nous savons qu'un tri par insertion est stable et ne modifiera pas l'ordre relatif des mêmes éléments. Cependant, dans différents processus de tri par insertion, les mêmes éléments peuvent se déplacer dans leurs tris par insertion respectifs, et finalement leur stabilité le sera. le changement est perturbé, donc le tri des coquilles est instable . Le tri Hill n'est pas aussi rapide que l'algorithme de tri rapide O(N*(logN)), il est donc plus adapté au tri de données de taille moyenne, mais n'est pas le choix optimal pour trier des données à très grande échelle. . Mais c'est beaucoup plus rapide que l'algorithme de complexité O(N^2). Et le tri Hill est très facile à mettre en œuvre et le code de l'algorithme est court et simple. De plus, la différence entre l'efficacité des performances de l'algorithme de Hill dans le pire des cas et le cas moyen n'est pas grande, tandis que l'efficacité du tri rapide dans le pire des cas sera très faible. 【Recommandations associées】

1.

Recommandation spéciale : Téléchargez la version V0.1 de "php Programmer Toolbox" 2.

Tutoriel vidéo gratuit Java

3

Manuel en ligne YMP

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!