Die zeitliche Komplexität der Hill-Sortierung beträgt O(n*log2n) und die räumliche Komplexität beträgt O(1). Es handelt sich um einen instabilen Sortieralgorithmus.
Idee: Die Hill-Sortierung ist auch eine Einfügungssortiermethode, bei der es sich tatsächlich um eine Gruppierungseinfügungsmethode handelt. Bestimmen Sie zunächst eine ganze Zahl d1, die kleiner als n ist, als erstes Inkrement, teilen Sie alle Datensätze in der Tabelle in d1-Gruppen auf, fügen Sie alle Datensätze, deren Abstand ein Vielfaches von d1 ist, in dieselbe Gruppe ein und führen Sie dann eine direkte Einfügungssortierung innerhalb jeder Gruppe durch Nehmen Sie das zweite Inkrement d2 (<d1) und wiederholen Sie die obige Gruppierung und Sortierung, bis das genommene Inkrement dt = 1 (dt <dt-1 <... <d2 <d1) ist, d. h. alle Datensätze werden in platziert derselben Gruppe, bis die direkte Einfügungssortierung durchgeführt wird.
Kopieren Sie den Codecode wie folgt:
void ShellSort(int* data,int length)
{
if( Daten == NULL || Länge <= 0 )
zurückkehren;
int d = Länge/2; //Schrittgröße
während(d)
{
for(int i = 0; i < d; ++i) // Entsprechend der Schrittgröße in Gruppen aufteilen und jede Gruppe sortieren
{
//Einfügesortierung
for(int j = i+d; j <length ; j +=d )
{
if(Daten[j] < Daten[j -d])
{
int temp = data[j]; //sentinel
int k = jd;
for(; k >=0&& temp < data[k]; k -=d)
{
Daten[k+d] =Daten[k];
}
Daten[k+d] =temp;
}
}
}
d = d/2;
}
}