java data structure sorting algorithm (2) merge sort

This article mainly introduces the merge sort of Java data structure sorting algorithm. It analyzes the principles, implementation techniques and related precautions of merge sort in detail based on specific examples. Friends in need can refer to this article

The example describes the merge sort of Java data structure sorting algorithm. Share it with everyone for your reference, the details are as follows:

The sorts of sorting mentioned above all arrange a group of records into an orderly sequence according to the size of the keywords, and the idea of ​​merge sorting is: based on Merge, merge two or more ordered lists into a new ordered list

Merge sort algorithm:Assume that the initial sequence contains n records, First, treat these n records as n ordered subsequences, each subsequence has a length of 1, and then merge them in pairs to get n/2 lengths of 2 (when n is an odd number, the length of the last sequence is 1 ) ordered subsequence. On this basis, the ordered subsequences of length 2 are then merged brightly to obtain several ordered subsequences of length 4. Repeat this until an ordered sequence of length n is obtained. This method is called: 2-way merge sort (the basic operation is to merge two adjacent ordered subsequences in the sequence to be sorted into an ordered sequence).

Algorithm implementation code is as follows:

package exp_sort;
public class MergeSort {
  /**
   * 相邻两个有序子序列的合并算法
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void Merge(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    int i, j, k;
    mid = (low + high) / 2;
    i = low;
    k = 0;
    j = mid + 1;
    // compare two list
    while (i <= mid && j <= high) {
      if (src_array[i] <= src_array[j]) {
        des_array[k] = src_array[i];
        i = i + 1;
      } else {
        des_array[k] = src_array[j];
        j = j + 1;
      }
      k = k + 1;
    }
    // if 1 have,cat
    while (i <= mid) {
      des_array[k] = src_array[i];
      k = k + 1;
      i = i + 1;
    }
    while (j <= high) {
      des_array[k] = src_array[j];
      k = k + 1;
      j = j + 1;
    }
    for (i = 0; i < k; i++) {
      src_array[low + i] = des_array[i];
    }
  }
  /**
   * 2-路归并排序算法，递归实现
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void mergeSort(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    if (low < high) {
      mid = (low + high) / 2;
      mergeSort(src_array, low, mid, des_array);
      mergeSort(src_array, mid + 1, high, des_array);
      Merge(src_array, low, high, des_array);
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array1[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    int array2[] = new int[array1.length];
    mergeSort(array1, 0, array1.length - 1, array2);
    System.out.println("\n----------after sort-------------");
    for (int ii = 0; ii < array1.length; ii++) {
      System.out.print(array1[ii] + " ");
    }
    System.out.println("\n");
  }
}

Code explanation:

In merge sort, a merge requires multiple calls to the 2-way merge algorithm. The time complexity of a merge is O(n). The time to merge two sorted tables is obviously linear, because at most n-1 comparisons are made, where n is the total number of elements. If there are multiple numbers, that is, when n is not 1, recursively merge and sort the first half of the data and the second half of the data to obtain the two parts of sorted data, and then merge them together.

Algorithm analysis:

This algorithm is based on the merge operation (also called the merge algorithm, which refers to the process of combining two sorted sequences An efficient sorting algorithm based on the operation of merging into a sequence). This algorithm is a very typical application of the divide and conquer method (pide and Conquer). It divides the problem into some small problems and then solves them recursively, and the conquering stage is solved by dividing the divided stage. Each answer fits together; divide and conquer is a very powerful use of recursion. Note: Compared with quick sort and heap sort, the biggest feature of merge sort is that it is a stable sorting method. The speed is second only to quick sort, and it is generally used for arrays that are generally disordered but whose sub-items are relatively ordered.

Complexity:

Time complexity is: O(nlogn)——This algorithm is the best and most efficient Bad and average time performance.
The space complexity is: O(n)
The number of comparison operations is between (nlogn) / 2 and nlogn - n + 1.
The number of assignment operations is (2nlogn). The space complexity of the merge algorithm is: 0 (n)
It is difficult to use in main memory sorting (merge sort takes up more memory. The main problem is that merging two sorted tables requires linear additional memory, which also costs money in the entire algorithm. Some additional operations such as copying data to a temporary array and then copying it back will seriously slow down the sorting speed) but it is very efficient and is mainly used for external sorting and for important internal sorting applications. , generally choose quick sort.

The steps for the merge operation are as follows:

Step 1: Apply for space so that its size is the sum of the two sorted sequences. The space is used to store the merged sequence
Step 2: Set two pointers, the initial positions are the starting positions of the two sorted sequences
Step 3: Compare the elements pointed to by the two pointers, Select a relatively small element and put it into the merge space, and move the pointer to the next position
Repeat step 3 until a certain pointer reaches the end of the sequence
Copy all the remaining elements of the other sequence directly to the end of the merge sequence

The steps of merge sorting are as follows (assuming that the sequence has n elements in total):

merge every two adjacent numbers in the sequence (merge ), forming floor(n/2) sequences, each sequence contains two elements after sorting
Merge the above sequences again, forming floor(n/4) sequences, each sequence contains four elements
Repeat step 2 until all elements are sorted

[Related recommendations]

1. Java data structure sorting algorithm (1) Tree selection sort

2. Detailed explanation of the example tutorial of Selection Sort_java in Java

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 (2) merge sort. For more information, please follow other related articles on the PHP Chinese website!