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

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

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

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

ผสาน sort-- คำหลัก ที่นี่จะแยกและผสาน เราแยกมากมายเต็มไม่ว่าจะเป็น มันหกองค์ประกอบแปดองค์ประกอบ 10,000 elements-- เราแยกมัน ลงครึ่งหนึ่งครึ่งหนึ่งครึ่งหนึ่ง จนกว่าเราจะได้อยู่ภายใต้การอาร์เรย์ n หนึ่งขององค์ประกอบอาร์เรย์ ชุดของ n หนึ่งอาร์เรย์องค์ประกอบ ดังนั้นเราจึงเริ่มต้นด้วยหนึ่ง อาร์เรย์ 1,000 องค์ประกอบ และเราได้รับไปยังจุดที่พวกเรา มี 1,000 อาร์เรย์หนึ่งองค์ประกอบ จากนั้นเราก็เริ่มที่จะผสานอาร์เรย์ย่อยเหล่านั้น กลับมารวมกันในลำดับที่ถูกต้อง ดังนั้นเราจึงใช้เวลาสองอาร์เรย์หนึ่งองค์ประกอบ และสร้างอาร์เรย์สององค์ประกอบ เราใช้เวลาสองอาร์เรย์สององค์ประกอบ และสร้างอาร์เรย์สี่องค์ประกอบ และอื่น ๆ และอื่น ๆ จนเราได้ สร้างขึ้นมาใหม่อีกครั้งหนึ่งอาร์เรย์องค์ประกอบ n 

เวลาทำงานที่เลวร้ายที่สุดกรณีของ ผสานการจัดเรียงเป็นครั้ง n log n เรามีองค์ประกอบ n แต่ กระบวนการ recombining นี้ ใช้เวลา log n ขั้นตอนที่จะได้รับ กลับไปมากมายเต็ม กรณีที่ดีที่สุดเวลาทำงานยังเป็นบันทึกของ n n เนื่องจากกระบวนการนี​​้ไม่ได้จริงๆ สนใจว่าอาร์เรย์เป็น เรียงหรือไม่ที่จะเริ่มต้นด้วย กระบวนการนี​​้เป็นกระบวนการเดียวกันที่มี วิธีการสิ่งที่ไม่มีไฟฟ้าลัดวงจร ดังนั้น n log n ในกรณีที่เลวร้ายที่สุด n log n ในกรณีที่ดีที่สุด 

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

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

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

ฉันลอยด์ดั๊กนี้เป็น CS50