Java data structure sorting algorithm (3) simple selection sort

This article mainly introduces the simplicity of java data structure and algorithmselection sorting, and analyzes the principles, implementation methods and related operation techniques of selection sorting in the form of examples. Friends in need can refer to the following

The examples in this article describe simple selection sorting of java data structures and algorithms. Share it with everyone for your reference. The details are as follows:

In the previous article, we have already described the sorting algorithm of the exchange class. In this section, we will start to talk about the sorting algorithm of the selection class. First, let’s take a look at the selection sorting algorithm. Algorithmic thought;

The basic algorithmic thought of selection sorting:

Each trip is in n-i+1 (i=1,2, Select the record with the smallest keyword among 3,...,n-1) records as the i-th record in the ordered sequence.

Simple selection sorting:

Suppose the number of records in the sorted sequence is n. i takes 1,2,…,n-1, find the record with the smallest sorting code from all n-i+1 records (Ri, Ri+1,…,Rn), and exchange it with the i-th record. After executing n-1 times, the sorting of the record sequence is completed.

The algorithm implementation code is as follows:

package exp_sort;
public class SimpleSelectSort {
  static int i;
  static int temp;
  public static void selectSort(int array[]) {
    for (i = 0; i < array.length; i++) {
      int k = i;  //记录当前位置
      for (int j = i + 1; j < array.length; j++) {
        if (array[j] < array[k]) {   //找出最小的数，并用k指向最小数的位置
          k = j;
        }
      }
            //交换最小数array[k]与第i位上的数
      if (k != i) {
        temp = array[i];
        array[i] = array[k];
        array[k] = temp;
      }
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    selectSort(array);
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
}

Algorithm analysis:

In this sorting process, the number of times records need to be moved a bit less. In the best case, that is, the initial state of the records to be sorted is already in positive order, there is no need to move the records; in the worst case, that is, the initial state of the records to be sorted is in reverse order, the maximum number of moves required is: 3 ( n-1). The number of comparisons required during the sorting process has nothing to do with the arrangement of the record sequence to be sorted in the initial state. When i=1, n-1 comparisons are required; when i=n, ​​the total number of comparisons required is: n(n-1)/2, that is, the time complexity of the comparison operation is: O(n^ 2), the time complexity of moving operation is O(n); this sorting is unstable sorting.

[Related recommendations]

1. java data structure sorting algorithm (1) tree selection sort

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

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

4. java data structure Sorting algorithm (4) Selection sort

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