โดยทั่วไปประสิทธิภาพของการเรียงลำดับจะถูกเปรียบเทียบจากสามด้าน ได้แก่ จำนวนการเปรียบเทียบข้อมูล จำนวนการย้ายข้อมูล และจำนวนพื้นที่หน่วยความจำที่ใช้
มาทำการเปรียบเทียบทั่วไปของการเรียงลำดับแบบฟอง การเรียงลำดับการเลือก การเรียงลำดับการแทรก และการเรียงลำดับอย่างรวดเร็ว โดยทั่วไปไม่ได้ใช้อัลกอริธึมการเรียงลำดับแบบบับเบิ้ลเนื่องจากจำนวนการเปรียบเทียบและการย้ายมีมากที่สุดในบรรดาอัลกอริธึมการเรียงลำดับหลายแบบ ข้อดีเพียงอย่างเดียวคืออัลกอริทึมนั้นง่ายและเข้าใจง่าย ดังนั้นจึงสามารถใช้ได้เมื่อปริมาณข้อมูลมีน้อย จะเป็นค่าแอปพลิเคชันบางส่วน การเรียงลำดับการเลือกมีจำนวนการเปรียบเทียบเท่ากับการเรียงลำดับแบบฟองซึ่งไม่มีกำลังสอง แต่จะลดจำนวนการแลกเปลี่ยนให้เหลือน้อยที่สุด จึงสามารถนำไปใช้ได้เมื่อปริมาณข้อมูลมีน้อยและการแลกเปลี่ยนข้อมูลใช้เวลานานกว่าการเปรียบเทียบ ข้อมูล เลือกการเรียงลำดับ
ในกรณีส่วนใหญ่ เมื่อปริมาณข้อมูลค่อนข้างน้อยหรือเรียงลำดับโดยทั่วไป อัลกอริธึมการเรียงลำดับการแทรกจะเป็นตัวเลือกที่ดีที่สุด สำหรับการจัดเรียงข้อมูลจำนวนมาก การเรียงลำดับอย่างรวดเร็วมักเป็นวิธีที่ดีที่สุด
อัลกอริธึมการเรียงลำดับข้างต้นใช้พื้นที่หน่วยความจำน้อยมาก และต้องการเพียงตัวแปรเพิ่มเติมเพื่อจัดเก็บรายการข้อมูลชั่วคราวระหว่างการแลกเปลี่ยน ดังนั้นจึงไม่มีการเปรียบเทียบขนาดของพื้นที่หน่วยความจำที่ถูกครอบครอง
จำนวนการเปรียบเทียบของการเรียงลำดับการแทรกยังคงเป็น n กำลังสอง แต่โดยทั่วไปจะเร็วกว่าการเรียงลำดับแบบฟองสองเท่าและเร็วกว่าการเรียงลำดับแบบเลือกเล็กน้อย มักใช้ในขั้นตอนสุดท้ายของอัลกอริธึมการเรียงลำดับที่ซับซ้อน เช่น การเรียงลำดับอย่างรวดเร็ว
อัลกอริทึม: หลังจากการประมวลผล i-1 L[1..i-1] จะถูกจัดเรียงแล้ว พาส i-th จะแทรก L[i] ลงในตำแหน่งที่เหมาะสมของ L[1..i-1] เท่านั้น
ดังนั้น L[1..i] จึงเป็นลำดับอีกครั้ง เพื่อให้บรรลุเป้าหมายนี้ เราสามารถใช้การเปรียบเทียบตามลำดับได้
ขั้นแรกให้เปรียบเทียบ L[i] และ L[i-1] ถ้า L[i-1]<=L[i] ดังนั้น L[1..i] จะถูกจัดเรียงและการประมวลผลผ่าน i-th สิ้นสุดลง
มิฉะนั้น ให้แลกเปลี่ยนตำแหน่งของ L[i] และ L[i-1] และทำการเปรียบเทียบ L[i-1] และ L[i-2] ต่อไปจนกระทั่งตำแหน่งที่แน่นอน j (1≤j≤i-1) คือ พบ.
จนกระทั่ง L[j] ≤L[j+1]
ข้อดี: มีการย้ายองค์ประกอบน้อยลง และต้องการพื้นที่เสริมเท่านั้น
ความซับซ้อนของเวลา n*n
นี่เป็นวิธีการเรียงลำดับที่ดีเมื่อจำนวนเรคคอร์ดที่จะเรียงลำดับมีน้อย แต่เมื่อ n มีขนาดใหญ่มาก ก็ไม่เหมาะสม
ตัวอย่างเช่น: ค่า int[] = { 5, 2, 4, 1, 3 };
กระบวนการเรียงลำดับ:
ครั้งที่ 1: 2,5,4,1,3
ครั้งที่ 2: 2,4,5,1,3
ครั้งที่ 3: 1,2,4,5,3
ครั้งที่ 4: 1,2,3,4,5
รหัสจาวา:
คัดลอกรหัสรหัสดังต่อไปนี้:
InsertSort ระดับสาธารณะ {
โมฆะคงที่สาธารณะ main (String [] args) {
ค่า int[] = { 5, 2, 4, 1, 3 };
เรียงลำดับ (ค่า);
สำหรับ (int i = 0; i <values.length; ++i) {
System.out.println(ค่า[i]);
-
-
การเรียงลำดับโมฆะสาธารณะแบบคงที่ (ค่า int []) {
อุณหภูมิภายใน;
อินท์เจ = 0;
สำหรับ (int i = 1; i <values.length; i++) {
if(values[i]<values[i-1])//การตัดสินที่นี่มีความสำคัญมาก ซึ่งสะท้อนถึงเหตุผลว่าทำไมการเรียงลำดับการแทรกจึงเร็วกว่าการเรียงลำดับแบบฟองและการเรียงลำดับการเลือก
-
อุณหภูมิ = ค่า [i];
//ย้ายข้อมูลไปข้างหลัง
สำหรับ (j=i-1; j>=0 && temp<values[j]; j--)
-
ค่า[เจ+1] =ค่า[เจ];
-
//แทรกข้อมูลไปที่ตำแหน่ง j+1
ค่า [j+1] = อุณหภูมิ;
System.out.print("th" + (i + 1) + "th:");
สำหรับ (int k = 0; k <values.length; k++) {
System.out.print(ค่า[k]+",");
-
System.out.println("");
-
-
-
-
ตัวอย่างที่สอง
คัดลอกรหัสรหัสดังต่อไปนี้:
แพ็คเกจ cn.cqu.coce.xutao;
ชั้นเรียนสาธารณะ zhijiecharu {
โมฆะคงที่สาธารณะ main (String args []) {
int[]={1,2,34,67,8,9,6,7,56,34,232,99};
int ฉัน,เจ,เค;
สำหรับ(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
System.out.println();
สำหรับ(i=1;i<a.length;i++){
สำหรับ(j=i-1;j>=0;j--)
ถ้า(a[i]>a[j])
หยุดพัก;
ถ้า(เจ!=i-1){
อุณหภูมิภายใน;
อุณหภูมิ=a[i];
สำหรับ(k=i-1;k>j;k--)
ก[k+1]=ก[k];
a[k+1]=อุณหภูมิ;
-
-
สำหรับ(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
System.out.println();
-
-