堆排序与快速排序稳定性探讨：全相等元素数组的排序疑问

Awesome question—let’s unpack this step by step, starting with a quick refresher on what sorting stability actually means, since that’s key here.

First: What is Sorting Stability? #

A sorting algorithm is stable if equal elements retain their original relative order after sorting. This only matters when equal elements are distinguishable (e.g., they have different original positions, or attached metadata like a unique ID). If every element is literally identical with no way to tell them apart, stability is irrelevant—since you can’t observe any order change.

Heap Sort: Still Unstable #

Heap sort’s instability comes from the swap operations it performs during heap construction and element extraction. These swaps don’t stop just because all elements are equal—they still disrupt the original relative order.

For example, imagine we have elements marked by their original positions: [2₁, 2₂, 2₃, 2₄]. Here’s what happens:

• Heap sort builds a max-heap (valid for any order of equal elements).
• It swaps the heap’s top element (2₁) with the last unsorted element (2₄), resulting in [2₄, 2₂, 2₃, 2₁].
• Re-heapifying does nothing (all elements are equal), so the next swap swaps 2₄ with 2₃, giving [2₃, 2₂, 2₄, 2₁].
• This pattern continues until the final array is [2₄, 2₃, 2₂, 2₁]—completely reversing the original order.

Even with all equal elements, heap sort breaks the original relative order, so it remains unstable.

Quick Sort: Still Unstable (Most Implementations) #

Quick sort’s stability depends on its partition scheme, but most standard implementations are unstable even with all equal elements:

• Hoare Partition Scheme (most common): Uses two pointers moving toward each other, swapping elements on the wrong side of the pivot. When all elements are equal, the left and right pointers will swap the first and last elements immediately, breaking their original order.
• Lomuto Partition Scheme: While simpler, it can still disrupt order if you pick a pivot that’s not at the end (e.g., a middle element). Swapping the pivot to the end shifts equal elements relative to each other.

There are modified stable quick sort variants, but these aren’t the standard versions you’ll find in most libraries or textbooks. For typical quick sort implementations, it remains unstable with all equal elements.

Final Takeaway #

If your equal elements have any distinguishable identity (like original position), both heap sort and standard quick sort are still unstable when sorting an array of all equal elements. The core mechanics that make them unstable—uncontrolled swaps for heap sort, partition-based swaps for quick sort—don’t vanish just because every element has the same value.

内容的提问来源于stack exchange，提问作者Mohammed Z. Aljezawi