06. Sorting

Sorting

1. Basic Concepts

• Sorting: Arranging a set of data elements in ascending or descending order according to their keys
• Stability: The relative order of equal elements remains unchanged after sorting
• Time complexity, space complexity

2. Insertion Sort

• Straight insertion sort: Insert elements one by one, O(n^2)
• Binary insertion sort: Use binary search to find the insertion position, O(n^2)

3. Bubble Sort

• Compare adjacent elements and swap if necessary, O(n^2), stable

4. Selection Sort

• Select the smallest (or largest) element each time and place it at the front, O(n^2), unstable

5. Shell Sort

• Grouped insertion sort, decreasing increment, O(n^1.3~n^2)

6. Quick Sort

• Divide and conquer, choose a pivot, recursively partition left and right, O(n log n)~O(n^2), unstable

7. Heap Sort

• Build a max (or min) heap, repeatedly take the top, O(n log n), unstable

8. Merge Sort

• Divide and conquer, recursively divide, merge sorted groups, O(n log n), stable

9. Radix Sort

• Group by digit, process from low to high, O(dn), stable

10. External Sort

• Suitable for large data sets, commonly uses multi-way merge

11. Comparison and Application of Sorting Algorithms

• Compare time, space, stability, and applicable scenarios

Exercises

1. Briefly describe the basic ideas of straight insertion sort and bubble sort.
2. What are the basic steps of quick sort?
3. What is the time complexity of merge sort and heap sort?
4. Which sorting algorithms are stable?
5. What scenarios are suitable for external sorting?