Introduction to the

Selection sort is a simple and intuitive sorting algorithm. It works by first picking the smallest (or largest) element from the data elements to be sorted, storing it at the beginning of the sequence, then finding the smallest (or largest) element from the remaining unsorted elements, and placing it at the end of the sorted sequence. And so on until the total number of data elements to be sorted is zero. Selection sort is an unstable sort method.

Time complexity

O(n^2)

Thought analysis

Order: From smallest to largest

First, find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence. Then, continue to find the smallest (large) element from the remaining unsorted elements and place it at the end of the sorted sequence. And so on until all the elements are sorted.

Comparison process:

Code implementation

public class SelectionSort {

    public static void main(String[] args) {
        int[] arr = {66.1.5.3.60.34.79.6};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void selectionSort(int[] arr) {
        // Minimum index
        int minIndex;
        / / the minimum
        int minVal;
        for (int i = 0; i < arr.length - 1; i++) {
            // assume I is the minimum index
            minIndex = i;
            // Assume arr[I] is the minimum
            minVal = arr[i];
            // Loop to find the smallest value
            for (int k = i + 1; k < arr.length; k++) {
                // If it encounters a value less than the minimum value, it assigns a smaller value
                if(minVal > arr[k]) { minIndex = k; minVal = arr[k]; }}// If minIndex== I, no smaller value is encountered, so no assignment is required.
            // Otherwise swap the smallest value with the current value
            if(minIndex ! = i) { arr[minIndex] = arr[i]; arr[i] = minVal; }}}}Copy the code

Run output:

[1, 3, 5, 6, 34, 60, 66, 79]

conclusion

The core of the algorithm is to assume that the current element is the minimum value each time, and then compare with the following elements one by one. If there are smaller elements, set the smaller element to the minimum value, and finally swap places. All elements are sorted when the loop is complete.