رمز خوارزمية فرز التل

التعقيد الزمني لفرز التل هو O(n*log2n) والتعقيد المكاني هو O(1)، وهي خوارزمية فرز غير مستقرة.

الفكرة: فرز التل هو أيضًا طريقة فرز بالإدراج، وهي في الواقع طريقة تجميع وإدراج. أولاً، حدد عددًا صحيحًا d1 أقل من n كزيادة أولى، وقسم جميع السجلات في الجدول إلى مجموعات d1، ثم ضع جميع السجلات التي تكون مسافاتها من مضاعفات d1 في نفس المجموعة، ثم قم بإجراء فرز الإدراج المباشر داخل كل مجموعة؛ ، خذ الزيادة الثانية d2 (<d1)، كرر التجميع والفرز أعلاه، حتى الزيادة المأخوذة dt=1 (dt<dt-1<...<d2<d1)، أي يتم وضع جميع السجلات في نفس المجموعة حتى يتم تنفيذ فرز الإدراج المباشر.

انسخ رمز الكود كما يلي:

باطلة ShellSort (عدد صحيح * البيانات، طول كثافة العمليات)
{
إذا (البيانات == NULL || الطول <= 0)
يعود؛

int d = length/2;
بينما (د)
{
for(int i = 0; i < d; ++i) // قسّم إلى مجموعات وفقًا لحجم الخطوة، وأدخل فرزًا لكل مجموعة
{
// فرز الإدراج
من أجل (int j = i+d; j <length ; j +=d )
{
إذا (بيانات [ي] < بيانات [ي -د])
{
int temp = data[j];
كثافة العمليات ك = دينار;
for(; k >=0&& temp < data[k]; k -=d)
{
data[k+d] =data[k];
}
data[k+d] =temp;
}
}
}
د = د/2;
}
}