Shell Sort เป็นการเรียงลำดับการแทรกประเภทหนึ่งและเป็นเวอร์ชันที่มีประสิทธิภาพและปรับปรุงมากขึ้นของการเรียงลำดับการแทรกโดยตรง ใช้ลักษณะเฉพาะสองประการของการเรียงลำดับการแทรก:
1) มีประสิทธิภาพมากเมื่อขนาดข้อมูลมีขนาดเล็ก
2) ความซับซ้อนของเวลาที่จัดเรียงข้อมูลที่กำหนดแล้วคือ O(n)
ดังนั้นการเรียงลำดับเชลล์จะแบ่งข้อมูลออกเป็นหลายบล็อกในแต่ละครั้งเพื่อใช้การเรียงลำดับการแทรก จากนั้นจึงรวมบล็อกเล็ก ๆ เหล่านี้ให้เป็นบล็อกเล็ก ๆ ที่ใหญ่ขึ้นหลังจากที่เรียงลำดับแล้ว และยังคงใช้การเรียงลำดับการแทรกเพื่อรวมบล็อกเล็ก ๆ อย่างต่อเนื่องจนกระทั่งชิ้นเล็ก ๆ สุดท้าย .
ในที่นี้ แต่ละการหารออกเป็นบล็อกเล็กๆ หลายๆ บล็อกจะถูกควบคุมโดย "ส่วนเพิ่ม" ที่จุดเริ่มต้น การเพิ่มขึ้นจะมีขนาดใหญ่ใกล้กับ n/2 ดังนั้นการหารจะอยู่ใกล้กับบล็อกเล็ก n/2 และ "ส่วนเพิ่ม" จะค่อยๆ ลดลง” ในที่สุดก็ลดลงเหลือ 1
ตัวอย่างเช่น:
publicclassMain{publicstaticintcount=0;publicstaticvoidshellSort(int[]data){//คำนวณค่า h สูงสุด inth=1; While(h<=data.length/3){h=h*3+1;} while(h > 0){for(inti=h;i<data.length;i+=h){if(data[i]<data[ih]){inttmp=data[i];intj=ih;ในขณะที่(j>= 0&&data [j]>tmp){data[j+h]=data[j];j-=h;}data[j+h]=tmp;print(data);}}//คำนวณค่า h ถัดไป h= (h-1)/3;}}publicstaticvoidprint(int[]data){for(inti=0;i<data.length;i++){System.out.print(data[i]+t); }ระบบ .out.println();}publicstaticvoidmain(String[]args){int[]data=newint[]{4,6,1,9,5,8};พิมพ์(ข้อมูล);shellSort(ข้อมูล); ข้อมูล);}}ผลการวิ่งมีดังนี้:
461958146958145698145689145689