Selection Sort

O algoritmo é baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o segundo menor valor para a segunda posição e assim sucessivamente, até os últimos dois elementos.

Como tudo funciona

Mãos a obra:

     
    import java.util.ArrayList;
    import java.util.Random;
    import java.util.Scanner;

    public class SelectionSort {

        public static void main(String[] args) {
            Scanner leia = new Scanner(System.in);
            ArrayList lista = new ArrayList<>();
            int cont = 1;

            for (int i = 0; i < 1000; i++) {
                Random rand = new Random();
                int n = rand.nextInt(1000);
                lista.add(n);
            }

            SelectionSort(lista);

            for (Integer integer : lista) {
                System.out.print(integer + ", ");
                if (cont % 20 == 0) {
                    System.out.println();
                }
                cont++;
            }
        }

        /* ---------------------- Algoritimo De Ordenação ---------------------- */

        public static void SelectionSort(ArrayList lista) {
            for (int i = 0; i < lista.size(); i++) {
                int min = i;
                for (int j = i + 1; j < lista.size(); j++) {
                    if (lista.get(j) < lista.get(min)) {
                        min = j;
                    }
                }
                Integer aux = lista.get(i);
                lista.set(i, lista.get(min));
                lista.set(min, aux);
            }
        }
    }

Tempo de execução(em segundos) VS Qtd de nº no Array:

Selection Sort	1.000	10.000	500.000	1.000.000
Bom	0.0395172	0.1438769	271.8567817	1282.1676655
Médio	0.0345794	0.3685115	2411.6839104	6749.7445372
Ruim	0.0021276	0.1964097	543.8211861	2284.7899298

*A tabela representa a quantidade de numros utilizadas e o tempo de execução o processo de ordenação