ความซับซ้อนของเวลาของการเรียงลำดับ Hill คือ O(n*log2n) และความซับซ้อนของพื้นที่คือ O(1) มันเป็นอัลกอริธึมการเรียงลำดับที่ไม่เสถียร
แนวคิด: การเรียงลำดับแบบ Hill ยังเป็นวิธีการเรียงลำดับแบบแทรก ซึ่งจริงๆ แล้วเป็นวิธีการแทรกแบบจัดกลุ่ม ขั้นแรก ให้กำหนดจำนวนเต็ม d1 ที่น้อยกว่า n เป็นส่วนเพิ่มครั้งแรก แบ่งระเบียนทั้งหมดในตารางออกเป็นกลุ่ม d1 ใส่ระเบียนทั้งหมดที่มีระยะห่างเป็นทวีคูณของ d1 ลงในกลุ่มเดียวกัน และดำเนินการเรียงลำดับการแทรกโดยตรงภายในแต่ละกลุ่ม ให้เพิ่มค่าขั้นที่สอง d2 (<d1) ทำซ้ำการจัดกลุ่มและการเรียงลำดับข้างต้น จนกระทั่งค่าเพิ่มที่ได้รับ dt=1 (dt<dt-1<...<d2<d1) นั่นคือ บันทึกทั้งหมดจะถูกวางไว้ใน กลุ่มเดียวกันจนกว่าจะดำเนินการเรียงลำดับการแทรกโดยตรง
คัดลอกรหัสรหัส ดังต่อไปนี้:
เป็นโมฆะ ShellSort (ข้อมูล int *, ความยาว int)
-
ถ้า ( ข้อมูล == NULL || ความยาว <= 0 )
กลับ;
int d = ความยาว/2; // ขนาดขั้นตอน
ในขณะที่(ง)
-
for(int i = 0; i < d; ++i) //แบ่งออกเป็นกลุ่มตามขนาดขั้นตอน และแทรกการเรียงลำดับแต่ละกลุ่ม
-
//เรียงลำดับการแทรก
สำหรับ(int j = i+d; j <ความยาว ; j +=d )
-
ถ้า (ข้อมูล [j] < ข้อมูล [j -d])
-
int temp = data[j]; //sentinel
int k = jd;
สำหรับ(; k >=0&& อุณหภูมิ < data[k]; k -=d)
-
ข้อมูล[k+d] =ข้อมูล[k];
-
ข้อมูล[k+d] =อุณหภูมิ;
-
-
-
ง = ง/2;
-
-