Introduction
Le tri des collines (réduction de la méthode incrémentielle) appartient au tri des classes d'insertion. Il est proposé par Shell. Le tri des collines a apporté des améliorations simples au tri direct de l'insertion: il augmente l'intervalle entre les éléments du tri de l'insertion et les inserts dans ces éléments d'intervalle, faisant ainsi passer les éléments de données à travers une grande portée. Une fois que ces éléments de données sont triés une fois, l'algorithme de tri de la colline réduit l'intervalle d'éléments de données, puis les trie, et se déroule à son tour. L'intervalle entre les éléments de données lorsque ce tri est appelé incréments, et la lettre H est utilisée pour représenter cet incrément.
La séquence H couramment utilisée est proposée par Knuth. Cette séquence commence à partir de 1 et est générée par la formule suivante:
H = 3 * H +1
Le programme doit à son tour pour calculer la séquence H à l'envers et doit être utilisé
h = (h-1) / 3
Implémentation de code
Code d'implémentation 1:
public static void shellort (int [] arr) {int temp; pour (int delta = arr.length / 2; delta> = 1; delta / = 2) {// trier chaque incrément une fois pour (int i = delta; i <arr.length; i ++) {for (int j = i; j> = delta && arr [j] <arr [j-delta]; j- = delta) {// noter que l'augmentation et la différence sont delta tempor = arr [j-delta]; arr [j-delta] = arr [j]; arr [j] = temp; }} // boucle i} // boucle delta}Code d'implémentation 2:
public static void shellSort2 (int [] arr) {int delta = 1; while (delta <arr.length / 3) {// générer delta delta = delta * 3 + 1; // <o (n ^ (3/2)) par Knuth, 1973>: 1, 4, 13, 40, 121, ...} int temp; for (; delta> = 1; delta / = 3) {for (int i = delta; i <arr.length; i ++) {for (int j = i; j> = delta && arr [j] <arr [j-delta]; j- = delta) {temp = arr [j-delta]; arr [j-delta] = arr [j]; arr [j] = temp; }} // boucle i} // boucle delta} Lorsque le programme ci-dessus le compare à la méthode d'insertion directe, vous constaterez que la différence entre celle-ci et le tri d'insertion directe est que le H dans le type d'insertion directe sera remplacé par 1.
Le tri des coquilles est instable, son surcharge d'espace est également O (1) et la surcharge de temps est estimée entre O (N3 / 2) et O (N7 / 6).