Ein Artikel, in dem ein Programmieranfänger den Algorithmus von einem Ende aus implementiert. Dieses Mal wird die Einfügesortierung in C, Java, Ruby, Python geschrieben. Wenn es irgendwelche Verbesserungen im Code gibt, würde ich es begrüßen, wenn Sie mich unterrichten könnten.
・ Wirksam für Arrays mit einer kleinen Anzahl von Elementen -Effektiv für Arrays, die fast ausgerichtet sind oder viele überlappende Elemente aufweisen (Weil die Anzahl der Elementwechsel reduziert ist) ・ Der durchschnittliche Berechnungsbetrag [^ 1] beträgt $ O $ ($ n ^ 2 $) [^ 2] (Um jedes von n Elementen im Durchschnitt durch ein konstantes Vielfaches von n zu ersetzen)
[^ 1]: Berechnungsbetrag: Bewertungskriterien des Algorithmus. Erhalten basierend auf den Anweisungen der Bestandteile. [^ 2]: Auftragsnotation: Notation, die den Rechenaufwand angibt. Ignorieren Sie andere Begriffe und Koeffizienten als die Begriffe mit der höchsten Ordnung.
/*Größe ist die Größe des Arrays*/
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
-Java Referenztyp Variablen sind "String", "Array", "Klasse" ・ In Ruby und Python können die Elemente in einer Zeile ersetzt werden. ・ Ruby for-Anweisung wird als jede Methode interpretiert (Wenn jede Methode geändert wird, ändert sich auch das Verhalten der for-Anweisung.) ・ "&&" und "und" unterscheiden sich in Ruby usw. Referenz: Unterschied zwischen && und und