การแทรกการเรียงลำดับนั้นมีประสิทธิภาพเมื่อทำงานกับข้อมูลที่จัดเรียงเกือบนั่นคือประสิทธิภาพของการเรียงลำดับเชิงเส้นสามารถทำได้
แต่การเรียงลำดับการแทรกโดยทั่วไปไม่มีประสิทธิภาพเนื่องจากการเรียงลำดับการแทรกสามารถย้ายข้อมูลทีละครั้งเท่านั้น
การเรียงลำดับฮิลล์ได้รับการตั้งชื่อตาม Donald Shell นักออกแบบอัลกอริทึมที่ตีพิมพ์ในปี 1959 ตำราเรียนและคู่มืออ้างอิงเก่าบางเล่มชื่ออัลกอริทึม Shell-Metzner ซึ่งมีชื่อ Marlene Metzner Norton แต่จากข้อมูลของ Metzner เอง "ฉันไม่ได้ทำอะไรเลยสำหรับอัลกอริทึมนี้ชื่อของฉันไม่ควรปรากฏในอัลกอริทึมในชื่อของชื่อ
แนวคิดพื้นฐานของการเรียงลำดับฮิลล์: ก่อนอื่นใช้จำนวนเต็ม D1 ที่เล็กกว่า N เป็นการเพิ่มขึ้นครั้งแรกและแบ่งบันทึกทั้งหมดของไฟล์ออกเป็นกลุ่มของ D1 บันทึกทั้งหมดที่มีหลายระยะทาง D1 จะถูกวางไว้ในกลุ่มเดียวกัน ทำการเรียงลำดับการแทรกโดยตรงโดยตรงในแต่ละกลุ่ม; บันทึกจะถูกวางไว้ในกลุ่มเดียวกันและจัดเรียงโดยตรง
วิธีนี้เป็นวิธีการแทรกการจัดกลุ่ม
ตัวอย่างที่ 1:
การคัดลอกรหัสมีดังนี้:
-
* การเรียงลำดับฮิลล์หรือที่เรียกว่าอัลกอริทึมการเรียงลำดับที่ลดลงลดลงเป็นรุ่นที่มีประสิทธิภาพและปรับปรุงการเรียงลำดับ การเรียงลำดับฮิลล์เป็นอัลกอริทึมการเรียงลำดับที่ไม่มั่นคง
-
* การเรียงลำดับฮิลล์เสนอวิธีการที่ได้รับการปรับปรุงตามคุณสมบัติสองคุณสมบัติของการเรียงลำดับต่อไปนี้:
-
* แทรกการเรียงลำดับมีประสิทธิภาพเมื่อทำงานกับข้อมูลเกือบเรียงลำดับซึ่งหมายความว่าประสิทธิภาพของการเรียงลำดับเชิงเส้นสามารถทำได้
* แต่การเรียงลำดับการแทรกโดยทั่วไปไม่มีประสิทธิภาพเนื่องจากการเรียงลำดับการแทรกสามารถย้ายข้อมูลได้ทีละครั้งเท่านั้น
-
-
ฟังก์ชั่นเชลล์ (รายการ) {
var gap = math.floor (list.length / 2);
ในขณะที่ (Gap> 0) {
สำหรับ (i = gap; i <list.length; i ++) {
temp = list [i];
สำหรับ (j = i; j> = gap && list [j - gap]> temp; j - = gap) {
รายการ [j] = รายการ [J - Gap];
-
รายการ [j] = อุณหภูมิ;
-
gap = math.floor (Gap / 2);
-
รายการคืน;
-
// ทดสอบ
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
Shellsort (arr);
ตัวอย่างที่ 2:
การคัดลอกรหัสมีดังนี้:
<script type = "text/javascript">
//document.write("---------------------------------------------------------------------------------------------- ------------------------------------------------------ ------------------------- N ถึงพลัง 1.3 -------- ");
//document.write("<< <br /> <br /> ")
// var array = อาร์เรย์ใหม่ (12, 25, 32, 16, 18, 27, 59, 69, 36);
ฟังก์ชั่นเชลล์ (อาร์เรย์) {
var j, i, v, h = 1, s = 3, k, n = array.length;
var result = "";
count var = 0;
ในขณะที่ (h <n)
H = S*H+1;
ในขณะที่ (h> 1) {
h = (h-1)/s;
สำหรับ (k = 0; k <h; k ++)
สำหรับ (i = k+h, j = i; i <n; i+= h, j = i) {
v = อาร์เรย์ [i];
ในขณะที่ (จริง)
if ((j- = h)> = 0 && array [j]> v)
อาร์เรย์ [j+h] = อาร์เรย์ [j];
อื่น
หยุดพัก;
อาร์เรย์ [j+h] = v;
-
นับ ++;
ผลลัพธ์ + = "<br /> เธรด" + count + "ผลลัพธ์ของการสั่งซื้อผ่านผ่านคือ:";
สำหรับ (var n = 0; n <array.length; n ++) {
ผลลัพธ์ + = อาร์เรย์ [n] + ",";
-
-
ผลตอบแทน;
-
// allsort (อาร์เรย์);
//document.write("<<br /> <br /> ");
</script>