Un article qu'un débutant en programmation implémentera l'algorithme d'une extrémité. Cette fois, le tri par insertion est écrit en C, Java, Ruby, Python. S'il y a des améliorations dans le code, je vous serais reconnaissant si vous pouviez m'apprendre.
・ Efficace pour les tableaux avec un petit nombre d'éléments -Efficace pour les tableaux qui sont presque alignés ou qui ont de nombreux éléments qui se chevauchent (Parce que le nombre de remplacements d'éléments est réduit) ・ Le montant moyen du calcul [^ 1] est de $ O $ ($ n ^ 2 $) [^ 2] (Pour remplacer chacun des n éléments en moyenne par un multiple constant de n)
[^ 1]: Montant de calcul: Critères d'évaluation de l'algorithme Obtenu sur la base des instructions constitutives. [^ 2]: Notation d'ordre: Notation indiquant le montant du calcul. Ignorez les termes et coefficients autres que les termes de l'ordre le plus élevé.
/*size est la taille du tableau*/
void insertionSort(int data[10], int size) {
int i, j;
for(i = 1; i < size; i++) {
j = i;
while(j > 0 && data[j - 1] > data[j]) {
swap(&data[j - 1], &data[j]);
j--;
}
}
}
void swap(int *a, int *b) {
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
Java
public static void insertionSort(int[] data) {
int i, j;
for(i = 1; i < data.length; i++) {
j = i;
while(j > 0 && data[j - 1] > data[j]) {
swap(data, j);
j--;
}
}
}
public static void swap(int[] data, int j) {
int tmp;
tmp = data[j];
data[j] = data[j - 1];
data[j - 1] = tmp;
}
Ruby
def insertionSort(data)
(1...data.length).each do |i|
j = i
while j > 0 && data[j - 1] > data[j]
data[j - 1], data[j] = data[j], data[j - 1]
j -= 1
end
end
end
Python
def insertionSort(data):
for i in range(1, len(data)):
j = i
while j > 0 and data[j - 1] > data[j]:
data[j - 1], data[j] = data[j], data[j - 1]
j -=1
-Les variables de type de référence Java sont "String", "Array", "Class" ・ En Ruby et Python, les éléments peuvent être remplacés sur une seule ligne. ・ Ruby for statement est interprété comme chaque méthode (Lorsque la méthode each est modifiée, le comportement de l'instruction for change également) ・ "&&" et "et" sont différents dans Ruby etc. Référence: Différence entre && et et