โครงสร้างข้อมูลและอัลกอริทึมยอดนิยมใน Java ที่คุณต้องรู้

ถ้าฉันต้องเลือกหัวข้อที่สำคัญที่สุดเพียงหัวข้อเดียวในการพัฒนาซอฟต์แวร์ก็คือโครงสร้างข้อมูลและอัลกอริทึม คุณอาจคิดว่ามันเป็นเครื่องมือพื้นฐานสำหรับโปรแกรมเมอร์คอมพิวเตอร์ทุกคน ในขณะที่เขียนโปรแกรมเราใช้ โครงสร้างข้อมูล เพื่อจัดเก็บและจัดระเบียบข้อมูลและ อัลกอริทึม เพื่อจัดการข้อมูลในโครงสร้างเหล่านั้น บทความนี้ประกอบด้วยการตรวจสอบโดยละเอียดของโครงสร้างข้อมูลทั่วไปและอัลกอริทึมใน เพื่อให้ผู้อ่านมีความพร้อม

ด้านล่างนี้เป็นหัวข้อที่กล่าวถึงในบทความนี้:

• โครงสร้างข้อมูลใน Java
  • โครงสร้างข้อมูลเชิงเส้น
  • โครงสร้างข้อมูลตามลำดับชั้น
• อัลกอริทึมใน Java
  • การเรียงลำดับอัลกอริทึม
  • การค้นหาอัลกอริทึม

โครงสร้างข้อมูลใน Java

โครงสร้างข้อมูลเป็นวิธีการจัดเก็บและจัดระเบียบข้อมูลในคอมพิวเตอร์เพื่อให้สามารถใช้งานได้อย่างมีประสิทธิภาพ เป็นวิธีการจัดการข้อมูลจำนวนมากอย่างมีประสิทธิภาพ และโครงสร้างข้อมูลที่มีประสิทธิภาพเป็นกุญแจสำคัญในการออกแบบอัลกอริทึมที่มีประสิทธิภาพ

ในบทความ 'โครงสร้างข้อมูลและอัลกอริทึมใน Java' นี้เราจะกล่าวถึงโครงสร้างข้อมูลพื้นฐานเช่น:

• โครงสร้างข้อมูลเชิงเส้น
  • รายการที่เชื่อมโยง
  • กอง
  • คิว

• โครงสร้างข้อมูลตามลำดับชั้น
  • ต้นไม้ไบนารี
  • กอง
  • ตารางแฮช

ลองดูแต่ละข้อ

โครงสร้างข้อมูลเชิงเส้นใน Java

โครงสร้างข้อมูลเชิงเส้นใน เป็นองค์ประกอบที่มีองค์ประกอบตามลำดับและเรียงลำดับในลักษณะที่: มีเพียงหนึ่งเดียว องค์ประกอบแรก และมีเพียงหนึ่งเดียว องค์ประกอบถัดไป มีเพียงหนึ่งเดียว องค์ประกอบสุดท้าย และมีเพียงหนึ่งเดียว องค์ประกอบก่อนหน้า ในขณะที่องค์ประกอบอื่น ๆ ทั้งหมดมี ต่อไป และก ก่อนหน้านี้ ธาตุ.

อาร์เรย์

อัน อาร์เรย์ เป็นโครงสร้างข้อมูลเชิงเส้นแสดงถึงกลุ่มขององค์ประกอบที่คล้ายกันซึ่งเข้าถึงได้โดยดัชนี ต้องระบุขนาดของอาร์เรย์ก่อนจัดเก็บข้อมูล รายการด้านล่างนี้เป็นคุณสมบัติของอาร์เรย์:

• แต่ละองค์ประกอบในอาร์เรย์เป็นชนิดข้อมูลเดียวกันและมีขนาดเท่ากัน
• องค์ประกอบของอาร์เรย์จะถูกเก็บไว้ที่ตำแหน่งหน่วยความจำที่อยู่ติดกันโดยองค์ประกอบแรกจะเริ่มต้นที่ตำแหน่งหน่วยความจำที่เล็กที่สุด
• องค์ประกอบของอาร์เรย์สามารถเข้าถึงได้โดยสุ่ม
• โครงสร้างข้อมูลอาร์เรย์ไม่ได้เป็นแบบไดนามิกอย่างสมบูรณ์

ตัวอย่างเช่น เราอาจต้องการวิดีโอเกมเพื่อติดตามคะแนนสูงสุดสิบอันดับแรกของเกมนั้น แทนที่จะใช้สิบที่แตกต่างกัน ตัวแปร สำหรับงานนี้เราสามารถใช้ชื่อเดียวสำหรับทั้งกลุ่มและใช้หมายเลขดัชนีเพื่ออ้างถึงคะแนนสูงสุดในกลุ่มนั้น

รายการที่เชื่อมโยง

ถึง เป็นโครงสร้างข้อมูลเชิงเส้นที่มีการรวบรวมหลายโหนดโดยที่ eองค์ประกอบ ach เก็บข้อมูลของตัวเองและตัวชี้ไปยังตำแหน่งขององค์ประกอบถัดไป ลิงก์สุดท้ายในรายการที่เชื่อมโยงชี้เป็นโมฆะซึ่งระบุจุดสิ้นสุดของห่วงโซ่ องค์ประกอบในรายการที่เชื่อมโยงเรียกว่าไฟล์ โหนด . โหนดแรกเรียกว่า ศีรษะ .โหนดสุดท้ายเรียกว่าที่ หาง .

ประเภทของรายการที่เชื่อมโยง

c ++ เรียงลำดับอาร์เรย์จากน้อยไปมาก

รายการที่เชื่อมโยงเดี่ยว (Uni-Directional)

รายการที่เชื่อมโยงเป็นทวีคูณ (สองทิศทาง)

รายการที่เชื่อมโยงแบบวงกลม

ตัวอย่างง่ายๆมีดังนี้ ลองนึกภาพรายการที่เชื่อมโยงกันเช่นคลิปหนีบกระดาษที่เชื่อมโยงกัน คุณสามารถเพิ่มคลิปหนีบกระดาษอีกอันที่ด้านบนหรือด้านล่างได้อย่างง่ายดาย การแทรกอันตรงกลางก็ยังรวดเร็ว สิ่งที่คุณต้องทำมีเพียงปลดโซ่ตรงกลางเพิ่มคลิปหนีบกระดาษใหม่จากนั้นเชื่อมต่ออีกครึ่งหนึ่ง รายการที่เชื่อมโยงจะคล้ายกัน

กอง

ซ้อนกัน, โครงสร้างข้อมูลนามธรรมคือชุดของ วัตถุ ที่ใส่และถอดออกตาม last-in-first-out (LIFO) หลักการ. สามารถแทรกออบเจ็กต์ลงในสแต็กได้ทุกเมื่อ แต่สามารถลบอ็อบเจ็กต์ที่แทรกล่าสุด (นั่นคือ“ สุดท้าย”) ได้ตลอดเวลารายการด้านล่างนี้เป็นคุณสมบัติของสแต็ก:

• เป็นรายการสั่งซื้อที่การแทรกและการลบสามารถทำได้ที่ปลายด้านหนึ่งที่เรียกว่าไฟล์ ด้านบน
• โครงสร้างข้อมูลแบบวนซ้ำพร้อมตัวชี้ไปที่องค์ประกอบด้านบน
• เป็นไปตามไฟล์ last-in-first-out (LIFO) หลักการ
• รองรับสองวิธีพื้นฐานที่สุด
  • push (e): แทรกองค์ประกอบ e ไปที่ด้านบนสุดของสแต็ก
  • pop (): ลบและส่งคืนองค์ประกอบบนสุดในสแตก

ตัวอย่างที่เป็นประโยชน์ของสแต็กรวมถึงเมื่อกลับคำ,เพื่อตรวจสอบความถูกต้องของ วงเล็บลำดับ,การใช้ฟังก์ชันย้อนกลับในเบราว์เซอร์และอื่น ๆ อีกมากมาย

คิว

ยังเป็นโครงสร้างข้อมูลนามธรรมอีกประเภทหนึ่ง คิวคือคอลเล็กชันของอ็อบเจ็กต์ที่ถูกแทรกและลบออกไม่เหมือนสแต็ก ก่อนเข้าก่อนออก (FIFO) หลักการ. นั่นคือสามารถแทรกองค์ประกอบได้ตลอดเวลา แต่เฉพาะองค์ประกอบที่อยู่ในคิวที่ยาวที่สุดเท่านั้นที่สามารถลบออกได้ตลอดเวลารายการด้านล่างนี้เป็นคุณสมบัติของคิว:

• มักเรียกว่า ก่อนเข้าก่อนออก รายการ
• รองรับสองวิธีพื้นฐานที่สุด
  • enqueue (e): แทรกองค์ประกอบ e ที่ ด้านหลัง ของคิว
  • dequeue (): ลบและส่งคืนองค์ประกอบจากไฟล์ ด้านหน้า ของคิว

คิวใช้ในไฟล์การถ่ายโอนข้อมูลแบบอะซิงโครนัสระหว่างสองกระบวนการการตั้งเวลา CPU การจัดตารางเวลาดิสก์และสถานการณ์อื่น ๆ ที่มีการใช้ทรัพยากรร่วมกันระหว่างผู้ใช้หลายคนและให้บริการตามเซิร์ฟเวอร์มาก่อนได้ก่อน ถัดไปในบทความ 'โครงสร้างข้อมูลและอัลกอริทึมใน Java' เรามีโครงสร้างข้อมูลแบบลำดับชั้น

โครงสร้างข้อมูลตามลำดับชั้นใน Java

ต้นไม้ไบนารี

ไบนารีทรีคือโครงสร้างข้อมูลต้นไม้แบบลำดับชั้นซึ่ง แต่ละโหนดมีลูกมากที่สุดสองลูก ซึ่งเรียกว่า เด็กซ้าย และ เด็กที่เหมาะสม . ต้นไม้ไบนารีแต่ละต้นมีกลุ่มโหนดต่อไปนี้:

• Root Node: เป็นโหนดที่อยู่บนสุดและมักเรียกว่าโหนดหลักเนื่องจากโหนดอื่น ๆ ทั้งหมดสามารถเข้าถึงได้จากรูท
• ต้นไม้ย่อยด้านซ้ายซึ่งเป็นต้นไม้ไบนารี
• ต้นไม้ย่อยด้านขวาซึ่งเป็นต้นไม้ไบนารี

รายการด้านล่างนี้เป็นคุณสมบัติของต้นไม้ไบนารี:

• ต้นไม้ไบนารีสามารถข้ามได้สองวิธี:
  • ความลึกแรก Traversal : เรียงตามลำดับ (ซ้าย - รูท - ขวา), สั่งซื้อล่วงหน้า (รูทซ้าย - ขวา) และหลังสั่ง (รูทซ้าย - ขวา - รูท)
  • การข้ามผ่านครั้งแรกที่กว้าง : การส่งผ่านคำสั่งระดับ
• ความซับซ้อนของเวลาของ Tree Traversal: O (n)
• จำนวนโหนดสูงสุดที่ระดับ 'l' = 2^l-1.

การประยุกต์ใช้ต้นไม้ไบนารี ได้แก่ :

• ใช้ในแอปพลิเคชันการค้นหาจำนวนมากที่ข้อมูลเข้า / ออกอยู่ตลอดเวลา
• เป็นเวิร์กโฟลว์สำหรับการประกอบภาพดิจิทัลสำหรับเอฟเฟกต์ภาพ
• ใช้ในเราเตอร์แบนด์วิธสูงเกือบทุกตัวสำหรับจัดเก็บตารางเราเตอร์
• ใช้ในเครือข่ายไร้สายและการจัดสรรหน่วยความจำ
• ใช้ในอัลกอริทึมการบีบอัดและอื่น ๆ อีกมากมาย

กองไบนารี

ไบนารีฮีปเสร็จสมบูรณ์ต้นไม้ไบนารีซึ่งตอบโจทย์คุณสมบัติฮีป พูดง่ายๆก็คือเป็นรูปแบบของต้นไม้ไบนารีที่มีคุณสมบัติดังต่อไปนี้:

• Heap เป็นต้นไม้ไบนารีที่สมบูรณ์: ต้นไม้จะถูกกล่าวว่าสมบูรณ์ถ้าทุกระดับยกเว้นที่ลึกที่สุดจะสมบูรณ์ ทีคุณสมบัติของ Binary Heap ทำให้เหมาะที่จะเก็บไว้ในไฟล์ .
• ติดตามคุณสมบัติฮีป: Binary Heap คือ a มิน - ฮีป หรือก Max-Heap .
  • กองไบนารีขั้นต่ำ: Fหรือทุกโหนดในฮีปค่าของโหนดคือ น้อยกว่าหรือเท่ากับ ค่านิยมของเด็ก ๆ
  • กองไบนารีสูงสุด: Fหรือทุกโหนดในฮีปค่าของโหนดคือ มากกว่าหรือเท่ากับ ค่านิยมของเด็ก ๆ

แอพพลิเคชั่นยอดนิยมของไบนารีฮีป ได้แก่ใช้ลำดับความสำคัญที่มีประสิทธิภาพค้นหาองค์ประกอบที่เล็กที่สุด (หรือใหญ่ที่สุด) อย่างมีประสิทธิภาพในอาร์เรย์และอื่น ๆ อีกมากมาย

ตารางแฮช

ลองนึกภาพว่าคุณมีไฟล์ วัตถุ และคุณต้องการกำหนดคีย์เพื่อให้ค้นหาได้ง่ายมาก ในการจัดเก็บคู่คีย์ / ค่านั้นคุณสามารถใช้อาร์เรย์ธรรมดาเช่นโครงสร้างข้อมูลซึ่งสามารถใช้คีย์ (จำนวนเต็ม) เป็นดัชนีเพื่อจัดเก็บค่าข้อมูลได้โดยตรง อย่างไรก็ตามในกรณีที่คีย์มีขนาดใหญ่เกินไปและไม่สามารถใช้เป็นดัชนีได้โดยตรงจะใช้เทคนิคที่เรียกว่าแฮช

ในการแฮชคีย์ขนาดใหญ่จะถูกแปลงเป็นคีย์ขนาดเล็กโดยใช้ ฟังก์ชันแฮช . จากนั้นค่าจะถูกเก็บไว้ในโครงสร้างข้อมูลที่เรียกว่าถึง ตารางแฮช ตารางแฮชเป็นโครงสร้างข้อมูลที่ใช้พจนานุกรม ADT ซึ่งเป็นโครงสร้างที่สามารถแมปคีย์ที่ไม่ซ้ำกับค่าได้

โดยทั่วไปตารางแฮชมีองค์ประกอบหลักสองส่วน:

1. อาร์เรย์ถัง: อาร์เรย์ที่เก็บข้อมูลสำหรับตารางแฮชคืออาร์เรย์ A ขนาด N ซึ่งแต่ละเซลล์ของ A จะถูกคิดว่าเป็น 'ที่เก็บข้อมูล' นั่นคือชุดของคู่คีย์ - ค่า จำนวนเต็ม N กำหนดความจุของอาร์เรย์
2. ฟังก์ชันแฮช: เป็นฟังก์ชันใด ๆ ที่แมปแต่ละคีย์ k ในแผนที่ของเรากับจำนวนเต็มในช่วง [0, N & ลบ 1] โดยที่ N คือความจุของอาร์เรย์ที่เก็บข้อมูลสำหรับตารางนี้

เมื่อเราใส่วัตถุลงในแฮชแท็กเป็นไปได้ว่าวัตถุต่าง ๆ อาจมีรหัสแฮชเหมือนกัน สิ่งนี้เรียกว่าไฟล์ การปะทะกัน . ในการจัดการกับการชนมีเทคนิคเช่นการผูกมัดและการระบุที่อยู่แบบเปิด

ดังนั้นนี่คือโครงสร้างข้อมูลพื้นฐานและใช้บ่อยที่สุดใน Java เมื่อคุณทราบถึงสิ่งเหล่านี้แล้วคุณสามารถเริ่มใช้งานได้ในไฟล์ . ด้วยเหตุนี้เราจึงเสร็จสิ้นส่วนแรกของบทความ 'โครงสร้างข้อมูลและอัลกอริทึมใน Java' นี้ ในส่วนต่อไปเราจะเรียนรู้เกี่ยวกับอัลกอริทึมพื้นฐานและวิธีใช้ในการใช้งานจริงเช่นการเรียงลำดับและการค้นหาการแบ่งและการพิชิตอัลกอริทึมโลภการเขียนโปรแกรมแบบไดนามิก

อัลกอริทึมใน Java

ในอดีตใช้เป็นเครื่องมือในการแก้ปัญหาการคำนวณทางคณิตศาสตร์ที่ซับซ้อนอัลกอริทึมมีความเชื่อมโยงอย่างลึกซึ้งกับวิทยาศาสตร์คอมพิวเตอร์และโดยเฉพาะอย่างยิ่งโครงสร้างข้อมูล อัลกอริทึมคือ ลำดับของคำแนะนำที่อธิบายถึงวิธีการแก้ปัญหาเฉพาะในช่วงเวลาที่ จำกัด มีสองวิธี:

• ผังงาน - มันคือการแสดงภาพของขั้นตอนการควบคุมของอัลกอริทึม
• รหัสเทียม - มันเป็นการแสดงข้อความของอัลกอริทึมที่ใกล้เคียงกับซอร์สโค้ดขั้นสุดท้าย

บันทึก: ประสิทธิภาพของอัลกอริทึมวัดจากความซับซ้อนของเวลาและความซับซ้อนของพื้นที่ ส่วนใหญ่ความซับซ้อนของอัลกอริทึมจะขึ้นอยู่กับปัญหาและอัลกอริทึมนั้นเอง

เรามาสำรวจอัลกอริทึมหลักสองประเภทใน Java ซึ่ง ได้แก่ :

• การเรียงลำดับอัลกอริทึมใน Java
• การค้นหาอัลกอริทึมใน Java

การเรียงลำดับอัลกอริทึมใน Java

อัลกอริทึมการเรียงลำดับคืออัลกอริทึมที่วางองค์ประกอบของรายการในลำดับที่แน่นอน คำสั่งที่ใช้บ่อยที่สุดคือลำดับตัวเลขและลำดับศัพท์ ในบทความ 'โครงสร้างข้อมูลและอัลกอริทึม' นี้จะให้สำรวจอัลกอริทึมการจัดเรียงบางส่วน

Bubble Sort ใน Java

ความแตกต่างระหว่างพ่อครัวกับ ansible

Bubble Sort มักเรียกว่าการจัดเรียงแบบจมเป็นอัลกอริทึมการเรียงลำดับที่ง่ายที่สุด ขั้นตอนซ้ำ ๆ ผ่านรายการที่จะจัดเรียงเปรียบเทียบองค์ประกอบที่อยู่ติดกันแต่ละคู่และสลับองค์ประกอบเหล่านี้หากเรียงลำดับไม่ถูกต้องBubble sort ได้รับชื่อเพราะกรององค์ประกอบออกไปด้านบนสุดของอาร์เรย์เช่นฟองอากาศที่ลอยอยู่บนน้ำ

นี่คือpseudocode แทน Bubble Sort Algorithm (บริบทการเรียงลำดับจากน้อยไปหามาก)

a [] คืออาร์เรย์ขนาด N start BubbleSort (a []) ประกาศจำนวนเต็ม i, j สำหรับ i = 0 ถึง N - 1 สำหรับ j = 0 ถึง N - i - 1 ถ้า a [j]> a [j + 1 ] จากนั้นสลับ [j], a [j + 1] end หากสิ้นสุดเพื่อคืนค่าสิ้นสุด BubbleSort

รหัสนี้จะสั่งอาร์เรย์หนึ่งมิติของรายการข้อมูล N จากน้อยไปหามาก วงนอกทำให้ N-1 ส่งผ่านอาร์เรย์ การส่งผ่านแต่ละครั้งใช้วงในเพื่อแลกเปลี่ยนรายการข้อมูลเพื่อให้รายการข้อมูลที่เล็กที่สุดถัดไป“ ฟองอากาศ” ไปยังจุดเริ่มต้นของอาร์เรย์ แต่ปัญหาคืออัลกอริทึมต้องการพาสเดียวทั้งหมดโดยไม่มีการสลับใด ๆ เพื่อให้ทราบว่ามีการจัดเรียงรายการ

ความซับซ้อนของเวลากรณีที่เลวร้ายที่สุดและเฉลี่ย: O (n * n) กรณีที่เลวร้ายที่สุดเกิดขึ้นเมื่ออาร์เรย์ถูกจัดเรียงแบบย้อนกลับ

ความซับซ้อนของเวลาเคสที่ดีที่สุด: บน). กรณีที่ดีที่สุดเกิดขึ้นเมื่อเรียงลำดับอาร์เรย์แล้ว

Selection Sort ใน Java

การเรียงลำดับการเลือกเป็นการผสมผสานทั้งการค้นหาและการเรียงลำดับ อัลกอริทึมจัดเรียงอาร์เรย์โดยการค้นหาองค์ประกอบต่ำสุดซ้ำ ๆ (พิจารณาจากน้อยไปหามาก) จากส่วนที่ไม่เรียงลำดับและวางไว้ในตำแหน่งที่เหมาะสมในอาร์เรย์

นี่คือรหัสเทียมที่แสดงถึงอัลกอริทึมการเรียงลำดับการเลือก (บริบทการเรียงลำดับจากน้อยไปหามาก)

a [] คืออาร์เรย์ขนาด N เริ่มต้น SelectionSort (a []) สำหรับ i = 0 ถึง n - 1 / * ตั้งค่าองค์ประกอบปัจจุบันเป็นขั้นต่ำ * / นาที = i / * ค้นหาองค์ประกอบขั้นต่ำ * / สำหรับ j = i + 1 ถึง n if list [j]
ดังที่คุณสามารถเข้าใจได้จากรหัสจำนวนครั้งที่การเรียงลำดับผ่านอาร์เรย์นั้นน้อยกว่าจำนวนรายการในอาร์เรย์ วงในจะค้นหาค่าที่เล็กที่สุดถัดไปและวงนอกจะวางค่านั้นลงในตำแหน่งที่เหมาะสม การเรียงลำดับการเลือกไม่เคยทำมากกว่า O (n) swaps และจะมีประโยชน์เมื่อการเขียนหน่วยความจำเป็นการดำเนินการที่มีค่าใช้จ่ายสูง
 ความซับซ้อนของเวลา: บน2) เนื่องจากมีสองลูปซ้อนกัน
 พื้นที่เสริม: หรือ (1).
 Insertion Sort ใน Java 
Insertion Sort เป็นอัลกอริธึมการเรียงลำดับอย่างง่ายซึ่งวนซ้ำผ่านรายการโดยใช้องค์ประกอบอินพุตทีละรายการและสร้างอาร์เรย์ที่เรียงลำดับสุดท้าย ง่ายมากและมีประสิทธิภาพมากขึ้นในชุดข้อมูลขนาดเล็ก เป็นเทคนิคการเรียงลำดับที่มั่นคงและเข้าที่
นี่คือรหัสเทียมที่แสดงอัลกอริทึมการเรียงลำดับการแทรก (บริบทการเรียงลำดับจากน้อยไปหามาก)
a [] คืออาร์เรย์ขนาด N start InsertionSort (a []) สำหรับ i = 1 ถึง N key = a [i] j = i - 1 while (j> = 0 and a [j]> key0 a [j + 1] = x [j] j = j - 1 end ในขณะที่ a [j + 1] = คีย์เอนด์สำหรับ end InsertionSort
ดังที่คุณเข้าใจได้จากโค้ดอัลกอริทึมการเรียงลำดับการแทรกลบองค์ประกอบหนึ่งออกจากข้อมูลอินพุตค้นหาตำแหน่งที่อยู่ในรายการที่เรียงลำดับและแทรกไว้ที่นั่น จะทำซ้ำจนกว่าจะไม่มีองค์ประกอบอินพุตใด ๆ ที่ไม่ได้เรียงลำดับ
 กรณีที่ดีที่สุด: กรณีที่ดีที่สุดคือเมื่ออินพุตเป็นอาร์เรย์ที่เรียงลำดับแล้ว ในกรณีนี้การเรียงลำดับการแทรกมีเวลาทำงานเชิงเส้น (เช่น & Theta (n))
 กรณีที่เลวร้ายที่สุด:  อินพุตกรณีที่แย่ที่สุดที่ง่ายที่สุดคืออาร์เรย์ที่เรียงลำดับย้อนกลับ
 QuickSort ใน Java 
Quicksort algorithm เป็นอัลกอริธึมการเรียงลำดับที่รวดเร็ววนซ้ำและไม่เสถียรซึ่งทำงานโดยใช้หลักการแบ่งและพิชิต มันเลือกองค์ประกอบเป็น pivot และแบ่งพาร์ติชันอาร์เรย์ที่กำหนดรอบ ๆ ที่เลือก pivot
 ขั้นตอนในการใช้งาน Quick sort:  
 
เลือก“ จุดหมุน” ที่เหมาะสม
แบ่งรายการออกเป็นสองรายการตามองค์ประกอบเดือยนี้ ทุกองค์ประกอบที่มีขนาดเล็กกว่าองค์ประกอบ Pivot จะอยู่ในรายการด้านซ้ายและทุกองค์ประกอบที่ใหญ่กว่าจะอยู่ในรายการด้านขวา หากองค์ประกอบเท่ากับองค์ประกอบ Pivot องค์ประกอบนั้นจะไปอยู่ในรายการใดก็ได้ เรียกว่าการดำเนินการพาร์ติชัน
เรียงลำดับรายการย่อยแต่ละรายการซ้ำ ๆ 
นี่คือรหัสเทียมที่แสดงถึง Quicksort Algorithm
QuickSort (A as array, low as int, high as int) {if (low
ในรหัสเทียมข้างต้น พาร์ติชัน () ฟังก์ชันดำเนินการกับพาร์ติชันและ Quicksort () ฟังก์ชันเรียกใช้ฟังก์ชันพาร์ติชันซ้ำ ๆ สำหรับแต่ละรายการขนาดเล็กที่สร้างขึ้น ความซับซ้อนของ Quicksort ในกรณีเฉลี่ยคือ & Theta (n log (n)) และในกรณีที่แย่ที่สุดคือ & Theta (n2)
 ผสานการเรียงลำดับใน Java 
Mergesort เป็นอัลกอริธึมการเรียงลำดับที่รวดเร็ววนซ้ำและเสถียรซึ่งทำงานโดยหลักการแบ่งและพิชิต เช่นเดียวกับ Quicksort การผสานการจัดเรียงจะแบ่งรายการองค์ประกอบออกเป็นสองรายการ รายการเหล่านี้เรียงลำดับอย่างอิสระแล้วรวมกัน ในระหว่างการรวมรายการองค์ประกอบจะถูกแทรก (หรือรวม) ในตำแหน่งที่ถูกต้องในรายการ
นี่คือ pseudocode ที่แสดงถึง Merge Sort Algorithm
กระบวนงาน MergeSort (a as array) if (n == 1) ส่งคืน var l1 เป็น array = a [0] ... a [n / 2] var l2 เป็น array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) end ขั้นตอนการผสาน (a as array, b as array) var c เป็น array ในขณะที่ (a และ b มีองค์ประกอบ) if ( a [0]> b [0]) เพิ่ม b [0] ต่อท้าย c ลบ b [0] จาก b else เพิ่ม [0] ต่อท้าย c ลบ [0] ออกจากจุดสิ้นสุดถ้าสิ้นสุดในขณะที่ (a มีองค์ประกอบ) เพิ่ม a [0] ต่อท้าย c ลบ a [0] ออกจากจุดสิ้นสุดในขณะที่ (b มีองค์ประกอบ) เพิ่ม b [0] ต่อท้าย c ลบ b [0] จาก b end ขณะกลับ ขั้นตอนการสิ้นสุด
 ผสาน () ฟังก์ชันแบ่งรายการออกเป็นสองสาย ผสาน () ในรายการเหล่านี้แยกจากกันแล้วรวมเข้าด้วยกันโดยส่งเป็นพารามิเตอร์เพื่อผสาน () ฟังก์ชันอัลกอริทึมมีความซับซ้อนของ O (n log (n)) และมีการใช้งานที่หลากหลาย
 Heap Sort ใน Java 
Heapsort คืออัลกอริทึมการเรียงลำดับตามการเปรียบเทียบโครงสร้างข้อมูล Binary Heap. คุณสามารถคิดว่ามันเป็นรุ่นปรับปรุง f การเรียงลำดับโดยที่มันแบ่งอินพุตออกเป็นภูมิภาคที่เรียงลำดับและไม่เรียงลำดับและลดขนาดพื้นที่ที่ไม่เรียงลำดับซ้ำโดยการแยกองค์ประกอบที่ใหญ่ที่สุดและย้ายไปยังพื้นที่ที่เรียงลำดับ
 ขั้นตอนในการใช้ Quicksort (ตามลำดับที่เพิ่มขึ้น): 
สร้างฮีปสูงสุดด้วยอาร์เรย์การเรียงลำดับ
ที่จุดนี้t รายการที่ใหญ่ที่สุดจะถูกเก็บไว้ที่รากของฮีป แทนที่ด้วยรายการสุดท้ายของฮีปและลดขนาดของฮีปลง 1 ในที่สุดก็ทำให้รากของต้นไม้เป็นกอง
ทำซ้ำขั้นตอนข้างต้นจนกว่าขนาดของฮีปจะมากกว่า 1
นี่คือ pseudocode ที่แสดงถึง Heap Sort Algorithm
Heapsort (a as array) สำหรับ (i = n / 2 - 1) ถึง i> = 0 heapify (a, n, i) สำหรับ i = n-1 ถึง 0 swap (a [0], a [i]) heapify (a, i, 0) end for end for heapify (a as array, n as int, i as int) maximum = i // Initialize maximum as root int l eft = 2 * i + 1 // left = 2 * i + 1 int right = 2 * i + 2 // right = 2 * i + 2 ถ้า (ซ้าย a [ใหญ่ที่สุด]) ใหญ่ที่สุด = ซ้ายถ้า (ขวา a [ใหญ่ที่สุด]) ใหญ่ที่สุด = ขวาถ้า (ใหญ่ที่สุด! = i) สลับ ( a [i], A [ใหญ่ที่สุด]) Heapify (a, n, ใหญ่ที่สุด) end heapify
นอกเหนือจากนี้ยังมีอัลกอริทึมการจัดเรียงอื่น ๆ ที่ไม่เป็นที่รู้จักกันดีเช่น Introsort, Counting Sort เป็นต้นไปยังชุดของอัลกอริทึมถัดไปในบทความ 'โครงสร้างข้อมูลและอัลกอริทึม' เรามาสำรวจอัลกอริทึมการค้นหา
 การค้นหาอัลกอริทึมใน Java 
การค้นหาเป็นหนึ่งในการดำเนินการที่พบบ่อยและดำเนินการบ่อยที่สุดในแอปพลิเคชันทางธุรกิจทั่วไป อัลกอริทึมการค้นหาคืออัลกอริทึมสำหรับการค้นหาไอเท็มที่มีคุณสมบัติที่ระบุระหว่างคอลเลกชันของไอเท็ม มาดูอัลกอริทึมการค้นหาที่ใช้บ่อยที่สุด 2 แบบ
 Linear Search Algorithm ใน Java 
การค้นหาเชิงเส้นหรือการค้นหาตามลำดับเป็นอัลกอริทึมการค้นหาที่ง่ายที่สุด เกี่ยวข้องกับการค้นหาตามลำดับสำหรับองค์ประกอบในโครงสร้างข้อมูลที่กำหนดจนกว่าจะพบองค์ประกอบหรือจุดสิ้นสุดของโครงสร้าง หากพบองค์ประกอบตำแหน่งของรายการจะถูกส่งกลับไม่เช่นนั้นอัลกอริทึมจะคืนค่า NULL
นี่คือรหัสเทียมที่แสดงถึงการค้นหาเชิงเส้นใน Java:
ขั้นตอน linear_search (a [], value) สำหรับ i = 0 ถึง n-1 ถ้า a [i] = value จากนั้นพิมพ์ 'Found' return i end ถ้า print 'Not found' end สำหรับ end linear_search
มันคืออัลกอริทึมกำลังดุร้ายแม้ว่าจะเป็นวิธีที่ง่ายที่สุด แต่ก็ไม่ใช่เรื่องธรรมดาที่สุดเนื่องจากไม่มีประสิทธิภาพ ความซับซ้อนของเวลาของการค้นหาเชิงเส้นคือ บน) .
 Binary Search Algorithm ใน Java 
การค้นหาแบบไบนารีหรือที่เรียกว่าการค้นหาลอการิทึมเป็นอัลกอริทึมการค้นหาที่ค้นหาตำแหน่งของค่าเป้าหมายภายในอาร์เรย์ที่เรียงลำดับแล้ว มันแบ่งคอลเลกชันอินพุตออกเป็นครึ่งเท่า ๆ กันและรายการจะถูกเปรียบเทียบกับองค์ประกอบตรงกลางของรายการ หากพบองค์ประกอบการค้นหาจะสิ้นสุดที่นั่น มิฉะนั้นเราจะค้นหาองค์ประกอบต่อไปโดยการแบ่งและเลือกพาร์ติชันที่เหมาะสมของอาร์เรย์โดยพิจารณาจากองค์ประกอบเป้าหมายมีขนาดเล็กหรือใหญ่กว่าองค์ประกอบกลาง
นี่คือรหัสเทียมที่แสดงถึงการค้นหาแบบไบนารีใน Java:
ขั้นตอน binary_search อาร์เรย์ที่เรียงลำดับ n ขนาดของอาร์เรย์ x ค่าที่ต้องการค้นหา lowerBound = 1 upperBound = n ในขณะที่ x ไม่พบหาก upperBound
การค้นหาจะสิ้นสุดลงเมื่อ upperBound (ตัวชี้ของเรา) ผ่าน lowerBound (องค์ประกอบสุดท้าย) ซึ่งหมายความว่าเราได้ค้นหาอาร์เรย์ทั้งหมดแล้วและองค์ประกอบนั้นไม่มีอยู่เป็นอัลกอริทึมการค้นหาที่ใช้บ่อยที่สุดเนื่องจากมีเวลาค้นหาที่รวดเร็ว ความซับซ้อนของเวลาของการค้นหาแบบไบนารีคือ บน) ซึ่งเป็นการปรับปรุงที่โดดเด่นของ บน) ความซับซ้อนของเวลาของ Linear Search
ใช้เนมสเปซ c ++
เรามาถึงตอนท้ายของบทความ 'โครงสร้างข้อมูลและอัลกอริทึมใน Java' ฉันได้กล่าวถึงหนึ่งในหัวข้อพื้นฐานและสำคัญที่สุดของ Javaหวังว่าคุณจะชัดเจนกับทุกสิ่งที่แบ่งปันกับคุณในบทความนี้
  ให้แน่ใจว่าคุณฝึกฝนให้มากที่สุดและเปลี่ยนประสบการณ์   
 ตรวจสอบไฟล์    โดย Edureka บริษัท การเรียนรู้ออนไลน์ที่เชื่อถือได้ซึ่งมีเครือข่ายผู้เรียนที่พึงพอใจมากกว่า 250,000 คนกระจายอยู่ทั่วโลก เราพร้อมที่จะช่วยเหลือคุณในทุกขั้นตอนในการเดินทางของคุณสำหรับการเป็นนอกเหนือจากคำถามสัมภาษณ์ java นี้เรามาพร้อมกับหลักสูตรที่ออกแบบมาสำหรับนักเรียนและมืออาชีพที่ต้องการเป็น Java Developer 
 มีคำถามสำหรับเรา? โปรดระบุไว้ในส่วนความคิดเห็นของ 'โครงสร้างข้อมูลและอัลกอริทึมใน Java'  บทความและเราจะติดต่อกลับโดยเร็วที่สุด