Selection Sort

Selection Sort
1. Chọn một phần từ lớn nhất trong n phần tử: a[0], a[1], ..., a[n-1], sau đó hoán vị với phần tử a[0].
2. Chọn phần tử lớn nhất trong n - 1 phần tử từ: a[1], a[2], ..., a[n-1], sau đó hoán vị với phẩn tử a[1].
3. Tổng quát: Ta thấy ở lần thứ i, ta sẽ tìm phần tử lớn nhất trong n - i phần tử từ: a, a[i+1],...,a[n-1], sau đó hoán vị no với a.

Ta có chương trình minh họa:

public class SelectionSort {

    // Sort by descending
    public static void sort(int[] array) {

        for (int i = 0; i < array.length; i++) {
            int max = array[i]; // Lưu phần tử lớn nhất
            int index = i; // lưu vị trí chứa phần tử lớn nhất
            for (int j = i + 1; j < array.length; j++) {
                if(max < array[j]){
                    max = array[j];
                    index = j;
                }
            }
            // Nếu chỉ số đã thay đổi, ta sẽ hoán vị
            if(index != i){
                int temp = array[i];
                array[i] = array[index];
                array[index] = temp;
            }
        }

    }
}