This is the seventh day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Top 10 classic sorting algorithms

Ten sorting algorithms – bubble sort

Ten sorting algorithms – selection sort

Ten sorting algorithms – insertion sort

Ten sorting algorithms – Hill sort

Ten sorting algorithms – merge sort

Ten sorting algorithms – quick sort

Ten sorting algorithms – counting sort

Ten sorting algorithms – bucket sort

Ten sort algorithms – radix sort

Heap sort

The heap here is not the heap of the JVM stack, but a special binary tree, often called a binary heap. It has the following characteristics:

  • It’s a complete binary tree
  • The value of a node in the heap is always no greater or less than the value of its parent

Knowledge supplement

Binary tree

An ordered tree with no more than 2 children of a node in the tree

Full binary tree

In a binary tree, except for leaf nodes, the child nodes of each node are 2, then the binary tree is full.

Perfect binary tree

If the nodes of a full binary tree are numbered, the convention is to number them from the root, from top to bottom, from left to right. Then a binary tree of depth k with n nodes is called a complete binary tree if and only if each of its nodes corresponds to a pair of nodes numbered from 1 to n in a full binary tree of depth k.

Characteristics: Leaf nodes can only appear in the lowest level and the second level, and the lowest level of leaf nodes are concentrated in the left part of the tree. It is important to note that a full binary tree is definitely a complete binary tree, and a complete binary tree is not necessarily a full binary tree.

Binary heap

A binary heap is a special kind of heap, which can be regarded as an array of objects of a complete binary tree, and can be divided into the following two types according to its properties:

  • Large root heap: each root node is greater than or equal to its left and right child nodes, also called the maximum heap
  • Small root heap: each root node is less than or equal to its left and right child nodes, also known as the minimum heap

If an array is represented by a large root heap (the array elements are variable), it would look like this:

It follows that:

  • For a node whose position is k, the positions of its children are: left child node = 2k + 1, right child node = 2(k + 1)

    For example, if k = 1, the corresponding array of its nodes is 5

    The position of the left child node is 3, and the corresponding array value is 3

    The right child node is at position 4, and the corresponding array value is 2

  • The position of the last non-leaf node is (n/2) -1, where n is the array length

    For example, if the length of the array is 6, (6/2) -1 = 2, that is, position 2 is the last non-leaf node

Given a random number set [35,63,48,9,86,24,53,11], consider the array to be a complete binary tree:

It is clear from the figure above that this binary tree does not meet the definition of a large root heap, but it can be adjusted to make it the maximum heap. If you start from the last non-leaf node and adjust from bottom to top and right to left, then:

Through the above adjustment, the binary tree is the maximum heap, this time to start sorting, sorting rules:

  • Swap top and tail elements
  • After the swap, reposition the elements so that it becomes a binary heap again

Code implementation

public class HeapSort { public static final int[] ARRAY = {35, 63, 48, 9, 86, 24, 53, 11}; Public static int[] sort(int[] array) {int length = array.length; if (length < 2) return array; // First build a maximum heap buildMaxHeap(array); While (lenth <= 0) {// Swap (array, 0, length-1); // Swap (array, 0, length-1); length--; AdjustHeap (array, 0, length); } return array; } private static void buildMaxHeap(int[] array) {// Build the maximum heap from the last non-leaves node. For (int I = array. Length / 2-1; int I = array. i >= 0; I --) {// adjust it to the maximum heap adjustHeap(array, I, array.length); / / private static void adjustHeap(int[] array, int parent, int parent, int parent) Int length) {// Define the maximum index int maxIndex = parent; Int left = 2 * parent + 1; int left = 2 * parent + 1; Int right = 2 * (parent + 1); // If there are children, compare the size of the parent node to the size of the left and right child nodes. If (left < length && array[left] > array[maxIndex]) {// If (left < length && array[left] > array[maxIndex]); } if (right < length && array[right] > array[maxIndex]) {// If the right child is larger than the parent maxIndex = right; } // If (maxIndex! = parent) { swap(array, maxIndex, parent); AdjustHeap (array, maxIndex, length); }} private static void swap(int[] array, int I, int j) {int temp = array[I]; array[i] = array[j]; array[j] = temp; } public static void print(int[] array) { for (int i : array) { System.out.print(i + " "); } System.out.println(""); } public static void main(String[] args) { print(ARRAY); System.out.println("============================================"); print(sort(ARRAY)); }}Copy the code

Time complexity

The time complexity of the heap is order nlogn.

Reference: Time complexity analysis of heap sort

Algorithm stability

The structure of the heap is: for the node at position K, the positions of its child nodes are respectively: left child node = 2K + 1, right child node = 2(k + 1); the maximum heap requires that the parent node is greater than or equal to two of its children; the minimum heap requires that the parent node is less than or equal to two of its children.

In a sequence of length n, the process of heapsort is to select a maximum (maximum heap) or a minimum (maximum heap) of three values, starting from the NTH /2 and its children. The choice between these three elements is of course not destabilizing. But when n/2-1, n/2-2… When these parent nodes select elements, they break stability. It is possible that the NTH / 2nd parent will swap the next element, but the NTH /2-1 parent will not swap the next element, and the stability between the two identical elements will be broken. So, heapsort is not a stable sorting algorithm.

Reference: Sort stability

thinking

For quicksort, the average complexity is O(nlogn), and heapsort is also O(nlogn). The following questions:

Leetcode: the KTH largest element in the array

The KTH largest element in an unordered array.

We know that quicksort has to sort the entire array in order to get the KTH largest element.

If you use heap sort, and it’s the largest heap, then the KTH loop will find the KTH largest element, and you don’t need to sort the entire array.

So for the question of how to choose, it depends on the specific scenario, or both.