Writing in the front
- Sorting classical sorting algorithm
- Record learning
1. HeapSort
1.1 concept
Heapsort refers to a sorting algorithm designed by using the heaptree (heap) data structure, which is a kind of selective sorting. You can take advantage of the nature of arrays to quickly locate elements of a given index. Heap sort is to take the maximum number at the top of the maximum heap, adjust the remaining heap to the maximum heap, and take the maximum number at the top again. This process continues until there is only one remaining heap.
1.2 Concept of heap
A heap is a special kind of complete binary tree. An “excellent” property of a complete binary tree is that every layer except the lowest is full, which allows the heap to be represented by an array (plain plain binary trees are usually represented by linked lists as basic containers), with each node corresponding to an element in the array.
Array index: 1 2 3 4 5 6 7 8 9 10
The value of the node is 16 14 10 8 7 9 3 2 4 1
We know that the subscript of the parent is I, and we know that
- The subscript of the left child is =
2*i - The subscript of the right child is =
2*i+1
We know that the subscript of the node is j
- The subscript of the parent node =
(j-1)/2
Binary heaps are generally divided into two types: maximum heap and minimum heap. Maximum heap: The maximum element value in the maximum heap occurs at the root (the top of the heap). Each parent node in the heap has an element value greater than or equal to its child (if present).
Minimum heap: The minimum element value in the minimum heap occurs at the root (top of the heap). Each parent node in the heap has an element value less than or equal to its child (if present).
1.3 Algorithm Description
Heap sort is to take the maximum number at the top of the maximum heap, adjust the remaining heap to the maximum heap, and take the maximum number at the top again. This process continues until there is only one remaining heap. Define the following operations in the heap:
- Max-heapify: Adjusts the end child of the heap so that the child is always smaller than the parent
- Create a build-max-heap: Reorder all the data in the Heap to make it the maximum Heap
- Before we move on, one thing to note is that arrays are zero-based, which means that our Heap structure model is going to change
Make changes to the previous method
Array index: 0 1 2 3 4 5 6 7 8 9
The value of the node is 16 14 10 8 7 9 3 2 4 1
We know that the subscript of the parent is I, and we know that
- The subscript of the left child is =
2*i+1 - The subscript of the right child is =
2*i+2
Schematic diagram
1.4 Code Demonstration
package com.zhuang.algorithm;
import java.util.Arrays;
/ * * *@Classname HeapSort
* @DescriptionHeap sort *@Date 2021/6/13 17:09
* @Created by dell
*/
public class HeapSort {
public static void main(String[] args) {
int[] arr = {51.46.20.18.65.97.82.30.77.50};
heapSort(arr);
System.out.println("The heap sort sequence is :");
System.out.println(Arrays.toString(arr));
}
// Define the heap sort method
/ * * *@paramArray arr * /
public static void heapSort(int[] arr) {
int temp = 0;
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
// After the first adjustment the maximum value is at the root of the big top heap
for (int j = arr.length - 1; j >= 1; j--) {
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
System.out.println(Arrays.toString(arr));
// Recursively make the next adjustment of the big top heap
// start with root I =0
adjustHeap(arr, 0, j); }}// Define a method to adjust the subtree at position I to the big top heap
/ * * *@paramArr Array to sort *@paramI non-leaf child node *@paramLen The length of the elements participating in the array that builds the big top heap */
public static void adjustHeap(int[] arr, int i, int len) {
// Define temporary variables
int temp = arr[i];
// If I is a non-leaf node, the left child node is I *2+1; The right child is I times 2 plus 2
// Build the big top heap from left to right and from bottom up
// Continue to select the left child of the node next time
for (int k = i * 2 + 1; k < len; k = k * 2 + 1) {
If the value of the left child of the current non-leaf node is less than the value of the right child, the maximum value is selected to become the new non-leaf parent node
if (k + 1 < len && arr[k] < arr[k + 1]) {
// Select the right child node
k += 1;
}
// Compare the maximum value of the left and right child nodes with the size of the current parent node to complete the big top heap
if (arr[k] > temp) {
// Set arr[I] to the maximum value
arr[i] = arr[k];
Int temp = arr[I] = arr[k]
i = k;
} else {
break; }}// After the for loop, put the maximum value of the parent node I at the toparr[i] = temp; }}Copy the code[50.77.82.46.65.20.51.30.18.97]
[18.77.51.46.65.20.50.30.82.97]
[30.65.51.46.18.20.50.77.82.97]
[50.46.51.30.18.20.65.77.82.97]
[20.46.50.30.18.51.65.77.82.97]
[18.46.20.30.50.51.65.77.82.97]
[18.30.20.46.50.51.65.77.82.97]
[20.18.30.46.50.51.65.77.82.97]
[18.20.30.46.50.51.65.77.82.97The heap sort sequence is: [18.20.30.46.50.51.65.77.82.97]
Copy the code1.5 Algorithm Analysis
-
Best case: T(n) = O(nlog^n^)
-
Worst case: T(n) = O(nlog^n^)
-
Average case: T(n) = O(nlog^n^)
1.6 stability
Heap sort is an unstable sorting algorithm with a lot of filtering and moving.
1.7 Application Scenarios
Heap sorting can be expensive in the process of building and adjusting the heap, and is not suitable when there are few elements. However, in the case of a large number of elements, it is a good choice. Especially when solving problems such as “first n large numbers”, it is almost the preferred algorithm.
Write in the last
- Learning stage, improper description, please also point out in the comments section
- Keep it up!