Shulou(Shulou.com)06/02 Report--

Today, I will talk to you about whether heap sorting is a stable sorting algorithm. Many people may not know much about it. In order to make you understand better, the editor has summarized the following content for you. I hope you can get something according to this article.

Heap sorting, quick sorting, Hill sorting and direct selection sorting are unstable sorting algorithms, while cardinality sorting, bubbling sorting, direct insertion sorting, half insertion sorting and merge sorting are stable sorting algorithms.

Heap sort

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

In a sequence with a length of n, the process of heap sorting is to choose the largest (large top heap) or the smallest (small top heap) with three values of its child nodes starting from n / 2. of course, the choice between these three elements will not destroy the stability. But when the elements are selected for the parent nodes 2-1, 2-1 and 2-2,.. .1, the stability will be destroyed.

It is possible that the n / 2 parent node exchange swaps the latter element, while the n / 2-1 parent node does not swap the latter same element, then the stability between the two same elements is destroyed. Therefore, heap sorting is not a stable sorting algorithm.

After reading the above, do you have any further understanding that heap sorting is a stable sorting algorithm? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.