การแนะนำ
การเรียงลำดับฮิลล์ (ลดวิธีการเพิ่มขึ้น) เป็นของการเรียงลำดับการแทรก มันถูกเสนอโดยเชลล์ การเรียงลำดับฮิลล์ได้ทำการปรับปรุงอย่างง่าย ๆ ในการเรียงลำดับการแทรกโดยตรง: มันเพิ่มช่วงเวลาระหว่างองค์ประกอบในการเรียงลำดับการแทรกและแทรกเข้าไปในองค์ประกอบช่วงเวลาเหล่านี้ซึ่งทำให้รายการข้อมูลเคลื่อนที่ข้ามช่วงขนาดใหญ่ หลังจากรายการข้อมูลเหล่านี้ถูกจัดเรียงครั้งเดียวอัลกอริทึมการเรียงลำดับฮิลล์จะลดช่วงเวลาของรายการข้อมูลแล้วจัดเรียงและดำเนินการต่อไป ช่วงเวลาระหว่างรายการข้อมูลเมื่อการเรียงลำดับเหล่านี้เรียกว่าเพิ่มขึ้นและตัวอักษร H ใช้เพื่อแสดงการเพิ่มขึ้นนี้
ลำดับ H ที่ใช้กันทั่วไปถูกเสนอโดย Knuth ลำดับนี้เริ่มต้นจาก 1 และสร้างขึ้นโดยสูตรต่อไปนี้:
H = 3 * H +1
โปรแกรมในทางกลับกันจำเป็นต้องคำนวณลำดับ H ในสิ่งที่ตรงกันข้ามและควรใช้
h = (h-1)/3
การใช้รหัส
รหัสการใช้งาน 1:
Public Static Void Shellsort (int [] arr) {int temp; สำหรับ (int delta = arr.length/2; delta> = 1; delta/= 2) {// เรียงลำดับการเพิ่มแต่ละครั้งสำหรับ (int i = delta; i <arr.length; i ++) {สำหรับ (int j = i; j> = delta && arr [j] <arr [j-delta]; j-delta) arr [j-delta] = arr [j]; arr [j] = อุณหภูมิ; }} // loop i} // loop delta}รหัสการใช้งาน 2:
โมฆะแบบคงที่สาธารณะ Shellsort2 (int [] arr) {int delta = 1; ในขณะที่ (delta <arr.length/3) {// สร้าง delta delta = delta*3+1; // <o (n^(3/2)) โดย Knuth, 1973>: 1, 4, 13, 40, 121, ... } int temp; สำหรับ (; delta> = 1; delta/= 3) {สำหรับ (int i = delta; i <arr.length; i ++) {สำหรับ (int j = i; j> = delta && arr [j] <arr [j-delta]; j- = delta) {temp = arr [j-delta]; arr [j-delta] = arr [j]; arr [j] = อุณหภูมิ; }} // loop i} // loop delta} เมื่อโปรแกรมข้างต้นเปรียบเทียบกับวิธีการแทรกโดยตรงคุณจะพบว่าความแตกต่างระหว่างมันกับการเรียงลำดับการแทรกโดยตรงคือ H ในการเรียงลำดับการแทรกโดยตรงจะถูกแทนที่ด้วย 1
การเรียงลำดับของเชลล์ไม่เสถียรค่าใช้จ่ายในพื้นที่ของมันคือ O (1) และค่าใช้จ่ายเวลาประมาณอยู่ระหว่าง O (N3/2) และ O (N7/6)