จัดเรียงฟอง
การเรียงลำดับฟองเมื่อฉันเห็นอัลกอริทึมนี้ฉันจำได้ว่าคำพูดที่ว่า "ทศนิยมลอยขึ้นมาและจำนวนมากก็จมลง" ผ่านการเปรียบเทียบเลเยอร์โดยเลเยอร์ทศนิยมลอยไปที่พื้นผิวและจำนวนมาก "จมหินที่ด้านล่างของน้ำ" สิ่งนี้บรรลุผลของการเรียงลำดับ การเรียงลำดับฟองเป็นอัลกอริทึมการเรียงลำดับที่ง่าย มันเข้าเยี่ยมชมลำดับซ้ำ ๆ ที่จะจัดเรียงเปรียบเทียบสององค์ประกอบในแต่ละครั้งและสลับพวกเขาหากพวกเขาไม่ถูกต้อง งานของการเยี่ยมชมลำดับซ้ำจนกว่าจะไม่จำเป็นต้องแลกเปลี่ยนนั่นคือลำดับได้รับการจัดเรียง ต้นกำเนิดของอัลกอริทึมนี้เป็นเพราะองค์ประกอบที่เล็กกว่าจะ "ลอย" ช้ากว่าไปด้านบนของลำดับผ่านการแลกเปลี่ยน
การทำงานของอัลกอริทึมการเรียงลำดับฟองมีดังนี้:
1. เปรียบเทียบองค์ประกอบที่อยู่ติดกัน หากอันแรกนั้นใหญ่กว่าอันที่สองให้แลกเปลี่ยนกับทั้งสอง
2. ทำงานเดียวกันกับองค์ประกอบที่อยู่ติดกันแต่ละคู่เริ่มต้นจากคู่แรกถึงคู่สุดท้ายในตอนท้าย ณ จุดนี้องค์ประกอบสุดท้ายควรเป็นจำนวนมากที่สุด
3. ทำซ้ำขั้นตอนข้างต้นสำหรับองค์ประกอบทั้งหมดยกเว้นขั้นตอนสุดท้าย
4. ดำเนินการทำซ้ำขั้นตอนข้างต้นสำหรับองค์ประกอบที่น้อยลงและน้อยลงในแต่ละครั้งจนกว่าจะไม่มีตัวเลขคู่ที่ต้องเปรียบเทียบ
ไดอะแกรมกระบวนการเรียงลำดับฟอง:
รหัสตัวอย่าง
Bubblesort ระดับสาธารณะ {สาธารณะคงที่ int [] bubblesort (int [] array) {สำหรับ (int i = 0; i <array.length; i ++) {สำหรับ (int j = 0; j <array.length-i-1; j ++) {ถ้า (array [j]> array [j+1]) อาร์เรย์ [j] = อาร์เรย์ [j+1]; อาร์เรย์ [j+1] = อุณหภูมิ; }} system.out.println ("th"+(i+1)+"การเรียงลำดับ"); สำหรับ (int k = 0; k <array.length; k ++) {system.out.print (array [k]+""); } system.out.println (); } return array; } / ** * @param args * / โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int [] array = {7,3,9,5,6,8,1}; Bubblesort (อาร์เรย์); -ผลการพิมพ์:
ลำดับที่ 1 3 7 5 6 8 1 9Sorting ลำดับที่ 2 3 5 6 7 1 8 9SORTING 3 5 6 1 7 8 9Sorting ลำดับที่ 4 3 5 1 6 7 8 9 5th สั่ง 3 1 5 6 7 8 9 การสั่งซื้อ 6 7 7 7 7 7 7 1 3 5 6 7 8 9Sorting 7th Order 1 3 5 6 7 8 9Sorting ลำดับที่ 5 3 5 6 7 8 9Sorting 6th Order 1 3 5 6 7 8 9Sorting 7th สั่ง 1 3 5 6 7 8 9 การสั่งซื้อ 7 3 5 7 5 7 7 7 7 9 คำสั่ง 5th 3 5 6 7 8 9Sorting 5th Order 3 5 6 7 8 9Sorting 5th Order 3 5 6 7 8 9Sorting 5th Order 3 5 6 7 8 9Sorting 5th Order 3 5 6 7 8 9 คำสั่งลำดับที่ 5 ลำดับที่ 5 คำสั่งซื้อที่ 5
การค้นหาแบบไบนารี
หลังจากเรียงลำดับคำสั่งซื้อเราต้องค้นหาข้อมูลที่เราต้องการ การค้นหาแบบ Dichotomous เป็นอัลกอริทึมส่วนเวลาและอัลกอริทึมพื้นฐานที่ใช้กันทั่วไป การค้นหาแบบไบนารีคือการค้นหาและเปรียบเทียบจากตำแหน่งตรงกลางของข้อมูลที่จัดเรียงคล้ายกับคู่กลางของไม้ไม้ดังนั้นจึงเรียกว่าการพับและการค้นหาครึ่ง มันเป็นวิธีการค้นหาที่มีประสิทธิภาพมากขึ้น
[ข้อกำหนดการค้นหาแบบไบนารี]: 1. ต้องใช้โครงสร้างการจัดเก็บตามลำดับ 2. คีย์จะต้องจัดเรียงอย่างเป็นระเบียบตามขนาดของคำหลัก
[ข้อดีและข้อเสีย] ข้อดีของวิธีการค้นหาครึ่งสุดท้ายคือมันมีเวลาเปรียบเทียบน้อยลงความเร็วในการค้นหาที่รวดเร็วและประสิทธิภาพเฉลี่ยที่ดี ข้อเสียของมันคือตารางที่จะค้นหาเป็นตารางที่สั่งซื้อและเป็นการยากที่จะแทรกและลบ ดังนั้นวิธีการค้นหาครึ่งจึงเหมาะสำหรับรายการที่เป็นระเบียบที่ไม่ได้เปลี่ยนแปลงบ่อยและพบบ่อย
[อัลกอริทึมคิด] อันดับแรกเปรียบเทียบคำหลักที่บันทึกไว้ในตำแหน่งกลางของตารางกับคำค้นหาการค้นหา หากทั้งสองเท่ากันการค้นหาจะประสบความสำเร็จ มิฉะนั้นตารางจะถูกแบ่งออกเป็นสองตารางย่อยด้วยบันทึกตำแหน่งกลาง หากคำหลักที่บันทึกไว้ในตำแหน่งตรงกลางมากกว่าคำค้นหาการค้นหาให้ค้นหาตารางย่อยก่อนหน้าเพิ่มเติมมิฉะนั้นการค้นหาเพิ่มเติมสำหรับตารางย่อยถัดไป
ทำซ้ำกระบวนการข้างต้นจนกว่าจะมีการบันทึกที่ตรงตามเงื่อนไขเพื่อให้การค้นหาประสบความสำเร็จหรือจนกว่าตารางเด็กจะไม่มีอยู่การค้นหาจะไม่สำเร็จในเวลานี้
[ความซับซ้อนของอัลกอริทึม] สมมติว่าความยาวของอาร์เรย์คือ n ความซับซ้อนของอัลกอริทึมคือ o(log(n)), ความซับซ้อนของเวลาที่เลวร้ายที่สุดคือ O(n)。
รหัสตัวอย่าง
แพ็คเกจ com.somnus.array;/** * วิธีการค้นหาไบนารี * @author compaq * */คลาสสาธารณะ BinarySearch {สาธารณะคงที่ int binarySearch (int [] อาร์เรย์, ค่า int) {int low = 0; int high = array.length-1; int middle = 0; ในขณะที่ (ต่ำ <= สูง) {middle = (ต่ำ+สูง)/2; // 0 6 6 6 6 6 6 สำหรับ (int i = 0; i <array.length; i ++) {system.out.print (array [i]+""); if (i == กลาง) // 3 5 6 พิมพ์ตัวคั่นทันทีหลังจากจุดกึ่งกลาง {system.out.print ("##"); }} system.out.println (); if (array [middle] == ค่า) {return middle; } if (value <array [middle]) {high = middle - 1; } if (value> array [middle]) {low = middle + 1; }} return -1; } / ** * @param args * / โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int [] array = {7,3,9,5,6,8,1}; int [] array1 = bubblesort.bubblesort (อาร์เรย์); INT INDEX = BinarySearch (Array1,1); System.out.println ("local:"+index); -ผลการพิมพ์:
ลำดับที่ 1 3 7 5 6 8 1 9Sorting ลำดับที่ 2 3 5 6 7 1 8 9SORTING 3 5 6 1 7 8 9SORTING ลำดับที่ 4 3 5 1 6 7 8 9 5 1 7 7 7 7 7 7 7 7 7 7 7 7
การวิเคราะห์และสรุป
ในอัลกอริธึมการค้นหาการแบ่งขั้วนั้นเร็วที่สุด แต่ต้องเป็นลำดับที่สั่งซื้อ นี่คือรากฐานของอัลกอริทึมและเรายังคงต้องใช้ความพยายามอย่างมากในการทดลองสรุปการดูดซับและการเรียนรู้อัลกอริทึม