JAVA sorting heap sort

The editor below will bring you a cliché about comparison sorting and heap sorting. The editor thinks it is quite good, so I will share it with you now and give it as a reference for everyone. Let’s follow the editor and take a look.

Heap sorting will involve some complete binary tree knowledge. For the sequence to be sorted {10, 2, 11, 8, 7}, consider it as a complete binary tree, as shown in the figure below.

The heap is divided into a large root heap and a small root heap: the large root heap means that each root node is larger than its child nodes (L(i) >= L(2i) && L(i) >= L(2i + 1)), the small root heap means that each root node is smaller than its child node (L(i) <= L(2i) && L(i) <= L( 2i + 1)). (In a complete binary tree, the left child node of the i-th node is 2i, and its right byte node is 2i + 1)

This article will use the construction of a large root heap as an example to explain.

The first step in heap sorting is to build the initial heap. How to build the initial heap? By definition, the key point lies in each root node. Observing the complete binary tree of the above-mentioned sequence to be sorted, it is not difficult to find that node 2 and node 10 have child nodes, which are the nodes that need attention.

How to locate node 2? It is found that it is a leaf node, or the parent node of the last node. According to the properties of a complete binary tree, the number of the parent node of any node except the root node is ⌊n / 2⌋. Given that n = 5, it is easy to know that the number of node 2 is ⌊5 / 2⌋ = ②. Compare it to the size of the left and right child nodes and adjust.

Finally, the root node 10 is left. The number of node 2 is known to be ②, ② - 1 = ①, which means the number of root node 10 is obtained. Compare it to the size of the left and right child nodes and adjust.

After the adjustment, it was found that a "large root heap" has been formed. The column to be sorted in the example is relatively simple, and a more complex column to be sorted is given to observe the The process of building a large root pile. For the sequence to be sorted {53, 17, 78, 09, 45, 65, 87, 32}, treat it as a complete binary tree.

Similarly, let’s look at the nodes it needs to pay attention to.

According to the first example, we can easily locate the number of node 09 as ⌊8 / 2⌋ = ④, and the number of node 78 as ④ - 1 = ③… ..., and so on, we found a certain pattern, that is, the node position that needs to be adjusted is from ⌊n / 2⌋ Start decreasing in sequence until the end of the root node ① (⌊n / 2⌋ ~ 1). Start adjusting now.

# Found after the fourth adjustment Node 53 does not meet the definition of a large root heap, and its right child node is larger than it. At this time, further downward adjustment is required.

Note that downward adjustments need to be made every time there is an upward adjustment to determine whether a downward adjustment is needed, rather than looking back after all upward adjustments are completed. Adjust downward. In this way, the large root heap is established, and the situation of the column array to be sorted has changed: {87, 45, 78, 32, 17, 65, 53, 09}. Next is the question of how to sort. Swap the root node of the large root heap with the last node, and adjust the binary tree so that it still satisfies the large root heap.

You can see that after calling the root node and the last node, the maximum value of the column to be sorted has been placed at the last position of the array {..., 87}. At this time, the first sorting is completed, but this first The pass sorting is not over yet. At this time, except for node 87, the other nodes do not meet the conditions of the large root heap, so the remaining nodes need to be adjusted to the large root heap. The sorting process is no longer given. The code implementation in Java and Python3 is as follows.

Java

package com.algorithm.sort.heap;

import java.util.Arrays;

/**
 * 堆排序
 * Created by yulinfeng on 6/20/17.
 */
public class Heap {
  
  public static void main(String[] args) {
    int[] nums = {53, 17, 78, 09, 45, 65, 87, 32};
    nums = heapSort(nums);
    System.out.println(Arrays.toString(nums));
  }
  
  /**
   * 堆排序
   * @param nums 待排序数组序列
   * @return 排好序的数组序列
   */
  private static int[] heapSort(int[] nums) {
  
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
      heapAdjust(nums, i, nums.length);
    }
    for (int i = nums.length - 1; i > 0; i--) {
      int temp = nums[i];
      nums[i] = nums[0];
      nums[0] = temp;
      heapAdjust(nums, 0, i);
    }
    return nums;
  }
  
  /**
   * 调整堆
   *
   * @param nums  待排序序列
   * @param parent   待调整根节点
   * @param length 数组序列长度
   */
  private static void heapAdjust(int[] nums, int parent, int length) {
    int temp = nums[parent];
    int childIndex = 2 * parent + 1;  //完全二叉树节点i从编号1开始的左子节点位置在2i，此处数组下标从0开始，即左子节点所在数组索引位置为：2i + 1
    while (childIndex < length) {
      if (childIndex + 1 < length && nums[childIndex] < nums[childIndex + 1]) {
        childIndex++;  //节点有右子节点，且右子节点大于左子节点，则选取右子节点
      }
      if (temp > nums[childIndex]) {
        break; //如果选中节点大于其子节点，直接返回
      }
      nums[parent] = nums[childIndex];
      parent = childIndex;
      childIndex = 2 * parent + 1;  //继续向下调整
    }
    nums[parent] = temp;
  }
}

Python3

#堆排序
def heap_sort(nums):

  for i in range(int(len(nums) / 2 - 1), -1, -1):
    heap_adjust(nums, i, len(nums))
  
  for i in range(len(nums) - 1, -1, -1):
    temp = nums[i]
    nums[i] = nums[0]
    nums[0] = temp
    heap_adjust(nums, 0, i)
  
  return nums

#调整堆
def heap_adjust(nums, parent, length):
  
  temp = nums[parent]
  childIndex = 2 * parent + 1
  while childIndex < length:
    if childIndex + 1 < length and nums[childIndex] < nums[childIndex + 1]:
      childIndex += 1
    if temp > nums[childIndex]:
      break
    nums[parent] = nums[childIndex]
    parent = childIndex
    childIndex = 2 * parent + 1
  
  nums[parent] = temp
    
nums = [53, 17, 78, 09, 45, 65, 87, 32]
nums = heap_sort(nums)
print(nums)

The above cliché about comparison sorting and heap sorting is all the content shared by the editor. I hope it can give you a reference, and I hope you will support Script Home.

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