การเรียงลำดับการเลือก Java จะค้นหารายการที่เล็กที่สุดในรายการและย้ายค่านั้นไปที่จุดเริ่มต้นของรายการ สิ่งนี้เกิดขึ้นซ้ำๆ จนกระทั่งทุกองค์ประกอบในรายการแรกได้รับการจัดเรียง การเรียงลำดับการเลือกส่งคืนรายการที่เรียงลำดับ
คุณเรียงลำดับรายการใน Java ได้อย่างไร คุณมีตัวเลือกน้อย ตัวเลือกทั่วไปอย่างหนึ่งคือการเรียงลำดับการเลือก
ในคู่มือนี้ เราจะพูดถึงการเลือกประเภทและวิธีการทำงาน นอกจากนี้เรายังจะอธิบายวิธีการสร้างการเรียงลำดับการเลือกใน Java เพื่อให้คุณทราบวิธีการสร้างของคุณเอง เริ่มกันเลย!
Java Selection Sort คืออะไร
การเรียงลำดับการเลือกจะค้นหารายการขั้นต่ำในรายการซ้ำๆ และย้ายไปยังจุดเริ่มต้นของรายการที่ไม่ได้เรียงลำดับในรายการ กระบวนการนี้จะเกิดขึ้นซ้ำๆ กับทุกๆ รายการในรายการจนกว่าจะมีการสั่งซื้อ
รายการแรกในรายการถือเป็นรายการที่เล็กที่สุด รายการนี้ถูกเปรียบเทียบกับองค์ประกอบถัดไป หากองค์ประกอบถัดไปมีขนาดเล็กลง องค์ประกอบจะสลับกัน อัลกอริทึมนี้จะค้นหาองค์ประกอบขั้นต่ำจนกว่าจะถึงองค์ประกอบสุดท้าย จากนั้นโปรแกรมของเราจะย้ายรายการที่เล็กที่สุดไปที่จุดเริ่มต้นของรายการ
ในการเรียงลำดับการเลือก รายการประกอบด้วยสองส่วน:รายการที่เรียงลำดับและรายการที่ไม่มีการเรียงลำดับ เมื่อองค์ประกอบถูกจัดเรียง พวกมันจะย้ายจากอาร์เรย์ย่อยที่ไม่เรียงลำดับไปยังอาร์เรย์ย่อยที่จัดเรียงแล้ว
คุณสามารถเรียงลำดับรายการในลำดับจากน้อยไปมากหรือมากไปหาน้อย
คุณควรใช้การเรียงลำดับการเลือกเมื่อใด
การเรียงลำดับการเลือกจะเหมาะสมที่สุดเมื่อคุณต้องการเรียงลำดับรายการขนาดเล็ก เนื่องจากมีวิธีที่มีประสิทธิภาพมากขึ้นในการจัดเรียงรายการขนาดใหญ่ อัลกอริธึม เช่น การเรียงลำดับการผสาน การเรียงลำดับการแทรก และการเรียงลำดับอย่างรวดเร็ว มีประสิทธิภาพมากกว่าการเรียงลำดับการเลือกในการเขียนโปรแกรม Java
81% ของผู้เข้าร่วมกล่าวว่าพวกเขารู้สึกมั่นใจมากขึ้นเกี่ยวกับโอกาสในการทำงานด้านเทคโนโลยีหลังจากเข้าร่วม bootcamp จับคู่กับ Bootcamp วันนี้
ผู้สำเร็จการศึกษาจากหลักสูตร bootcamp โดยเฉลี่ยใช้เวลาน้อยกว่าหกเดือนในการเปลี่ยนอาชีพ ตั้งแต่เริ่มต้น bootcamp ไปจนถึงหางานแรก
การเรียงลำดับการเลือกทำงานได้ดีที่สุดเมื่อตรวจสอบองค์ประกอบทั้งหมดของอาร์เรย์เป็นข้อบังคับ กรณีนี้จะเกิดขึ้นหากมีการจัดเรียงรายการน้อยหรือไม่มีเลยในรายการ การเรียงลำดับการเลือกมักจะมีประสิทธิภาพดีกว่าการเรียงลำดับแบบฟอง ซึ่งเข้าใจง่ายกว่า
การเรียงลำดับการเลือกทำงานอย่างไร
มันไม่มีประโยชน์อะไรที่จะลองใช้อัลกอริธึมใน Java โดยที่ไม่รู้ว่าเราต้องการให้อัลกอริทึมของเราทำอะไรก่อน เริ่มต้นด้วยการเดินผ่านขั้นตอนต่างๆ ที่การเรียงลำดับการเลือกใช้เพื่อเรียงลำดับรายการตามลำดับ
พิจารณาอาร์เรย์ที่ไม่เรียงลำดับต่อไปนี้:
| 17 | 14 | 9 | 12 |
การเรียงลำดับการเลือกตั้งค่ารายการแรกเป็นรายการที่เล็กที่สุดในรายการ นี่เป็นค่าชั่วคราวซึ่งจะเปลี่ยนแปลงทุกครั้งที่โปรแกรมของเราทำการเปรียบเทียบ ค่านี้ถูกเก็บไว้ในตัวแปรของตัวเอง
| ขั้นต่ำ =17 | | | |
| 17 | 14 | 9 | 12 |
รายการ "ขั้นต่ำ" ถูกเปรียบเทียบกับองค์ประกอบที่สอง อิลิเมนต์นี้อยู่ในส่วนที่ไม่ได้เรียงลำดับของอาร์เรย์ ทุกองค์ประกอบหลังจากองค์ประกอบที่เรียงลำดับแล้วจะไม่เรียงลำดับ
สมมติว่าองค์ประกอบที่สองมีขนาดเล็กกว่ารายการ "ขั้นต่ำ" ในกรณีนี้ ค่าของรายการ “ขั้นต่ำ” จะถูกตั้งค่าเป็นค่าของรายการที่สอง 14 น้อยกว่า 17 ดังนั้นค่าต่ำสุดใหม่ของเราจึงกลายเป็น 14
| ขั้นต่ำ =14 | | | |
| 17 | 14 | 9 | 12 |
กระบวนการนี้ทำซ้ำสำหรับแต่ละรายการในรายการของเรา 9 น้อยกว่า 14 ดังนั้นค่าของ “ขั้นต่ำ” จะกลายเป็น 9 9 ไม่น้อยกว่า 12 ดังนั้นค่าต่ำสุดจึงเท่าเดิม
หลังจากทำซ้ำหนึ่งครั้ง รายการของเราพบว่า 9 เป็นจำนวนที่น้อยที่สุด รายการนี้ถูกย้ายไปที่จุดเริ่มต้นของรายการ:
| 9 | 17 | 14 | 12 |
กระบวนการนี้เริ่มต้นใหม่อีกครั้งจากองค์ประกอบแรกที่ไม่เรียงลำดับ ดังนั้น การเปรียบเทียบชุดต่อไปของเราจะเริ่มต้นด้วย 17:
- 17 เท่ากับค่าต่ำสุด
- โปรแกรมของเราเปรียบเทียบ 17 กับ 14 ค่าของ “ขั้นต่ำ” จะกลายเป็น 14
- โปรแกรมของเราเปรียบเทียบ 14 กับ 12 ค่าของ “ขั้นต่ำ” กลายเป็น 12
- โปรแกรมของเราย้าย 12 รายการไปที่ท้ายรายการที่จัดเรียงในรายการ
รายการของเรามีลักษณะดังนี้:
| 9 | 12 | 17 | 14 |
กระบวนการนี้จะเกิดขึ้นซ้ำๆ จนกว่ารายการของเราจะได้รับคำสั่ง เมื่ออัลกอริทึมของเราดำเนินการเสร็จสิ้น รายการต่อไปนี้จะถูกส่งคืน:
| 9 | 12 | 14 | 17 |
รายการของเราเรียงลำดับจากน้อยไปมาก
วิธีการสร้างการเรียงลำดับการเลือกใน Java
สิ่งหนึ่งที่ต้องรู้ว่าการเรียงลำดับการเลือกทำงานอย่างไร เป็นอีกหนึ่งการสร้าง มาโค้ดการเรียงลำดับการเลือกใน Java ที่ใช้ตรรกะที่เราพูดคุยกันในการดำเนินการ
ตั้งค่าโปรแกรม
สร้างไฟล์ชื่อ selection_sort.java เราจะเริ่มต้นด้วยการนำเข้าไลบรารี Java Arrays ลงในโค้ดของเรา:
import java.util.Arrays;
เราใช้ไลบรารีนี้ในภายหลังในรหัสของเรา เราใช้มันเพื่อแปลงอาร์เรย์ที่เรียงลำดับของเราเป็นสตริงเพื่อให้เราสามารถพิมพ์ไปยังคอนโซลได้
สร้างฟังก์ชันการจัดเรียง
ต่อไป เราจะประกาศคลาสและสร้างวิธีการที่ดำเนินการเรียงลำดับการเลือกของเรา เพิ่มสิ่งต่อไปนี้ใน selection_sort.java . ของคุณ ไฟล์:
class SelectionSort {
void sortNumbers(int array[]) {
int size = array.length;
for (int item = 0; item < size - 1; item++) {
int minimum = item;
for (int number = minimum + 1; number < size; number++) {
if (array[number] < array[minimum]) {
minimum = number;
}
}
int temporary = array[item];
array[item] = array[minimum];
array[minimum] = temporary;
}
}
}
ในชั้นเรียนของเรา เราได้กำหนดวิธีการที่เรียกว่า sortNumbers ซึ่งดำเนินการเรียงลำดับของเรา เราเริ่มต้นด้วยการคำนวณความยาวของอาร์เรย์ของเรา เราเก็บความยาวของอาร์เรย์ของเราไว้ในตัวแปร Java
จากนั้นเราสร้าง Java สำหรับลูป วนซ้ำนี้วนซ้ำทุกรายการในรายการของเรา ภายใน for loop เราจะพบรายการขั้นต่ำซึ่งเป็นรายการแรกในรายการ
จากนั้นเราจะเริ่มลูปใหม่เพื่อเปรียบเทียบรายการขั้นต่ำกับทุกรายการในรายการ
หากตัวเลขที่ for loop กำลังอ่านมีค่าน้อยกว่าจำนวนขั้นต่ำ ค่าของ “minimum” จะกลายเป็นตัวเลขนั้น ในลูปของเรา “number” แทนค่าดัชนีของตัวเลขที่เรากำลังเปรียบเทียบกับค่าต่ำสุด
เมื่อเปรียบเทียบจำนวนขั้นต่ำกับทุกตัวเลขในรายการแล้ว inner for loop จะหยุด จากนั้นจำนวนขั้นต่ำจะถูกย้ายตามหมายเลขที่จัดเรียงทั้งหมดในรายการ
เรียกฟังก์ชันการเรียงลำดับ
รหัสของเรายังไม่ได้ทำอะไรเลย เรายังไม่ได้เรียกชั้นเรียนของเราและให้รายชื่อเพื่อจัดเรียง
ด้านล่าง sortNumbers วิธีในรายการ เพิ่มรหัสต่อไปนี้:
public static void main(String args[]) {
int[] toSort = { 17, 14, 9, 12 };
SelectionSort newSort = new SelectionSort();
newSort.sortNumbers(toSort);
System.out.println(Arrays.toString(toSort));
}
ภายในวิธีการหลักของเรา เราได้ประกาศรายการของรายการที่จะเรียงลำดับที่เรียกว่า toSort . จากนั้นเราจะเริ่มต้นอินสแตนซ์ของคลาส SelectionSort ที่เรียกว่า newSort เราใช้สิ่งนี้เพื่อเรียก sortNumbers . ของเรา เมธอด ซึ่งเรียงลำดับค่าในอาร์เรย์ toSort
หลังจากดำเนินการเมธอด sortNumbers เราจะพิมพ์อาร์เรย์ที่เรียงลำดับไปยังคอนโซล เราทำสิ่งนี้โดยใช้ Arrays.toString() เมธอด ซึ่งจะแปลงอาร์เรย์ของเราเป็นรายการสตริง
เรียกใช้รหัสของเรา:
[9, 12, 14, 17]
รายการของเราได้รับการจัดเรียง!
Selection Sort Java:เรียงลำดับค่าจากมากไปหาน้อย
เป็นที่น่าสังเกตว่าคุณสามารถเรียงลำดับค่าจากมากไปหาน้อยได้ โดยแทนที่โค้ดบรรทัดต่อไปนี้ใน sortNumbers . ของคุณ วิธีการ:
if (array[number] < array[minimum]) { ด้วยรหัสนี้:
if (array[number] > array[minimum]) { รหัสนี้จะตรวจสอบว่าค่า "ขั้นต่ำ" มากกว่าค่าที่ for loop เข้าถึงหรือไม่ ซึ่งหมายความว่าค่า "ขั้นต่ำ" จะแสดงค่าสูงสุดในรายการแทนที่จะเป็นค่าต่ำสุด
เพื่อป้องกันความสับสน คุณควรเปลี่ยนชื่อ "ขั้นต่ำ" เป็น "สูงสุด" หากคุณกำลังเรียงลำดับรายการจากมากไปหาน้อย
คุณทำได้แล้ว คุณได้จัดเรียงรายการใน Java โดยใช้อัลกอริธึมการเรียงลำดับการเลือก
ความซับซ้อนของการเรียงลำดับการเลือก Java คืออะไร
มีความซับซ้อน 3 ครั้งที่เราต้องพิจารณาเมื่อประเมินอัลกอริทึม:กรณีที่ดีที่สุด กรณีที่เลวร้ายที่สุด และกรณีเฉลี่ย
การเรียงลำดับการเลือกมีความซับซ้อนของตัวพิมพ์เล็กที่ดีที่สุด ปานกลาง และแย่ที่สุดเป็น O(n^2) ซึ่งหมายความว่าอัลกอริทึมจะใช้เวลานานขึ้นแบบทวีคูณเมื่อจำนวนของรายการในรายการเพิ่มขึ้น
คุณสับสนกับความซับซ้อนของอัลกอริทึมหรือไม่? ตรวจสอบซีรี่ส์สองตอนของเราใน Big O Notation นี่คือสัญกรณ์ที่เราใช้เพื่ออธิบายความซับซ้อนของอัลกอริทึม
บทสรุป
การเรียงลำดับการเลือกเป็นวิธีที่มีประสิทธิภาพในการเรียงลำดับรายการข้อมูล พวกเขาทำงานโดยการเลือกรายการที่เล็กที่สุดจากรายการที่ไม่ได้เรียงลำดับและย้ายรายการนั้นไปที่จุดเริ่มต้นของรายการที่ไม่ได้เรียงลำดับ ขั้นตอนนี้จะทำซ้ำจนกว่าจะจัดเรียงรายการ
คุณต้องการเป็นนักพัฒนา Java หรือไม่? ดูคู่มือวิธีการเรียนรู้ Java ของเรา คุณจะพบเคล็ดลับและคำแนะนำการเรียนรู้ยอดนิยมเกี่ยวกับหลักสูตรออนไลน์ที่ดีที่สุดและแหล่งข้อมูลการเรียนรู้ในคู่มือนี้
