Selection sort

Scan for the smallest element and swap it into position 0. Scan the rest for the next smallest and swap it into position 1. Continue until the array is ordered.

public static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        if (min != i) {
            int tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }
}

Two details worth noticing. The outer loop stops at length - 1, because once everything else is placed the last element must already be correct. And the inner loop tracks the index of the minimum rather than its value, because you need the index to swap.

Cost

The inner loop runs n-1 times, then n-2, and so on: about n²/2 comparisons regardless of the input. That is O(n²).

Unusually, it does the same work on already-sorted data as on reversed data. There is no early exit, because it cannot know it has finished until it has looked.

What it does have is a low number of writes: at most n-1 swaps, one per outer pass. If comparisons are cheap and writes are expensive, flash memory being the standard example. That property occasionally matters.

Stability

Not stable as written. Swapping a distant element into place can jump it over an equal one and reverse their original order. A version that shifts rather than swaps is stable, at the cost of more writes.

Why it is taught

It is the easiest sort to trace by hand, and the invariant is easy to state: after pass i, the first i+1 elements are the smallest i+1 elements in order, and they never move again.

That is the whole value. For real work use Arrays.sort, which is O(n log n) and, for objects, stable. On a thousand elements selection sort does roughly half a million comparisons where a good sort does about ten thousand.

Insertion sort is a better simple sort. Same worst case, but nearly linear on almost-sorted data, which is why real implementations fall back to it for small ranges.