Interprétation détaillée de l'algorithme de tri Hill et de l'implémentation du code Java associé

Le tri de Shell est un algorithme de tri très "magique". On l'appelle « magique » car personne ne peut expliquer clairement quelles sont ses performances. Tri en colline dû à DL. Shell doit son nom à sa proposition en 1959. Depuis que C. A. R. Hoare a proposé le tri rapide en 1962, le tri rapide est généralement utilisé car il est plus simple. Cependant, de nombreux mathématiciens travaillent encore sans relâche pour trouver la complexité optimale du tri de Hill. En tant que programmeurs ordinaires, nous pouvons apprendre des idées de Hill.
D'ailleurs, avant l'émergence du tri Hill, il existait une opinion répandue dans l'industrie informatique selon laquelle « les algorithmes de tri ne peuvent pas percer O(n2) ». L’émergence du tri Hill a brisé cette malédiction et bientôt, des algorithmes tels que le tri rapide sont apparus les uns après les autres. En ce sens, le tri Hill nous fait entrer dans une nouvelle ère.

Aperçu/idée de l'algorithme
La proposition du tri Hill est principalement basée sur les deux points suivants :
1 L'algorithme de tri par insertion peut approximativement atteindre une complexité O(n) lorsque le tableau est fondamentalement ordonné. . degré, extrêmement efficace.
2. Cependant, le tri par insertion ne peut déplacer les données qu'un bit à la fois, et les performances se détérioreront rapidement lorsque le tableau est grand et fondamentalement désordonné.

Sur cette base, nous pouvons utiliser une méthode de tri par insertion groupée. La méthode spécifique est : (prenons un tableau de 16 éléments comme exemple)
1 Sélectionnez un delta d'incrément supérieur à 1. . Sélectionnez le sous-tableau du tableau en fonction de cet incrément pour un tri par insertion directe. Par exemple, si l'incrément sélectionné est 5, les éléments d'index 0, 5, 10 et 15 seront triés.
2. Conservez le delta incrémentiel et déplacez le premier élément dans l'ordre pour un tri par insertion directe jusqu'à ce qu'un tour soit terminé. Pour l'exemple ci-dessus, les tableaux [1, 6, 11], [2, 7, 12], [3, 8, 13], [4, 9, 14] sont triés dans l'ordre.
3. Réduisez l'incrément et répétez le processus ci-dessus jusqu'à ce que l'incrément soit réduit à 1. Évidemment, la dernière fois est un tri par insertion directe.
4. Tri terminé.
Comme le montre ce qui précède, l'incrément diminue constamment, c'est pourquoi le tri Hill est également appelé « tri par incrément décroissant ».

Implémentation du code

package sort; 
  
public class ShellSortTest { 
  public static int count = 0; 
  
  public static void main(String[] args) { 
  
    int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; 
    print(data); 
    shellSort(data); 
    print(data); 
  
  } 
  
  public static void shellSort(int[] data) { 
    // 计算出最大的h值 
    int h = 1; 
    while (h <= data.length / 3) { 
      h = h * 3 + 1; 
    } 
    while (h > 0) { 
      for (int i = h; i < data.length; i += h) { 
        if (data[i] < data[i - h]) { 
          int tmp = data[i]; 
          int j = i - h; 
          while (j >= 0 && data[j] > tmp) { 
            data[j + h] = data[j]; 
            j -= h; 
          } 
          data[j + h] = tmp; 
          print(data); 
        } 
      } 
      // 计算出下一个h值 
      h = (h - 1) / 3; 
    } 
  } 
  
  public static void print(int[] data) { 
    for (int i = 0; i < data.length; i++) { 
      System.out.print(data[i] + "\t"); 
    } 
    System.out.println(); 
  } 
  
}

Résultats d'exécution :

5  3  6  2  1  9  4  8  7   
1  3  6  2  5  9  4  8  7   
1  2  3  6  5  9  4  8  7   
1  2  3  5  6  9  4  8  7   
1  2  3  4  5  6  9  8  7   
1  2  3  4  5  6  8  9  7   
1  2  3  4  5  6  7  8  9   
1  2  3  4  5  6  7  8  9

Performance/complexité de l'algorithme
La séquence incrémentielle de tri Hill peut être choisie selon les besoins. la condition est que le dernier doit être 1 (car il doit être ordonné par 1). Cependant, différentes sélections de séquences auront un impact important sur les performances de l’algorithme. Le code ci-dessus montre deux incréments.
Rappelez-vous : il est préférable de ne pas avoir de facteur commun autre que 1 pour deux éléments dans la séquence incrémentielle ! (Évidemment, cela n’a pas beaucoup de sens de trier une séquence ordonnée par 4 puis par 2).
Voici quelques séquences delta courantes.
Le premier incrément est l'incrément initialement proposé par Donald Shell, qui est réduit de moitié jusqu'à 1. Selon les recherches, en utilisant l'incrément de Hill, la complexité temporelle est toujours O(n2).
Le deuxième incrément Hibbard : {1, 3, ..., 2^k-1}. La complexité temporelle de cette séquence incrémentielle est d'environ O(n^1,5).
Le troisième incrément Incrément Sedgewick : (1, 5, 19, 41, 109,...), la séquence générée est soit 9*4^i - 9*2^i 1 ou 4^i - 3*2 ^je 1.

Stabilité de l'algorithme
Nous savons tous que le tri par insertion est un algorithme stable. Cependant, le tri Shell est un processus d’insertion multiple. Dans une insertion, nous pouvons garantir que l'ordre des mêmes éléments n'est pas modifié, mais dans plusieurs insertions, les mêmes éléments peuvent être déplacés dans différents tours d'insertion, et finalement la stabilité est détruite. Par conséquent, l'algorithme de tri Shell n'est pas stable. .

Scénarios applicables à l'algorithme
Bien que le tri Shell soit rapide, il s'agit après tout d'un tri par insertion, et son ordre de grandeur n'est pas aussi rapide que le tri rapide de l'étoile montante O(n㏒n). Le tri Shell n’est pas un bon algorithme face à de grandes quantités de données. Cependant, cela convient parfaitement aux données de petite et moyenne taille.

Pour des explications plus détaillées sur l'algorithme de tri Hill et les articles liés à l'implémentation du code Java, veuillez faire attention au site Web PHP chinois !