L'efficacité du tri est généralement comparée sous trois aspects : le nombre de comparaisons de données, le nombre de déplacements de données et la quantité d'espace mémoire occupée.
Faisons une comparaison générale du tri à bulles, du tri par sélection, du tri par insertion et du tri rapide. L'algorithme de tri à bulles n'est généralement pas utilisé car son nombre de comparaisons et de déplacements est le plus grand parmi plusieurs algorithmes de tri. Son seul avantage est que l'algorithme est simple et facile à comprendre, il peut donc être utilisé lorsque la quantité de données est faible. sera une valeur d'application. Le tri par sélection a le même nombre de comparaisons que le tri à bulles, qui est n au carré, mais il réduit le nombre d'échanges au minimum, il peut donc être appliqué lorsque la quantité de données est petite et que l'échange de données prend plus de temps que la comparaison. données. Sélectionnez trier.
Dans la plupart des cas, lorsque la quantité de données est relativement petite ou fondamentalement ordonnée, l’algorithme de tri par insertion constitue le meilleur choix. Pour trier de plus grandes quantités de données, le tri rapide est généralement la meilleure méthode.
L'algorithme de tri ci-dessus occupe très peu d'espace mémoire et ne nécessite qu'une variable supplémentaire pour stocker temporairement les éléments de données lors de l'échange. Il n’y a donc aucune comparaison possible quant à la taille de l’espace mémoire occupé.
Le nombre de comparaisons du tri par insertion est toujours de n au carré, mais en général, il est deux fois plus rapide que le tri à bulles et un peu plus rapide que le tri par sélection. Il est souvent utilisé dans les étapes finales d’algorithmes de tri complexes, tels que le tri rapide.
Algorithme : Après le traitement i-1, L[1..i-1] a été trié. La ième passe insère uniquement L[i] dans la position appropriée de L[1..i-1],
De sorte que L[1..i] est à nouveau une séquence ordonnée. Pour atteindre cet objectif, nous pouvons utiliser la comparaison séquentielle.
Comparez d'abord L[i] et L[i-1]. Si L[i-1]<=L[i], alors L[1..i] a été trié et la i-ème passe de traitement est terminée ;
Sinon, échangez les positions de L[i] et L[i-1], et continuez à comparer L[i-1] et L[i-2] jusqu'à ce qu'une certaine position j (1≤j≤i-1) soit trouvé.
Jusqu'à L[j] ≤L[j+1]
Avantages : moins d'éléments sont déplacés et seul un espace auxiliaire est nécessaire
Complexité temporelle n*n
C'est une bonne méthode de tri lorsque le nombre n d'enregistrements à trier est petit. Mais quand n est très grand, ce n’est pas approprié
Par exemple : int[] valeurs = { 5, 2, 4, 1, 3 } ;
Processus de tri :
1ère fois : 2,5,4,1,3
2ème fois : 2,4,5,1,3
3ème fois : 1,2,4,5,3
4ème fois : 1,2,3,4,5
codejava :
Copiez le code comme suit :
classe publique InsertSort {
public static void main (String[] arguments) {
int[] valeurs = { 5, 2, 4, 1, 3 } ;
trier(valeurs);
pour (int i = 0; i < valeurs.longueur; ++i) {
System.out.println(values[i]);
}
}
sort public static void (valeurs int[]) {
température int;
entier j = 0 ;
pour (int i = 1; i < valeurs.longueur; i++) {
if(values[i]<values[i-1])//Le jugement ici est très important. Cela reflète la raison pour laquelle le tri par insertion est plus rapide que le tri à bulles et le tri par sélection.
{
temp = valeurs[i];
// Déplacer les données vers l'arrière
pour (j=i-1; j>=0 && temp<values[j]; j--)
{
valeurs[j+1] =valeurs[j];
}
//Insérer des données à la position j+1
valeurs[j+1] =temp;
System.out.print("th" + (i + 1) + "th:");
pour (int k = 0; k < valeurs.longueur; k++) {
System.out.print(values[k]+",");
}
System.out.println("");
}
}
}
}
Deuxième exemple
Copiez le code comme suit :
paquet cn.cqu.coce.xutao ;
classe publique zhijiecharu {
public static void main(String args[]){
int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
int je,j,k;
pour(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
System.out.println();
pour(i=1;i<a.length;i++){
pour(j=i-1;j>=0;j--)
si(a[i]>a[j])
casser;
si(j!=i-1){
température int;
temp=a[je];
pour(k=i-1;k>j;k--)
une[k+1]=une[k];
a[k+1]=temp;
}
}
pour(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
System.out.println();
}
}