Java data structure sorting algorithm (1) Tree selection sorting

This article mainly introduces the tree shape of java data structure sorting algorithmselection sorting, combined with specific examples to analyze the principles, implementation skills and related precautions of java tree selection sorting, friends in need You can refer to the following

The example of this article describes the tree selection sorting algorithm of java data structure. Share it with everyone for your reference, the details are as follows:

Here we will talk about the sorting of one of the selection types: tree selection sorting

In simple selection sorting, each comparison The results of the last comparison are not used, so the time complexity of the comparison operation is O(N^2). If you want to reduce the number of comparisons, you need to save the size relationship during the comparison process. Tree selection sort is an improvement over simple selection sort.

Tree selection sorting: Also known as Tournament Sort), is a sorting based on the championship Think about the method of selection sorting. First perform a pairwise comparison of the keywords of n records, and then perform a pairwise comparison between the n/2 smaller ones, and repeat this until the smallest record is selected.

Algorithm implementation code is as follows:

package exp_sort;
public class TreeSelectSort {
 public static int[] TreeSelectionSort(int[] mData) {
  int TreeLong = mData.length * 4;
  int MinValue = -10000;
  int[] tree = new int[TreeLong]; // 树的大小
  int baseSize;
  int i;
  int n = mData.length;
  int max;
  int maxIndex;
  int treeSize;
  baseSize = 1;
  while (baseSize < n) {
   baseSize *= 2;
  }
  treeSize = baseSize * 2 - 1;
  for (i = 0; i < n; i++) {
   tree[treeSize - i] = mData[i];
  }
  for (; i < baseSize; i++) {
   tree[treeSize - i] = MinValue;
  }
  // 构造一棵树
  for (i = treeSize; i > 1; i -= 2) {
   tree[i / 2] = (tree[i] > tree[i - 1] ? tree[i] : tree[i - 1]);
  }
  n -= 1;
  while (n != -1) {
   max = tree[1];
   mData[n--] = max;
   maxIndex = treeSize;
   while (tree[maxIndex] != max) {
    maxIndex--;
   }
   tree[maxIndex] = MinValue;
   while (maxIndex > 1) {
    if (maxIndex % 2 == 0) {
     tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + 1] ? tree[maxIndex]
       : tree[maxIndex + 1]);
    } else {
     tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] ? tree[maxIndex]
       : tree[maxIndex - 1]);
    }
    maxIndex /= 2;
   }
  }
  return mData;
 }
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
  TreeSelectionSort(array);
  for (int i = 0; i < array.length; i++) {
   System.out.print(array[i] + " ");
  }
  System.out.println("\n");
 }
}

Algorithm analysis:

In tree selection sorting, except for the smallest keyword, the selected smallest keyword all goes through a comparison process from leaf nodes to follow nodes. Since the depth of a complete binary tree containing n leaf nodes is log2n +1, therefore in tree selection sorting, each time a smaller keyword is selected, log2n comparisons are required, so the time complexity is O(nlog2n), and the number of moving records does not exceed the number of comparisons, so the total algorithm time is complex The degree is O(nlog2n). Compared with the simple selection sort algorithm, it reduces the number of comparisons by an order of magnitude and adds n-1 additional storage space to store intermediate comparison results.

Supplement:

Here we introduce the improved algorithm for tree selection sorting, namely the heap sorting algorithm.

Heap sorting makes up for the shortcoming of the tree selection sorting algorithm that takes up a lot of space. When using heap sort, only one record-sized auxiliary space is required.

The algorithm idea is:

Store the keywords of the records to be sorted in the array r[1...n], and r It is regarded as a sequential representation of a complete binary tree. Each node represents a record. The first record r[1] is used as the root of the binary tree. Each of the following records r[2...n] is layered from left to layer. Arranged in right order, the left child of any node r[i] is r[2*i], the right child is r[2*i+1]; the parent is r[[i/2]].

Heap definition: The key value of each node satisfies the following conditions:

r[i].key >= r[2i].key and r[ i].key >= r[2i+1].key (i=1,2,...[i/2])

The complete binary tree that meets the above conditions is called a large root heap; on the contrary, if The key of any node in this complete binary tree is less than or equal to the key of its left child and right child, and the corresponding heap is called a small root heap.

The process of heap sorting mainly needs to solve two problems: the first is to build an initial heap according to the heap definition; the second is to rebuild the heap after removing the largest element to obtain the sub-large element.

Heap sorting is to use the characteristics of the heap to sort the record sequence. The process is as follows:

1. Build a heap for the given sequence;
2. Output the top of the heap; (first element Exchange with the tail element)
3. Rebuild the heap with the remaining elements; (filter the first element)
4. Repeat steps 2 and 3 until all elements are output.

Note: "Filtering" must start from the [n/2]th node and go backwards layer by layer until the root node.

Algorithm analysis:

1. For a heap with a depth of k, the number of keyword comparisons required for "filtering" is at most 2(k-1) ;
2. The heap depth of n keywords is [log2n]+1, and the number of keyword comparisons required to initially build the heap is at most: n* [log2n];
3. Rebuild the heap n- 1 time, the number of keyword comparisons required does not exceed: (n-1)*2 [log2n];

Therefore, in the worst case, the time complexity of heap sort is O(nlog2n ), this is the biggest advantage of heap sort.

[Related recommendations]

1. Detailed tutorial on selection sorting (Selection Sort_java) in Java

2. java data structure Sorting algorithm (2) Merge sort

3. java data structure sorting algorithm (3) Simple selection sort

4. java data structure sorting Algorithm (4) Selection sort

The above is the detailed content of Java data structure sorting algorithm (1) Tree selection sorting. For more information, please follow other related articles on the PHP Chinese website!