Is heap sort stable?

Heap sort, quick sort, Hill sort, and direct selection sort are unstable sorting algorithms, while radix sort, bubble sort, direct insertion sort, half insertion sort, and merge sort It is a stable sorting algorithm.

Heap sorting

We know that the structure of the heap is that the children of node i are 2*i and 2*i 1 nodes. The big top heap requires the parent node to be greater than or equal to its 2 child nodes. The small top heap requires that the parent node be greater than or equal to its 2 child nodes. The heap requires that the parent node be less than or equal to its 2 child nodes.

In a sequence of length n, the process of heap sorting is to select the largest (big top heap) or the smallest (small top heap) starting from the n/2th and its child nodes with a total of 3 values. The choice between elements certainly does not destroy stability. But when selecting elements for n /2-1, n/2-2, ...1 parent nodes, the stability will be destroyed.

It is possible that the n/2th parent node exchanges the next element, and the n/2-1th parent node does not exchange the next same element. Then these two same elements The stability between them is destroyed. Therefore, heap sort is not a stable sorting algorithm.

The above is the detailed content of Is heap sort stable?. For more information, please follow other related articles on the PHP Chinese website!