Deux exemples d'algorithme de tri JavaScript Hill Sorting

Deux exemples d'algorithme de tri JavaScript Hill Sorting_Basic Knowledge

WBOY

Libérer： 2016-05-16 16:53:18

original

1651 Les gens l'ont consulté

Le tri par insertion est très efficace lorsqu'il fonctionne sur des données presque triées, c'est-à-dire qu'il peut atteindre l'efficacité du tri linéaire.
Mais le tri par insertion est généralement inefficace car le tri par insertion ne peut déplacer les données qu'un bit à la fois.
Le tri Hill doit son nom à son concepteur, Donald Shell, et l'algorithme a été publié en 1959. Certains manuels et manuels de référence plus anciens ont nommé l'algorithme Shell-Metzner, qui contient le nom de Marlene Metzner Norton, mais selon Metzner elle-même, "Je n'ai rien fait pour cet algorithme et mon nom ne devrait pas apparaître dans l'algorithme". >

Deux exemples d'algorithme de tri JavaScript Hill Sorting_Basic Knowledge
L'idée de base du tri Hill : prenez d'abord un entier d1 inférieur à n comme premier incrément, et divisez tous les enregistrements du fichier en groupes d1. Tous les enregistrements dont la distance est un multiple de d1 sont placés dans le même groupe. Effectuez d'abord un tri par insertion directe dans chaque groupe ; puis prenez le deuxième incrément d2 < d1 et répétez le regroupement et le tri ci-dessus jusqu'à ce que l'incrément dt = 1 (dt < dt-l< … < d2 < d1), qui c'est-à-dire jusqu'à ce que tous les enregistrements soient placés dans le même groupe pour le tri par insertion directe.

Cette méthode est essentiellement une méthode d'insertion groupée.

Exemple 1 :

Copier le code Le code est le suivant :

/**
* Le tri Hill, également connu sous le nom d'algorithme de tri incrémentiel descendant, est une version plus efficace et améliorée du tri par insertion. Le tri Hill est un algorithme de tri non stable.
*
* Le tri par insertion propose une méthode améliorée basée sur les deux propriétés suivantes du tri par insertion :
*
* Le tri par insertion est très efficace lorsqu'il fonctionne sur des données presque triées, c'est-à-dire l'efficacité. de tri linéaire peut être réalisé
* mais le tri par insertion est généralement inefficace, car le tri par insertion ne peut déplacer les données qu'un bit à la fois
*
*/

function shellSort( list ) {
var gap = Math.floor( list.length / 2 );

while( gap > 0 ) {

for( i = écart; i < list.length; i ) {
temp = list[i];

for( j = i; j >= écart && liste[ j - écart ] > = Math.floor( gap / 2 );
}

liste de retour;
};

// test
var arr = [2, 1, 3 , 12, 5, 66, 23, 87, 15, 32];

shellSort(arr);

Exemple 2 :

Copier le code

Le code est le suivant :