Detailed explanation of examples of implementation of insertion sort in java

This article mainly introduces the insertion sort of java data structure and algorithm, and analyzes the concept, classification, principle, implementation method and related precautions of java insertion sort in the form of examples. Friends in need can refer to it

The examples in this article describe insertion sorting of java data structures and algorithms. I share it with you for your reference. The details are as follows:

After reviewing, I sorted out the knowledge about sorting in the data structure. I wrote it down because I want to share it with more people. The most important thing is Just make a backup for future reference.

Sort

1. Concept:

A sequence with n records {R1, R2,.......,Rn} (note here: 1,2,n are the sequences in the table below, and the following have the same effect), and the sequence of the corresponding keywords is {K1,K2,.... .....,Kn}. Through sorting, it is required to find an arrangement p1, p2,...pn of the current subscript sequence 1,2,...,n, so that the corresponding keyword satisfies the following non-decreasing ( Non-increasing) relationship, that is: Kp1<=Kp2<=Kpn, thus obtaining a sequence of records ordered by keyword: {Rp1, Rp2,.....,Rpn}.

2. Classification

Sorting can be divided into two categories based on the difference in memory occupied by data during sorting.

Internal sorting: The entire sorting process is completely performed in memory, as follows:

Insertion sorting (direct insertion sorting, half insertion sorting, Hill sorting );

Exchange class sorting (Bubble sort, quick sort);

Selection class sorting (simpleSelection sort, tree selection sort, heap sort);

Merge sort;

Allocation class sort (multi-key Sequence table implementation of word sort, chained radix sort, and radix sort));

External sorting: Because the amount of data to be sorted is too large, the memory cannot accommodate all the data. Sorting requires the use of external storage devices (disk sorting, tape sorting).

3. Stability

Assume that there are multiple records with the same keyword in the sequence to be sorted. Assume Ki=Kj(1<=i<=n,1<=j<=n,i != j), if Ri leads Rj (i.e. i<=j) in the sequence before sorting, we get after sorting If Ri still leads Rj in the sequence, the sorting method used is said to be stable; conversely, when the leading relationship of the same keyword changes during the sorting process, the sorting method used is unstable.

Insertion sort:

Idea: Each time a record to be sorted is inserted into the appropriate position in the previously sorted sub-file according to its key size until all records are inserted. until completed.

Direct insertion sorting:

Algorithm idea: Assume that the records to be sorted are stored in the arrayR[1.. n] in. Initially, R[1] forms an ordered area, and the unordered area is R[2..n]. From i=2 until i=n, ​​R[i] is inserted into the current ordered area R[1..i-1] in sequence, generating an ordered area containing n records.

The code implemented in java is as follows:

package exp_sort;
public class DirectInsertSort {
  public static void DircstSort(int array[]) {
    int j;
    // 循环从第二个数开始，第一个数用做存放待插入的记录
    for (int i = 1; i < array.length; i++) {
      int temp = array[i];
      // 寻找插入位置
      for (j = i; j > 0 && temp < array[j - 1]; j--) {
        array[j] = array[j - 1];
      }
      // 将待插入记录插入到已经排序的序列中
      array[j] = temp;
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    DircstSort(array);
  }
}

Algorithm analysis: The best situation is that the record to be sorted itself has been sorted according to the key The words are arranged in order. The worst case is that the records to be sorted are arranged in reverse order according to the keywords; The time complexity is O(N^2) and the space complexity is O(1); This algorithm is a stable sorting algorithm: It is more suitable for situations where the number of records to be sorted is small and basically in order.

Half Insertion Sort:

Algorithm idea: The performance of halved search for ordered tables is better than sequential search.

The algorithm implementation code is as follows:

package exp_sort;
public class BinaryInsertSort {
  public static void sort(int array[]) {
    int temp, low, mid, high;
    for (int i = 1; i < array.length; i++) {
      temp = array[i];
      low = 0;
      high = i -1;
      //确定插入位置
      while (low <= high) {
        mid = (low + high) / 2;
        if (temp < array[mid]) {
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      //记录依次向后移动
      for (int j = i; j >= low + 1; j--) {
        array[j] = array[j-1];
      }
      //插入记录
      array[low] = temp;
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = {38, 62, 35, 77, 55, 14, 35, 98};
    sort(array);
  }
}

Algorithm analysis: is a stable sorting algorithm, which is significantly less expensive than the direct insertion algorithm The number of comparisons between keywords is reduced, so the speed is faster than the direct insertion sort algorithm , but the number of record moves has not changed, so the time complexity of the half insertion sort algorithm is still O (n^2), is the same as the direct insertion sort algorithm. Additional space O(1).

【Related recommendations】

1. Special recommendation:"php "Programmer's Toolbox" V0.1 version download

2. Java Free Video Tutorial

##3. YMP Online Manual

The above is the detailed content of Detailed explanation of examples of implementation of insertion sort in java. For more information, please follow other related articles on the PHP Chinese website!