Thuật toán Sắp xếp

Putting things in order

• Sorting 排序 rearranges elements into order (smallest to largest, say).
• The AP course covers two simple sorts: selection sort 选择排序 and insertion sort 插入排序.
• Both use nested loops and swap or shift elements into place.
• Sorting first is what lets you use fast binary search afterwards.

Selection sort

• Find the smallest remaining element and swap it to the front.
• Then find the smallest of what's left, swap it into the next spot, and so on.
• The front of the array grows sorted; the back shrinks unsorted.
• One swap per pass — but it still scans the rest each pass.

An insertion sort, shifting each key into place pass by pass

Insertion sort

• Take the next element and shift it back into its correct place among the already-sorted front.
• Like sorting a hand of cards: slot each new card where it belongs.
• The sorted region grows by one each pass.
• Fast when the data is already nearly sorted.

How much work

• Both sorts use nested loops, so they do about n² comparisons in the worst case.
• That's fine for small arrays but slow for very large ones.
• They sort in place 原地 — no second array needed.
• The exam wants you to trace them, not just name them.