a) Principle : Each time, select the smallest element from the records to be sorted, and place it in the order at the end of the sorted sequence until all records are sorted. That is, each trip is selected as the i-th record in the ordered sequence among n-i+1 (i=1, 2, ...n-1) records. The algorithms based on this idea mainly include simple selection sorting, tree selection sorting and heap sorting. (This is a common simple selection sorting only)
b) The basic idea of simple selection of sorting : Given an array: int[]arr={n data in it}; the first time sorting, select the smallest data in the data to be sorted arr[1]~arr[n], and exchange it with arr[1]; the second time, select the smallest data in the data to be sorted arr[2]~arr[n], and exchange it with r[2]; and so on, select the smallest data in the data to be sorted arr[i]~arr[n], and exchange it with r[i] until all sorting is completed.
c) Example : array int[]arr={5,2,8,4,9,1};
-------------------------------------------------------
First order: Original data: 528491
Minimum data 1, put 1 first, that is, 1 and 5 interchange positions,
Sort result: 128495
-------------------------------------------------------
Second order:
The data outside 1 {28495} is compared, 2 is the smallest,
Sort result: 128495
-------------------------------------------------------
The third order:
Data other than 1 and 2 are compared {8495}, 4 is minimal, 8 and 4 are exchanged
Sort result: 124895
-------------------------------------------------------
The fourth order:
Other data other than 1, 2, 4 are compared {895}, 5 is minimum, 8 and 5 are exchanged
Sort result: 124598
-------------------------------------------------------
The fifth order:
Other data other than 1, 2, 4, 5 are compared, 8 is minimal, 8 and 9 are exchanged
Sort result: 124589
-------------------------------------------------------
Note: The method to get the smallest number in each order: for loop to compare, define a third variable temp. First, compare the first two numbers, put the smaller number in temp, and then use temp to compare with the remaining data. If data smaller than temp appears, use it instead of the original data in temp. For details, referring to the code examples below, I believe you have learned the for loop statement before learning to sort. In this way, it will be particularly easy to understand here.
Code example:
//Select sort public class SelectionSort { public static void main(String[] args) { int[] arr={1,3,2,45,65,33,12}; System.out.println("Before exchange:"); for(int num:arr){ System.out.print(num+" "); } //Select the optimization of sorting for(int i = 0; i < arr.length - 1; i++) {//Sort the i-th order int k = i; for(int j = k + 1; j < arr.length; j++){//Select the smallest record if(arr[j] < arr[k]){ k = j; //Note the location of the minimum value found so far} } //After the end of the inner loop, that is, after finding the minimum number of this loop, then exchange if(i != k){ //Swap a[i] and a[k] int temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; } } System.out.println(); System.out.println("After swap:"); for(int num:arr){ System.out.print(num+" "); } }}Screenshot of the running result:
Select the time complexity of sorting: The number of comparisons of simple selection sorts has nothing to do with the initial sorting of the sequence. Assuming that the sequence to be sorted has N elements, the number of comparisons will always be N(N-1)/2. The number of movements is related to the initial sorting of the sequence. When the sequence is positive, the number of movements is the least, which is 0. When the sequence is inversely sequenced, the most movements are 3N(N-1)/2.
So, in summary, the time complexity of simple sorting is O(N2).