Heap sorting summarized by Java sorting algorithm

This example describes the heap sorting summarized by Java sorting algorithm. Share with you for your reference. The specific analysis is as follows:

Robert W. Floyd, the winner of the 1991 Computer Pioneer Award and professor of computer science department of Stanford University, and J. Williams jointly invented the famous heap sort algorithm in 1964. This paper mainly introduces that heap sorting is implemented in Java.

Heap sort is a sort algorithm designed by using the data structure of heap tree (heap), which can quickly locate the elements of the specified index by using the characteristics of array. Heap sort is an unstable sort method. The auxiliary space is O (1) and the worst time complexity is O (nlog2n). The average performance of heap sort is close to the worst performance.

Heap sorting makes use of the maximum (or minimum) key of the records at the top of the large root heap (or small root heap), which makes it easy to select the records with the maximum (or minimum) key in the current unordered area.

(1) Basic idea of sorting with large root heap

① First build the initial file R [1.. n] into a large root heap, which is the initial unordered area ②, and then exchange the record R [1] (i.e. the top of the heap) with the largest keyword with the last record R [n] of the unordered area, so as to obtain a new unordered area R [1.. n-1] and ordered area R [n], which meet R [1.. n-1] keys≤R[n]. Key ③ since the new root R [1] after exchange may violate the heap nature, the current unordered area R [1.. n-1] should be adjusted to heap. Then, the record R [1] with the largest keyword in R [1.. n-1] is exchanged with the last record R [n-1] of the interval again, so as to obtain a new disordered region R [1.. n-2] and ordered region R [n-1.. n], which still satisfies the relationship R [1.. n-2] keys≤R[n-1..n]. Keys, also adjust R [1.. n-2] to heap Until there is only one element in the unordered area. (2) Basic operations of the large root heap sorting algorithm: ① initialization: construct R [1.. n] as the initial heap; ② basic operations of each sorting: exchange the top record R [1] of the current unordered area with the last record of the interval, and then adjust the new unordered area to heap (also build heap). Note: ① you only need to sort n-1 times and select a larger n-1 keyword to make the file increase in order. ② Sorting with a small root heap is similar to using a large root heap, except that the sorting result is decreasing and orderly. Heap sorting is opposite to direct selection sorting: at any time, the unordered area always precedes the ordered area, and the ordered area gradually expands from back to front to the whole vector at the tail of the original vector.

Code implementation:

The heap can be regarded as a tree, and the height of a node in the heap can be defined as the number of edges on the longest simple descent path from the node to the leaf node; Define the height of the heap as the height of the tree root. We will see that the running time of some basic operations on the heap structure is at most proportional to the height of the tree, which is O (LGN). I hope I can help you by reading this article.

I hope this article will be helpful to your Java programming.