จัดเรียงอย่างรวดเร็วปกติ
ค้นหาฐานค่าพื้นฐานจากนั้นจัดเรียงในการเดินทางครั้งเดียวเพื่อให้ตัวเลขทางด้านซ้ายของฐานมีขนาดเล็กกว่าฐานและตัวเลขทางด้านขวาของฐานจะมากกว่าหรือเท่ากับฐาน จากนั้นแบ่งออกเป็นสอง subarrays เรียงลำดับ เรียกซ้ำเช่นนี้
Public Class Quicksort {public Static <t ขยายเปรียบเทียบได้ <? Super t >> Void Sort (t [] arr) {sort (arr, 0, arr.length - 1);} สาธารณะคงที่ <t ขยายเปรียบเทียบได้ <? super t >> void sort (t [] arr, int ซ้าย, int ขวา) {ถ้า (ซ้าย> = ขวา) return; int p = พาร์ติชัน (arr, ซ้าย, ขวา); เรียงลำดับ (arr, ซ้าย, p - 1); เรียงลำดับ (arr, p + 1, ขวา); super t >> พาร์ติชัน int (t [] arr, int ซ้าย, int ขวา) {t base = arr [ซ้าย]; int j = ซ้าย; สำหรับ (int i = ซ้าย+1; i <= ขวา; i ++) {ถ้า (base.compareto (arr [i])> 0) {j ++; การเรียงลำดับ} การแลกเปลี่ยนโมฆะสาธารณะคงที่ (วัตถุ [] arr, int i, int j) {ถ้า (i! = j) {วัตถุอุณหภูมิ = arr [i]; arr [i] = arr [j]; arr [j] = temp;}} void printarr (วัตถุ] {system.out.print (o); system.out.print ("/t");} system.out.println ();} โมฆะคงที่สาธารณะหลัก (สตริง args []) {จำนวนเต็ม [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; 6sort (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}การเพิ่มประสิทธิภาพการเรียงลำดับอย่างรวดเร็ว: แบบสุ่มเลือกฐานค่าฐาน
เมื่ออาร์เรย์เกือบจะถูกสั่งซื้อประสิทธิภาพการสั่งซื้อที่รวดเร็วนั้นไม่ดี (เพราะหลังจากแต่ละคำสั่งซื้อขนาดซ้ำของส่วนย่อยด้านซ้ายและขวาจะแตกต่างกันมากและส่วนที่ใหญ่กว่ามีแนวโน้มที่จะไปถึง o (n^2) ในที่สุด)
การแก้ไข: ค่าอ้างอิงถูกเลือกแบบสุ่มแทนที่จะใช้หมายเลขแรกทุกครั้ง สิ่งนี้จะไม่ถูกรบกวนโดย "อาร์เรย์ที่สั่งเกือบ" แต่ประสิทธิภาพการเรียงลำดับของ "อาร์เรย์เกือบหมดคำสั่ง" อาจลดลงเล็กน้อยอย่างน้อยก็มีส่วนที่เปลี่ยนไปก่อนการเรียงลำดับ การแลกเปลี่ยนนี้ไม่มีความหมายในการสั่งซื้อ ... มีส่วนประกอบ "โชค" มากมาย ...
Public Class Quicksort {public Static <t ขยายเปรียบเทียบได้ <? Super t >> Void Sort (t [] arr) {sort (arr, 0, arr.length - 1);} สาธารณะคงที่ <t ขยายเปรียบเทียบได้ <? super t >> void sort (t [] arr, int ซ้าย, int ขวา) {ถ้า (ซ้าย> = ขวา) return; int p = พาร์ติชัน (arr, ซ้าย, ขวา); เรียงลำดับ (arr, ซ้าย, p - 1); เรียงลำดับ (arr, p + 1, ขวา); Super t >> พาร์ติชัน int (t [] arr, int ซ้าย, int ขวา) {// ก่อนการเรียงลำดับปล่อยให้ค่าอ้างอิงถูกแลกเปลี่ยนด้วยหมายเลขสุ่ม ด้วยวิธีนี้ค่าอ้างอิงจะสุ่ม // มันจะไม่ทำให้ระดับการเรียกซ้ำของด้านซ้ายและขวาไม่สอดคล้องกันเมื่ออาร์เรย์ได้รับคำสั่งค่อนข้างส่งผลให้เกิดความซับซ้อนที่เลวร้ายที่สุด (arr, ซ้าย, (int) (math.random ()*(ขวา - ซ้าย+1)+ซ้าย)); ฐาน = arr [ซ้าย]; int j = ซ้าย (base.Compareto (arr [i])> 0) {j ++; swap (arr, j, i);}} swap (arr, ซ้าย, j); return j; // กลับมุมล่างของค่าอ้างอิงหลังจากการเรียงลำดับ} {arr = arr = {{{{{ arr [j]; arr [j] = temp;}} private static void printarr (วัตถุ [] arr) {สำหรับ (วัตถุ o: arr) {system.out.print (o); system.out.print ("/t");} system.out.println ();} 0, 4, 6}; printarr (arr); // 3 5 1 7 2 9 8 0 4 6sort (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}}การเรียงลำดับอย่างรวดเร็วยังคงปรับให้เหมาะสม: ใช้การเรียงลำดับแทรกร่วมกัน
การสั่งซื้ออย่างรวดเร็วคือการลดขนาดของปัญหาอย่างต่อเนื่องเพื่อแก้ปัญหาย่อยและต้องมีการเรียกซ้ำอย่างต่อเนื่อง อย่างไรก็ตามการเรียกซ้ำมีขนาดเล็กพอและหากการเรียกซ้ำ + ไม่เสถียรนี้ยังคงดำเนินการต่อไปประสิทธิภาพอาจไม่ดีนัก
ดังนั้นเมื่อปัญหามีขนาดเล็กและเกือบจะเป็นระเบียบการเรียงลำดับการแทรกทำงานได้ดี คุณมักจะเห็นความคิดเห็นดังกล่าวใน array.sort () ที่มาพร้อมกับ Java: "ใช้การเรียงลำดับการแทรกในอาร์เรย์เล็ก ๆ ", "เรียงลำดับการเรียงลำดับที่เล็กที่สุด"
Public Class Quicksort {public Static <t ขยายเปรียบเทียบได้ <? super t >> void sort (t [] arr) {sort (arr, 0, arr.length - 1, 16);}/*** @param arr Array ที่จะจัดเรียง* @param ซ้ายใกล้* @param ใกล้ขวา* @param k ขยายเทียบเคียงได้ <? super t >> void sort (t [] arr, int ซ้าย, int ขวา, int k) {// ชั่วโมงมาตราส่วนถูกจัดเรียงโดยการแทรกถ้า (ขวา - ซ้าย <= k) {insertionsort (arr, ซ้าย, ขวา); return;} int p = พาร์ติชัน (arr, ซ้าย, ขวา); super t >> void insertionsort (t [] arr, int l, int r) {สำหรับ (int i = l + 1; i <= r; i ++) {t cur = arr [i]; int j = i-1; สำหรับ (; j> = 0 && cur.compareto (arr [J]) <0; Static <t ขยายเปรียบเทียบได้ <? Super t >> พาร์ติชัน int (t [] arr, int ซ้าย, int ขวา) {// ก่อนการเรียงลำดับปล่อยให้การแลกเปลี่ยนค่าอ้างอิงด้วยหมายเลขสุ่ม ด้วยวิธีนี้ค่าอ้างอิงจะสุ่ม // มันจะไม่ทำให้ระดับการเรียกซ้ำของด้านซ้ายและขวาไม่สอดคล้องกันเมื่ออาร์เรย์ค่อนข้างเป็นระเบียบส่งผลให้เกิดความซับซ้อนที่เลวร้ายที่สุด (arr, ซ้าย, (int) (math.random () * (ขวา - ซ้าย + 1) + ซ้าย)); t base = arr [ซ้าย]; int j = ซ้าย (base.compareto (arr [i])> 0) {j ++; swap (arr, j, i);}} swap (arr, ซ้าย, j); return j; // กลับมุมล่างของค่าฐาน arr [j]; arr [j] = temp;}} private static void printarr (วัตถุ [] arr) {สำหรับ (วัตถุ o: arr) {system.out.print (o); system.out.print ("/t");} system.out.println ();} 0, 4, 6}; printarr (arr); // 3 5 1 7 2 9 8 0 4 6sort (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}}การเรียงลำดับอย่างรวดเร็วยังคงปรับให้เหมาะสม: การเรียงลำดับเร็วสองทาง
ในการเรียงลำดับอย่างรวดเร็วปกติเริ่มต้นมีการกล่าวกันว่าค่าฐานที่ด้านซ้ายของฐานมีขนาดเล็กกว่าฐานในขณะที่ฐานทางด้านขวามากกว่าหรือเท่ากับฐาน สิ่งเหล่านี้เท่ากับฐานจะรวบรวมทางด้านขวา (หรือเปลี่ยนความสัมพันธ์ขนาดเล็กน้อยจะรวมตัวกันทางซ้าย) อย่างไรก็ตามมันจะรวมตัวกัน เมื่อมีการทำซ้ำตัวเลขจำนวนมากในอาร์เรย์มันจะนำไปสู่ความแตกต่างอย่างมากในขนาดของสองหมวดย่อย ในเวลานี้ฉันต้องการกำหนดตัวเลขเท่ากับฐานทั้งสองด้านของฐานแทนที่จะรวมเข้าด้วยกัน
(หมายเหตุ: เมื่อทดสอบรหัสควรมองหาส่วนหนึ่งของการเรียงลำดับการแทรกและดูเหมือนในรหัสของฉันด้านล่าง ... มิฉะนั้นเมื่อปริมาณข้อมูลน้อยกว่า k = 16 การเรียงลำดับการแทรกจะดำเนินการ ... )
Public Class Quicksort {public Static <t ขยายเปรียบเทียบได้ <? super t >> void sort (t [] arr) {sort (arr, 0, arr.length - 1, 16);}/*** @param arr Array ที่จะจัดเรียง* @param ซ้ายใกล้* @param ใกล้ขวา* @param k ขยายเทียบเคียงได้ <? super t >> void sort (t [] arr, int ซ้าย, int ขวา, int k) {// insertionsort (arr, ซ้าย, ขวา); // return; //} ถ้า (ซ้าย> = ขวา) กลับ; int p = พาร์ติชัน (arr, ซ้าย); super t >> void insertionsort (t [] arr, int l, int r) {สำหรับ (int i = l + 1; i <= r; i ++) {t cur = arr [i]; int j = i-1; สำหรับ (; j> = 0 && cur.compareto (arr [J]) <0; Static <t ขยายเปรียบเทียบได้ <? Super t >> พาร์ติชัน int (t [] arr, int ซ้าย, int ขวา) {// ก่อนการเรียงลำดับปล่อยให้การแลกเปลี่ยนค่าอ้างอิงด้วยหมายเลขสุ่ม ด้วยวิธีนี้ค่าอ้างอิงจะสุ่ม // มันจะไม่ทำให้เครื่องชั่งแบบเรียกซ้ำของด้านซ้ายและขวาไม่สอดคล้องกันเมื่ออาร์เรย์ได้รับคำสั่งค่อนข้างส่งผลให้เกิดความซับซ้อนที่เลวร้ายที่สุดในการแลกเปลี่ยน (arr, ซ้าย, (int) (math.random () * (ซ้าย - ซ้าย + 1) + ซ้าย); 1; // สำหรับ [ซ้าย+1 ......... ขวา] ช่วงเวลาที่กล่าวถึงในบรรทัดก่อนหน้านี้ฉันหมายถึง [ซ้าย+1 ...... i) ปิดด้านขวาขวาเปิดอยู่น้อยกว่าหรือเท่ากับฐาน int j = ขวา; // สำหรับ [ซ้าย+1 ...... ขวา] ช่วงเวลาที่กล่าวถึงในสองบรรทัดก่อนหน้า j หมายถึงค่าของ (j ...... ขวา] ซ้ายเปิดและปิดด้านขวามีมากกว่าหรือเท่ากับฐานในขณะที่ (จริง) {// สแกนจากซ้ายไปขวา ขวาไปซ้ายสแกนองค์ประกอบแรกที่เล็กกว่าฐานจากนั้น j หยุดอยู่ที่นั่น หลังจากการเรียงลำดับการเรียงลำดับ} โมฆะคงที่สาธารณะ swap (วัตถุ [] arr, int i, int j) {ถ้า (i! = j) {วัตถุอุณหภูมิ = arr [i]; arr [i] = arr [j]; arr [j] = temp;}} private static printarr (Object [] arr) {system.out.print (o); system.out.print ("/t");} system.out.println ();} โมฆะคงที่สาธารณะหลัก (สตริง args []) {จำนวนเต็ม [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; 6sort (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}ดำเนินการต่อเพื่อเพิ่มประสิทธิภาพการเรียงลำดับที่รวดเร็ว: การเรียงลำดับที่รวดเร็วสองครั้งไม่จำเป็นต้องมีการแลกเปลี่ยนใช้ Exchange
เมื่อสองเส้นทางข้างต้นค้นหาค่าที่มากกว่าฐานและค่าน้อยกว่าฐานพวกเขาใช้วิธีการแลกเปลี่ยน () เพื่อแลกเปลี่ยน การแลกเปลี่ยนสองหลักเกี่ยวข้องกับการทำงานของอุณหภูมิตัวแปรที่สามโดยมีการอ่านและเขียนเพิ่มเติม ถัดไปใช้วิธีการกำหนดโดยตรงเพื่อวางน้อยกว่าทางด้านขวาและมากกว่าทางซ้าย เมื่อฉันและเจพบตำแหน่งนั้นคือที่ควรวางฐาน การเดินทางครั้งนี้เสร็จสมบูรณ์ เพียงแค่กลับมา
Public Class Quicksort {public Static <t ขยายเปรียบเทียบได้ <? super t >> void sort (t [] arr) {sort (arr, 0, arr.length - 1, 16);}/*** @param arr Array ที่จะจัดเรียง* @param ซ้ายใกล้* @param ใกล้ขวา* @param k ขยายเทียบเคียงได้ <? super t >> void sort (t [] arr, int ซ้าย, int ขวา, int k) {// insertionsort (arr, ซ้าย, ขวา); // return; //} ถ้า (ซ้าย> = ขวา) กลับ; int p = พาร์ติชัน (arr, ซ้าย); super t >> void insertionsort (t [] arr, int l, int r) {สำหรับ (int i = l + 1; i <= r; i ++) {t cur = arr [i]; int j = i-1; สำหรับ (; j> = 0 && cur.compareto (arr [J]) <0; Static <t ขยายเปรียบเทียบได้ <? Super t >> พาร์ติชัน int (t [] arr, int ซ้าย, int ขวา) {// ก่อนการเรียงลำดับปล่อยให้การแลกเปลี่ยนค่าอ้างอิงด้วยหมายเลขสุ่ม ด้วยวิธีนี้ค่าอ้างอิงจะสุ่ม // มันจะไม่ทำให้เครื่องชั่งแบบเรียกซ้ำของด้านซ้ายและขวาไม่สอดคล้องกันเมื่ออาร์เรย์ได้รับคำสั่งค่อนข้างส่งผลให้เกิดความซับซ้อนที่เลวร้ายที่สุดในการแลกเปลี่ยน (arr, ซ้าย, (int) (math.random () * (ขวา-ซ้าย + 1) + ซ้าย); ซ้าย; // สำหรับ [ซ้าย+1 ......... ขวา] ช่วงเวลาที่กล่าวถึงในบรรทัดก่อนหน้านี้ฉันหมายถึง [ซ้าย+1 ...... i) ค่าช่วงเวลาที่ปิดด้านซ้ายปิดซ้ายน้อยกว่าหรือเท่ากับฐาน int j = ขวา; // สำหรับ [ซ้าย+1 ...... ขวา] ช่วงเวลาที่กล่าวถึงในสองบรรทัดก่อนหน้า J หมายถึงค่าของ (j ...... ขวา] เปิดซ้ายและช่วงปิดด้านขวามากกว่าหรือเท่ากับฐานในขณะที่ (i <j) {// scan จากขวาไปซ้าย j-; arr [i] = arr [j]; // สแกนจากซ้ายไปขวาสแกนองค์ประกอบแรกที่ใหญ่กว่าฐานจากนั้นฉันก็หยุดอยู่ที่นั่น int i, int j) {ถ้า (i! = j) {object temp = arr [i]; arr [i] = arr [j]; arr [j] = temp;}} private static void printarr (object [] arr) {สำหรับ (arr) {system.out.print.print (o); args []) {integer [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; printarr (arr); // 3 5 1 7 2 9 8 0 4 6sort (arr); printarr (arr);การเรียงลำดับอย่างรวดเร็วยังคงปรับให้เหมาะสม: เมื่อมีการใช้ข้อมูลจำนวนมากและการทำซ้ำจำนวนมากให้ใช้การเรียงลำดับอย่างรวดเร็วแบบสามทาง
แบ่งอาร์เรย์ออกเป็นสามเส้นทาง เส้นทางแรกมีขนาดเล็กกว่าฐานเส้นทางที่สองเท่ากับฐานและเส้นทางที่สามนั้นมากกว่าฐาน
ใช้ตัวชี้เพื่อสแกนจากด้านหน้าไปด้านหลังถ้า:
1. ตัวเลขที่ชี้ไปที่ CUR น้อยกว่าฐานจากนั้น: แลกเปลี่ยนค่าของ arr [cur] และ arr [i] จากนั้น i ++, cur ++
2. ตัวเลขที่ชี้ไปที่ CUR เท่ากับฐานจากนั้น: CUR ++
3. ตัวเลขที่ชี้ไปที่ CUR นั้นมากกว่าฐานจากนั้น: แลกเปลี่ยนค่าของ arr [cur] และ arr [j] และจากนั้น j--
เมื่อ cur> j หมายความว่าทั้งสามเส้นทางเสร็จสมบูรณ์
Public Class Quicksort {public Static <t ขยายเปรียบเทียบได้ <? super t >> void sort (t [] arr) {sort (arr, 0, arr.length - 1, 16);}/*** @param arr array ที่จะจัดเรียง* @param ซ้ายปิดซ้าย* @param ใกล้ขวา* @param k ขยายเทียบเคียงได้ <? super t >> void sort (t [] arr, int ซ้าย, int ขวา, int k) {// insertionsort (arr, ซ้าย, ขวา); // return; //} ถ้า (ซ้าย> = ขวา) กลับ; int [] ret = พาร์ติชัน (arr, ซ้าย, ขวา); super t >> void insertionsort (t [] arr, int l, int r) {สำหรับ (int i = l + 1; i <= r; i ++) {t cur = arr [i]; int j = i-1; สำหรับ (; j> = 0 && cur.compareto (arr [J]) <0; cur;}}/*** @param arr array ที่จะจัดเรียง* @param ออกจากขอบเขตซ้ายของอาร์เรย์ที่จะจัดเรียง* @param ขวาขอบเขตด้านขวาของอาร์เรย์ที่จะเรียงลำดับ* @param <t> ทั่วไป* @return*/ส่วนตัว Super t >> int [] พาร์ติชัน (t [] arr, int ซ้าย, int ขวา) {// ก่อนการเรียงลำดับปล่อยให้ค่าอ้างอิงถูกแลกเปลี่ยนด้วยหมายเลขสุ่ม ด้วยวิธีนี้ค่าอ้างอิงจะสุ่ม // มันจะไม่ทำให้เครื่องชั่งแบบเรียกซ้ำทางด้านซ้ายและขวาไม่สอดคล้องกันเมื่ออาร์เรย์ค่อนข้างเป็นระเบียบส่งผลให้เกิดความซับซ้อนที่เลวร้ายที่สุด (arr, ซ้าย, (int) (math.random () * (ขวา - ซ้าย + 1) + ซ้าย); จะถูกแบ่งออกเป็นสามช่องทาง (ช่วงเวลา) int i = ซ้าย; // ซ้ายระบุว่า [lleft ... ซ้าย) ตัวเลขทางด้านซ้ายปิดด้านขวาช่วงเปิดเปิดมีขนาดเล็กกว่าฐาน int j = ขวา; // ซ้ายแสดงว่า <= j) {ถ้า (arr [cur] .compareto (ฐาน) == 0) {cur ++;} อื่นถ้า (arr [cur] .Compareto (ฐาน) <0) {swap (arr, cur ++, i ++); และปัญหาย่อยเพียงต้องการแก้ปัญหาซ้ายและขวาของ I และ J} การแลกเปลี่ยนโมฆะคงที่สาธารณะ (Object [] arr, int i, int j) {ถ้า (i! = j) {วัตถุอุณหภูมิ = arr [i]; arr [i] = arr [j]; arr [j] = temp;}} {system.out.print (o); system.out.print ("/t");} system.out.println ();} โมฆะคงที่สาธารณะหลัก (สตริง args []) {จำนวนเต็ม [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; 6sort (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}สรุป
ข้างต้นเป็นคำอธิบายโดยละเอียดทั้งหมดของการใช้งานการเขียนโปรแกรม Java การเรียงลำดับและการปรับให้เหมาะสมที่สุด ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!