Ich kann keine Informationen darüber finden, welcher Sortieralgorithmus C qsort function verwendet.
Ist es Quicksort? Es wird nicht im Menschen erwähnt.
Die Implementierung von qsort wurde nicht angegeben: Eine Implementierung kann einen beliebigen Sortieralgorithmus verwenden. Interessanterweise muss die Sortierung nicht stabil sein und es gibt keine Komplexitätsanforderung.
Die gesamte Spezifikation von qsort (C11 §7.22.5.2) lautet wie folgt:
Die Funktion
qsortÜbersicht
%Vor%Beschreibung
Die Funktion
qsortsortiert ein Array vonnmemb-Objekten, deren erstes Element ist gezeigt vonbase. Die Größe jedes Objekts wird durchsizeangegeben.Der Inhalt des Arrays wird in aufsteigender Reihenfolge nach einer Vergleichsfunktion sortiert, auf die compar zeigt, die mit zwei Argumenten aufgerufen wird, die auf die zu vergleichenden Objekte zeigen. Die Funktion soll eine Ganzzahl kleiner als, gleich oder größer als Null zurückgeben, wenn das erste Argument als kleiner, gleich oder größer als das zweite betrachtet wird.
Wenn zwei Elemente als gleichwertig verglichen werden, ist ihre Reihenfolge im resultierenden sortierten Array nicht spezifiziert.
Gibt
zurückDie Funktion
qsortgibt keinen Wert zurück.
In Ergänzung zu James McNellis Zitat des Standards ist es bemerkenswert, dass GNU's libc Dokumentation sagt das
Die Funktion
qsortleitet ihren Namen von der Tatsache ab, dass sie ursprünglich mit dem "Quick Sort" -Algorithmus implementiert wurde.
und dass es sich entschieden hat, ein alternativer Algorithmus , anscheinend ein Merge sort.