รู้เบื้องต้นเกี่ยวกับหลักการของการเรียงลำดับอย่างรวดเร็ว
การเรียงลำดับอย่างรวดเร็วคือการอัพเกรดการเรียงลำดับฟองที่เราได้เรียนรู้มาก่อน พวกเขาทั้งหมดเป็นของการเรียงลำดับการแลกเปลี่ยนและพวกเขาทั้งหมดใช้การเปรียบเทียบและการเคลื่อนไหวอย่างต่อเนื่องเพื่อให้บรรลุการเรียงลำดับ การเรียงลำดับอย่างรวดเร็วเป็นอัลกอริทึมการเรียงลำดับที่มีประสิทธิภาพมาก การใช้งานจะเพิ่มระยะห่างระหว่างการเปรียบเทียบและการเคลื่อนไหวของบันทึกและย้ายบันทึกด้วยคำหลักที่ใหญ่กว่าโดยตรงจากด้านหน้าไปด้านหลังและบันทึกด้วยคำหลักที่เล็กลงโดยตรงจากด้านหลังไปด้านหน้าซึ่งจะช่วยลดจำนวนการเปรียบเทียบและการเคลื่อนไหวทั้งหมด ในเวลาเดียวกันความคิดของการ "แบ่งและพิชิต" ถูกนำมาใช้เพื่อแยกใหญ่ออกเป็นขนาดเล็กและเล็ก ๆ เป็นสิ่งเล็ก ๆ หลักการมีดังนี้: สำหรับชุดบันทึกที่กำหนดเลือกองค์ประกอบมาตรฐานโดยปกติแล้วองค์ประกอบแรกหรือองค์ประกอบสุดท้ายจะถูกเลือกและผ่านการสแกนลำดับที่จะจัดเรียงจะถูกแบ่งออกเป็นสองส่วนซึ่งเล็กกว่าองค์ประกอบมาตรฐานและส่วนที่มากกว่าหรือเท่ากับ ในเวลานี้องค์ประกอบเกณฑ์มาตรฐานอยู่ในตำแหน่งที่ถูกต้องหลังจากจัดเรียงแล้วทั้งสองส่วนจะถูกจัดเรียงแบบซ้ำในลักษณะเดียวกันจนกว่าจะมีการสั่งซื้อทั้งหมดในลำดับ
1. จำนวน K ที่น้อยที่สุด
ป้อนหมายเลข n เพื่อค้นหาหมายเลข K ที่เล็กที่สุดเช่นป้อน 4,5,1,6,2,7,3,8 และจำนวนที่น้อยที่สุดคือ 1,2,3,4
ขึ้นอยู่กับ O (n) ปัญหานี้สามารถแก้ไขได้โดยใช้ฟังก์ชั่นการตัด หากหมายเลข Kth ของอาร์เรย์ถูกปรับตามหมายเลข Kth ดังนั้นตัวเลขทั้งหมดที่เล็กกว่าหมายเลข Kth จะอยู่ทางด้านซ้ายของอาร์เรย์และตัวเลขทั้งหมดที่ใหญ่กว่าอาร์เรย์ Kth อยู่ทางด้านขวาของอาร์เรย์ หลังจากการปรับค่า K หมายเลข K ทางด้านซ้ายของอาร์เรย์เป็นหมายเลข K ที่เล็กที่สุดซึ่งไม่จำเป็นต้องสั่งซื้อ
นำเข้า java.util.scanner; คลาสสาธารณะหลัก {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {สแกนเนอร์ใน = สแกนเนอร์ใหม่ (system.in); int n = in.nextint (); int k = in.nextint (); int [] num = new int [n]; i = 0; i <n; i ++) {num [i] = in.nextint ();} boolean b = getMink (n, num, k, out); ถ้า (b) {สำหรับ (int i = 0; i <k; int uik, int [] poutputarray) {ถ้า (pinputarray == null || poutputarray == null || uik> uiinputnum || uiinputnum <= 0 || uik <= 0) {return false;} int start = 0; ในขณะที่ (ดัชนี! = uik-1) {ถ้า (ดัชนี> uik-1) {// ดัชนีอยู่ทางด้านขวาของ k-1 end = index-1; index = พาร์ติชัน (pinputarray, เริ่มต้น, สิ้นสุด); i = 0; i <uik; i ++) {poutputArray [i] = pinputarray [i];} return true;} // ฟังก์ชั่นพาร์ติชันพาร์ติชันส่งคืนค่าดัชนีของแถวด่วนขององค์ประกอบแรกของอาร์เรย์ partition int public IND; j = end; ในขณะที่ (i <j) {ในขณะที่ (i <j && privot <= a [j]) {j-;} swap (a, i, j); ในขณะที่ (i <j && privot> = a [i]) {i ++;} swap (a, i, j);} return i;} โมฆะคงที่สาธารณะ swap (int [] a, int i, int j) {int t = a [i]; a [i] = a [j]; 2. ตัวเลขที่มีมากกว่าครึ่งหนึ่งของเหตุการณ์ในอาร์เรย์
มีตัวเลขในอาร์เรย์ที่ปรากฏมากกว่าครึ่งหนึ่งของความยาวของอาร์เรย์ โปรดค้นหาหมายเลขนี้ ตัวอย่างเช่น 1, 2, 3, 2, 2, 5, 4, 2, หมายเลข 2 ปรากฏขึ้น 5 ครั้งในอาร์เรย์เกินครึ่งหนึ่งของความยาวของอาร์เรย์เอาท์พุท 2
แรงบันดาลใจจากการเรียงลำดับอย่างรวดเร็วในการเรียงลำดับอย่างรวดเร็วตอนนี้เลือกตัวเลขในอาร์เรย์จากนั้นปรับลำดับของตัวเลขในอาร์เรย์เพื่อให้ตัวเลขที่เล็กกว่าหมายเลขที่เลือกจะถูกจัดอันดับทางซ้ายและตัวเลขที่ใหญ่กว่าหมายเลขที่เลือกจะถูกจัดอันดับทางด้านขวา
หากตัวห้อยของหมายเลขที่เลือกเกิดขึ้นเป็น n/2 หมายเลขนี้จะเป็นหมายเลขค่ามัธยฐานในอาร์เรย์
นำเข้า java.util.scanner; คลาสสาธารณะหลัก {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {เครื่องสแกนใน = สแกนเนอร์ใหม่ (System.in); int n = in.nextint (); int [] num = new int [n]; สำหรับ (int i = 0; i <n; i ++) b = gethalfnum (n, num); ถ้า (b! = -1) {system.out.println (b);}} สาธารณะคงที่ int gethalfnum (int uiinputnum, int [] pinputarray) {ถ้า (pinputarray == null || uiinputnum <= 0) start = 0; int end = uiInputNum-1; int index = พาร์ติชัน (pinputArray, start, end); ในขณะที่ (ดัชนี! = กลาง) {// ถ้ามันไม่เท่ากับครึ่งหนึ่งของความยาวก็หมายความว่าค่ามัธยฐานไม่พบถ้า (ดัชนี> กลาง) {end = index-1; index = พาร์ติชัน (pinputarray, start, end);} else {start = index+1; index = partition (pinputarray, เริ่มต้น เริ่มต้น, int end) {int privot = a [start]; int i = start; int j = end; ในขณะที่ (i <j) {ในขณะที่ (i <j && privot <= a [j]) {j-;} swap (a, i, j); ในขณะที่ (i <j & privot> = a [i]) {i ++;} swap (a, i, j);} return i;} swap แบบคงที่สาธารณะ (int [] a, int i, int j) {int t = a [i]; a [i] = a [j]; a [j] 3. ค้นหาหมายเลขที่เล็กที่สุด kth ในอาร์เรย์
ตัวอย่างเช่นอาร์เรย์ 1, 5, 2, 6, 8, 0, 6, หมายเลขที่เล็กที่สุดที่ 4 คือ 5
นำเข้า java.util.scanner; คลาสสาธารณะหลัก {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {เครื่องสแกนใน = สแกนเนอร์ใหม่ (system.in); int n = in.nextint (); int k = in.nextint (); int [] num = new int [n]; สำหรับ (int i = 0; i <n; i ++) {num [i] = in.nextint ();} int b = getMink (n, num, k); ถ้า (b! =-1) {system.out.println (b);}} uik) {ถ้า (pinputarray == null || uik> uiInputNum || uiInputNum <= 0 || uik <= 0) {return -1;} int start = 0; ในขณะที่ (index! = uik-1) {// ถ้าดัชนีไม่ใช่ตำแหน่งของ K-1 ถ้า (ดัชนี> uik-1) {end = index-1; index = พาร์ติชัน (pinputarray, start, end);} else {start = index+1; index = พาร์ติชัน สิ้นสุด) {int privot = a [start]; int i = start; int j = end; ในขณะที่ (i <j) {ในขณะที่ (i <j && privot <= a [j]) {j-;} swap (a, i, j); ในขณะที่ (i <j & privot> = a [i]) {i ++;} swap (a, i, j);} return i;} swap แบบคงที่สาธารณะ (int [] a, int i, int j) {int t = a [i]; a [i] = a [j]; a [j]สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับรหัสตัวอย่างของคำถามอัลกอริทึมสามคำถามโดยอิงจากการเรียงลำดับการเขียนโปรแกรม Java อย่างรวดเร็ว ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!