อัลกอริทึมการจัดเรียง
แนะนำใหม่| English | ความหมาย |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | การเรียงลำดับ |
| selection sort/sɪˈlekʃn sɔːt/ | การเรียงลำดับด้วยการเลือก |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | การเรียงลำดับด้วยการแทรก |
| in place/ɪn pleɪs/ | ในสถานที่ |
การจัดเรียงสิ่งต่างๆ
- Sorting จัดเรียงองค์ประกอบให้เป็นระเบียบ (เล็กไปใหญ่为例)
- AP course ครอบคลุมการจัดเรียงแบบง่ายสองชนิด: selection sort และ insertion sort
- ทั้งคู่ใช้ nested loops และ swap หรือ shift องค์ประกอบเข้าที่
- การ sort ก่อนเป็นสิ่งที่ทำให้คุณสามารถใช้ fast binary search ได้ในภายหลัง
การจัดเรียงแบบเลือก
- หาค่า น้อยที่สุด ที่เหลืออยู่และ สลับ กับตำแหน่งหน้าสุด
- จากนั้นหาค่าที่น้อยที่สุดของส่วนที่เหลือ สลับเข้าตำแหน่งถัดไป และทำเช่นนี้ต่อไป
- ส่วนหน้าของ arreglo จะ เรียงลำดับ; ส่วนหลังจะ ไม่เรียงลำดับ และเล็กลงเรื่อยๆ
- มีการสลับเพียงครั้งต่อรอบ遍历 — แต่มันยังต้องตรวจสอบส่วนที่เหลือในทุกรอบ遍历
Insertion sort
- นำ องค์ประกอบถัดไป มา เลื่อนกลับ ไปยังตำแหน่งที่ถูกต้องในส่วนของหน้าที่เรียงลำดับอยู่แล้ว
- เหมือนการจัดมือไพ่: วางไพ่ใหม่แต่ละใบลงในช่องที่เหมาะสม
- พื้นที่ที่เรียงลำดับจะเพิ่มขึ้นหนึ่งตำแหน่งต่อรอบ遍历
- เร็วเมื่อข้อมูล เรียงลำดับเกือบสมบูรณ์อยู่แล้ว
ปริมาณงานที่ใช้
- ทั้งสองแบบใช้ลูปซ้อนกัน ดังนั้นจึงมีการเปรียบเทียบประมาณ
n²ครั้งในกรณีแย่ที่สุด - เหมาะสำหรับอาร์เรย์ขนาดเล็ก แต่ช้าสำหรับอาร์เรย์ขนาดใหญ่มาก
- พวกมันเรียงลำดับ in place — ไม่ต้องใช้ array อื่น
- การสอบต้องการให้คุณ trace ไม่ใช่แค่ชื่อ
Selection sort SWAP عنصرที่เหลือเล็กสุดไปด้านหน้า; insertion sort SHIFT แต่ละ عنصرใหม่กลับเข้าไปในส่วนที่เรียงแล้ว — อย่าสับสนกัน** ทั้งสองเป็น Sort แบบ nested-loop O(n²) และจัดระเบียบ in place Both are strictly ordered by step-by-step tracing (the AP exam asks for the array's state after each pass), rather than memorising a name.
Selection sort on [3, 1, 2]:
- Pass 1: smallest is
1; swap to front →[1, 3, 2]. - Pass 2: smallest of
[3, 2]is2; swap →[1, 2, 3]. - Sorted — the front grew one element per pass.
Sorting เรียงลำดับองค์ประกอบ Selection sort ทำซ้ำการ SWAP عنصرที่เหลือเล็กสุดไปด้านหน้า; insertion sort SHIFT แต่ละ عنصرใหม่กลับเข้าไปในส่วนที่เรียงแล้ว ทั้งสองเป็น nested-loop, in-place, Sort แบบ O(n²) Sorting ทำให้ทำ binary search ได้เร็วขึ้น afterwards
ขั้นตอนของการจัดเรียง
แต่ละรอบจะวางองค์ประกอบเพิ่มเติมอีกหนึ่งตัวให้อยู่ในตำแหน่งที่ถูกต้อง
Selection sort ทำงานโดย...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Selection sort เลือกค่าต่ำสุดและสลับมันไปข้างหน้า
Insertion sort ทำงานโดย...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Insertion sort ใส่แต่ละองค์ประกอบลงในตำแหน่งที่เรียงลำดับแล้ว
ในกรณีแย่ที่สุด การจัดเรียงทั้งสองชนิดจะทำการเปรียบเทียบประมาณ...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ลูปซ้อนกันให้ O(n²)
ทั้ง Selection และ Insertion sort ทำงานภายใน (ไม่ต้องใช้数组เสริม)
Difficulty 1/5 · 100 coins + a small bonus on first completion today
พวกมันจัดระเบียบ数组เดิมเดียวกัน
เรียงลำดับรอบของ Selection sort บน [3, 1, 2]
Difficulty 3/5 · 200 coins + a small bonus on first completion today
ด้านหน้าจะเรียงลำดับเพิ่มขึ้น, อย่างน้อยหนึ่งองค์ประกอบต่อรอบ
การจัดเรียงก่อนช่วยได้เพราะจะทำให้เราสามารถนำไปใช้...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Binary search ต้องใช้ข้อมูลที่เรียงลำดับแล้ว