Sorting Algorithms — Algorithms 练习题

Grades 11–12 / College 中等难度 10 道题

Sorting arranges elements in order (ascending or descending). Different algorithms trade off simplicity, speed, and memory. Stability means equal elements keep their relative order after sorting.

Bubble sort repeatedly swaps adjacent out-of-order pairs — O(n²) time, simple but slow. Selection sort finds minimum and swaps — also O(n²). Merge sort divides, sorts halves, merges — O(n log n), stable, uses extra memory.

Quicksort picks a pivot, partitions smaller/larger — average O(n log n), in-place variants common. For small or nearly sorted data, simpler algorithms may suffice; for large data, O(n log n) is preferred.

练习的技能

  • Tracing simple sorts on small arrays
  • Comparing time complexities
  • Understanding stable vs. unstable sorts
  • Choosing appropriate sorting algorithm
姓名： 日期： 课时：

练习题：Sorting Algorithms

说明： 仔细解答每一道题。清晰地展示所有解题过程。在指定位置或按指示在另一张纸上写出最终答案。

  1. 1.**Multiple Choice:** Which of the following sorting algorithms has the best average-case time complexity?
    1. A. Bubble Sort
    2. B. Insertion Sort
    3. C. Merge Sort
    4. D. Selection Sort

Sorting Algorithms — 练习题（续）

  1. 2.**Short Answer:** What is the worst-case time complexity of Quick Sort, and what condition causes it?
  2. 3.**Free Response:** Trace the execution of Merge Sort on the following array: [38,27,43,3,9,82,10][38, 27, 43, 3, 9, 82, 10]. Show each recursive split and the merge steps.

Sorting Algorithms — 练习题（续）

  1. 4.**Multiple Choice:** Which sorting algorithm works by repeatedly swapping adjacent elements if they are in the wrong order?
    1. A. Merge Sort
    2. B. Bubble Sort
    3. C. Quick Sort
    4. D. Heap Sort

Sorting Algorithms — 练习题（续）

  1. 5.**Short Answer:** Explain why Insertion Sort is efficient for nearly sorted data. What is its best-case time complexity?

Sorting Algorithms — 练习题（续）

  1. 6.**Free Response:** Perform one complete pass of Bubble Sort on the array [5,1,4,2,8][5, 1, 4, 2, 8], showing the array after each swap. Then state whether the array is fully sorted after that pass.

Sorting Algorithms — 练习题（续）

  1. 7.**Multiple Choice:** Which of the following is **not** an in-place sorting algorithm?
    1. A. Quick Sort
    2. B. Heap Sort
    3. C. Merge Sort
    4. D. Insertion Sort

Sorting Algorithms — 练习题（续）

  1. 8.**Short Answer:** What is the key property of a heap that makes Heap Sort possible? Briefly describe how Heap Sort works.

Sorting Algorithms — 练习题（续）

  1. 9.**Free Response:** Given the array [64,34,25,12,22,11,90][64, 34, 25, 12, 22, 11, 90], show the result after each pass of Selection Sort. How many passes are needed to fully sort the array?

Sorting Algorithms — 练习题（续）

  1. 10.**Multiple Choice:** Which sorting algorithm has a worst-case time complexity of O(n2)O(n^2) but an average-case of O(nlog⁡n)O(n \log n)?
    1. A. Merge Sort
    2. B. Quick Sort
    3. C. Heap Sort
    4. D. Bubble Sort

参考答案

  1. 1.
    Merge Sort has average-case O(nlog⁡n)O(n \log n); Bubble, Insertion, and Selection are O(n2)O(n^2).
    最终答案： C
  2. 2.
    最终答案： Worst-case time complexity is O(n2)O(n^2). This occurs when the pivot chosen is always the smallest or largest element (e.g., already sorted or reverse-sorted array with poor pivot selection).
  3. 3.
    最终答案： Split: [38,27,43,3][38,27,43,3] and [9,82,10][9,82,10] ; Further splits until single elements: ; [38,27][38,27], [43,3][43,3], [9,82][9,82], [10][10] ; Merge [38,27]→[27,38][38,27] \rightarrow [27,38]; [43,3]→[3,43][43,3] \rightarrow [3,43]; [9,82]→[9,82][9,82] \rightarrow [9,82] ; Merge [27,38][27,38] and [3,43]→[3,27,38,43][3,43] \rightarrow [3,27,38,43] ; Merge [9,82][9,82] and [10]→[9,10,82][10] \rightarrow [9,10,82] ; Final merge: [3,27,38,43][3,27,38,43] and [9,10,82]→[3,9,10,27,38,43,82][9,10,82] \rightarrow [3,9,10,27,38,43,82]
  4. 4.
    Bubble Sort repeatedly swaps adjacent elements if they are out of order.
    最终答案： B

参考答案（续）

  1. 5.
    最终答案： Insertion Sort is efficient for nearly sorted data because it only makes a few comparisons and shifts; best-case time complexity is O(n)O(n) (already sorted).
  2. 6.
    最终答案： Pass 1: ; Compare 5 and 1: swap →[1,5,4,2,8]\rightarrow [1,5,4,2,8] ; Compare 5 and 4: swap →[1,4,5,2,8]\rightarrow [1,4,5,2,8] ; Compare 5 and 2: swap →[1,4,2,5,8]\rightarrow [1,4,2,5,8] ; Compare 5 and 8: no swap ; Array after pass: [1,4,2,5,8][1,4,2,5,8]. Not fully sorted (4 and 2 are out of order).
  3. 7.
    Merge Sort requires O(n)O(n) extra space, so it is not in-place.
    最终答案： C
  4. 8.
    最终答案： A heap is a complete binary tree where each parent is greater (max-heap) or smaller (min-heap) than its children. Heap Sort builds a max-heap, then repeatedly swaps the root with the last element and reheapifies the reduced heap.

参考答案（续）

  1. 9.
    最终答案： Pass 1: [11,34,25,12,22,64,90][11,34,25,12,22,64,90] ; Pass 2: [11,12,25,34,22,64,90][11,12,25,34,22,64,90] ; Pass 3: [11,12,22,34,25,64,90][11,12,22,34,25,64,90] ; Pass 4: [11,12,22,25,34,64,90][11,12,22,25,34,64,90] ; Pass 5: [11,12,22,25,34,64,90][11,12,22,25,34,64,90] (no change) ; 6 passes are needed (for n=7n=7, Selection Sort requires n−1=6n-1=6 passes).
  2. 10.
    Quick Sort has worst-case O(n2)O(n^2) but average-case O(nlog⁡n)O(n \log n).
    最终答案： B
下载 PDF

需要避免的常见错误

  • Assuming bubble sort is O(n) with early exit always
  • Confusing merge sort space complexity
  • Incorrect pivot partition in quicksort traces
  • Thinking all O(n²) sorts behave identically in practice

生成您自己的练习表

想要一套难度自选的 sorting algorithms 新题？使用 WorksheetSmith 在几秒内编译一份可打印的自定义 PDF。

生成自定义 Sorting Algorithms 练习表

相关练习表

最后更新：2026

打开 WorksheetSmith 练习表应用