Select sorting concept
Selection sorting is also an exchange sorting algorithm, which has a certain similarity to bubble sorting. Therefore, I personally believe that selecting sorting can be regarded as an improved algorithm for bubble sorting. Its idea is as follows:
Suppose that the array arr[] is now sorted, and it has n elements.
1 Compare the first element (in Java, subscript is 0) with the second element. If the former is greater than the latter, then it must be not the smallest, but we do not rush to swap like bubble sorting. We can set a temporary variable a to store the subscript of this currently smallest element. Then we continue to compare the smallest element with the third element. If it is still not the smallest, then we modify the value of a. In this way, until the comparison with the last element is completed, it is certain that a must be the subscript of the smallest element.
2. If the value of a is not 0 (the initial value, that is, the subscript of the first element), exchange the two elements with subscripts a and 0.
3. Repeat the above process, and start the comparison with the element with subscript 1 this time, because the smallest element has been placed at the position with subscript 0.
4. This way, until only the last element is left, you can be sure that this element is the largest.
5. Sorting is completed.
Obviously, this algorithm also requires n-1 rounds of sorting.
It should be noted that the above explanation is only the way to find the minimum value each time. In fact, you can also find the maximum value every time, but you need to put it on the tail of the array every time.
Java implementation code:
SelectArray.java
package ch02;public class SelectArray { // array private long[] arr; // size of valid data in array private int elems; // default constructor public SelectArray() { arr = new long[50]; } public SelectArray(int max) { arr = new long[max]; } // Insert data public void insert(long value) { arr[elems] = value; elems++; } // Display data public void display() { for (int i = 0; i < elems; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // Select sort public void selectSort(){ int min = 0; long tmp = 0L; for(int i = 0; i < elems -1; i++){ min = i; for(int j = i + 1; j < elems; j++) { if(arr[j] < arr[min]) { min = j; } } tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; } }}Test code:
package ch02;public class TestSelectArray { public static void main(String[] args) { SelectArray sArr = new SelectArray(); sArr.insert(89); sArr.insert(54); sArr.insert(667); sArr.insert(7); sArr.insert(12); sArr.insert(43); sArr.insert(12); sArr.display(); sArr.selectSort(); sArr.display(); }} result: