การเรียงลำดับอย่างรวดเร็วทำให้ฉันดูมันมาเป็นเวลานานและทรมานฉันมาเป็นเวลานานเพราะฉันมีความคิดทั่วไป แต่ปัญหาต่าง ๆ มักจะเกิดขึ้นเมื่อเขียนโค้ด มันยังคงยากสำหรับฉันเป็นการส่วนตัวที่จะแก้ไขมัน ความยากระดับหนึ่งและเนื่องจากการทำงานและความเกียจคร้าน ข้อผิดพลาดที่ไม่สามารถแก้ไขได้จึงถูกเลื่อนออกไปเป็นเวลานาน ในที่สุดวันนี้ก็ออกมาแล้ว และฉันก็ยังคงตื่นเต้นเล็กน้อย ให้ฉันแบ่งปันรหัสของฉันและให้ คำอธิบายเล็กน้อย
หากต้องการเรียนรู้การเรียงลำดับอย่างรวดเร็ว คุณต้องเรียนรู้วิธีการแบ่งและพิชิตก่อน แนวคิดในการแบ่งและพิชิตคือการให้สตริงของตัวเลขที่ไม่อยู่ในลำดับ (ตัวเลขเป็นเพียงสมมติฐาน อาจเป็นวัตถุอื่นก็ได้ แน่นอนพารามิเตอร์ของวิธีการสามารถกำหนดได้ด้วยตัวเอง ฉันอยู่ที่นี่ สมมติว่ามีอาร์เรย์ของจำนวนเต็ม) แล้วมอบให้เขา เลขกลาง วิธีหารแล้วพิชิตจะแบ่งเลขเหล่านี้เป็น 2 ส่วนตามเลขกลางที่กำหนดให้ ส่วนหนึ่งอยู่ทางซ้ายของเลขกลาง และอีกส่วนหนึ่งอยู่ทางขวา โดยใช้เลขนี้เป็นเลขกลาง จุดแบ่งเลขทั้ง 2 ข้างยังผิดลำดับ วิธีผมนิยามไว้ดังนี้
//ซ้ายคือจุดสิ้นสุดด้านซ้ายของส่วนแบ่งและพิชิตของอาร์เรย์ และทางขวาคือจุดสิ้นสุดรวมของส่วนแบ่งและพิชิตของอาร์เรย์ ตัวอย่างเช่น สำหรับอาร์เรย์ที่มีความยาว 10 ถ้า ฉันต้องการหารและพิชิตจำนวนเต็ม 5 ตัวแรก ฉันสามารถผ่าน 0 หรือ 4 เป็นสัญญาณ int สาธารณะFenZhi(int left,int right){ if(left<0||left>n-1||right<0||right> n-1) { return -1; } int temp = ทดสอบ [ซ้าย]; j=right; int i=left; while(i<j){ while(test[j]>=test[left]&&i<j){ j--; } ในขณะที่(ทดสอบ[i]<=ทดสอบ[ซ้าย] &&i<j){ i++; } if(i<j){ temp = test[i]; test[i]=test[j]; ทดสอบ[j]=temp; = ทดสอบ[i]; test[i]=test[left]; test[left]=temp; } สำหรับ (int m=0;m<n;m++){ System.out.print(test[m]+" "); ; }แน่นอน คุณสามารถส่งผ่านตัวเลขตรงกลางเป็นพารามิเตอร์ได้ ตอนนี้ผมใช้ตัวเลขทางซ้ายที่ส่งเข้ามาเป็นตัวหารเท่านั้น
หลังจากทำความเข้าใจการแบ่งและพิชิตแล้ว การเรียงลำดับอย่างรวดเร็วก็ทำได้ง่าย นั่นคือ การแบ่งและพิชิตตัวเลขที่แบ่งออกเป็นสองส่วน เป็นต้น จนได้ตัวเลขทั้งหมดตามลำดับดังนี้
โมฆะสาธารณะ QuickSort (int ซ้าย, int ขวา) { if (ขวา - ซ้าย <1) { return ; } อื่น ๆ { int point = this.signalFenZhi (ซ้าย, ขวา); System.out.println (จุด); point!=left&&point!=right){ QuickSort(ซ้าย,จุด-1); QuickSort(จุด+1,ขวา);ประสิทธิภาพในการเรียงลำดับอย่างรวดเร็วนั้นยอดเยี่ยมมากในบรรดาอัลกอริธึมการเรียงลำดับจำนวนมาก ความซับซ้อนของเวลาคือ O(N*log2n) อย่างไรก็ตาม หากไม่ได้เลือกจุดหารของการหารและการพิชิตที่ดี ความซับซ้อนของเวลาจะลดลงเหลือ (n กำลังสอง) ) เพราะหากอาร์เรย์นี้เกิดขึ้นแล้วเรานำหมายเลขซ้ายสุดที่ส่งผ่านทุกครั้ง ประสิทธิภาพจะต่ำมาก ดังนั้นเราจะต้องหลีกเลี่ยงสถานการณ์นี้ หากทดสอบตัวเลือกทั้งหมดแล้ว มันจะใช้เวลานานมาก เวลาดังนั้น วิธีการประนีประนอมคือการบวกเลขกลางเข้ากับเลขซ้ายสุดและเลขขวาสุด แล้วหาเลขกลางระหว่างตัวเลขเหล่านั้น การใช้ค่านี้เป็นค่าหารจะทำให้ทุกอย่างดีขึ้น ตามวิธีการข้างต้น โค้ดที่แก้ไขจะเป็นดังนี้ แต่หลังจากที่ฉันทำเสร็จแล้ว วิธีการนี้ไม่ค่อยดีนัก จะดีกว่าถ้าส่งผ่านค่าหารเป็นวิธีการแบ่งแยกและพิชิตเพื่อน ๆ ที่สามารถลองด้วยตัวเองได้ แต่ฉันจะไม่ลองที่นี่
แพ็คเกจ com.jll; FenZhi คลาสสาธารณะ { int [] ทดสอบ; int n = 10; สาธารณะ FenZhi () { ทดสอบ = ใหม่ int [10]; =(int)(Math.random()*100)+1; System.out.print(test[i]+" "); } System.out.println(); } สาธารณะ FenZhi(int n){ if(n>0){ this.n=n; test = new int[n]; for(int i=0;i<n;i++){ ทดสอบ[i]=(int)(Math.random ()*100)+1; } } } สัญญาณ int สาธารณะFenZhiMajorizationFirst(int left,int right){ if(left<0||left>n-1||right<0||right>n-1||left>=right){ return -1; } if(right-left>=2){ int กลาง = (ขวา+ซ้าย)/2; if(test[left]>test[middle]){ int temp = test[middle]; test[middle] = test[left]; if(test[left]>test[right]){ int temp = test[left]; test[left] = test[right]; ทดสอบ[ขวา]; } if(test[middle]>test[right] ){ int temp = ทดสอบ[กลาง] = ทดสอบ[ขวา]; } int temp = ทดสอบ[กลาง] = ทดสอบ[ซ้าย]; = temp; int j=right-1; int i=left+1; while(i<j){ while(test[j]>=test[left]&i<j){ j--; ]<=ทดสอบ[ซ้าย]&&i<j){ i++; } if(i<j){ temp = test[i]; test[i]=test[j]; test[j]=temp; ฉัน==เจ){ temp = test[i]; test[i]=test[left]; test[left]=temp; } /*if(i==j){ temp = test[กลาง]; ]; test[i]=temp; }*/ /*for(int m=0;m<n;m++){ System.out.print(test[m]+" "); อื่น { if(test[right]<test[left]){ int temp = test[right]; test[right] = test[left] = temp; } กลับขวา; ,int ขวา){ if(right-left<1){ return ; }else{ int point = this.signalFenZhiMajorizationFirst(left, right); System.out.println("the point คือ: "+point); quickSortMajorizationFirst(left,point-1); quickSortMajorizationFirst(point+1,right); } } public static void main(String[] args) { FenZhi f = new FenZhi(); System.out. println(f.signalFenZhiMajorizationFirst(0, 9)); System.out.println(); f.quickSortMajorizationFirst(0,fn-1); //f.quickSort(0,f.test.length-1); สำหรับ(int i:f.test){ System.out.print(i+" "); }}รหัสทำงานดังนี้:
95 40 64 18 78 23 73 84 40 ประเด็นคือ:4 ประเด็นคือ:1 ประเด็นคือ:3 ประเด็นคือ:7 ประเด็นคือ:6 ประเด็นคือ:918 23 40 40 64 73 78 84 95
ข้างต้นคือสิ่งที่ฉันได้เรียนรู้ โปรดบันทึกไว้เพื่อใช้อ้างอิงในอนาคต