package com.matao.sorting;

import java.util.Arrays;

/**
 * Created by matao on 8/13/16.
 * 选择排序法:
 * 对于长度为N的数组,选择排序需要大约 pow(N, 2)/2 的比较
 * 以及 N 次交换
 * 不稳定排序
 */
public class SelectionSort extends BaseSort {

    @Override
    public void sort(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < a.length; j++) {
                if (lessThan(a[j], a[minIndex])) {
                    minIndex = j;
                }
            }
            exchange(a, i, minIndex);
        }
    }

    public static void main(String[] args) {
        SelectionSort selectionSort = new SelectionSort();

        Integer[] a = {2, 1, 5, 7, 0, 10};
        selectionSort.sort(a);
        System.out.println(Arrays.toString(a));

        Integer[] b = {1, 1, 0, 3, -1};
        selectionSort.sort(b);
        System.out.println(Arrays.toString(b));
    }
}

@@ -90,73 +90,501 @@
 %0A * 
-%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%E6%B3%95:%0A * %E5%AF%B9%E4%BA%8E%E9%95%BF%E5%BA%A6%E4%B8%BAN%E7%9A%84%E6%95%B0%E7%BB%84,%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%E9%9C%80%E8%A6%81%E5%A4%A7%E7%BA%A6 pow(N, 2)/2 %E7%9A%84%E6%AF%94%E8%BE%83%0A * %E4%BB%A5%E5%8F%8A N %E6%AC%A1%E4%BA%A4%E6%8D%A2%0A * %E4%B8%8D%E7%A8%B3%E5%AE%9A%E6%8E%92%E5%BA%8F
+%3Cpre%3E%0A * Selection Sort%0A *%0A * 1) Find the smallest item in the array and exchange it with the first entry%0A *    (itself if the first entry is already the smallest).%0A * 2) Then, find the next smallest item and exchange it with the second entry.%0A * 3) Continue in this way until the entire array is sorted.%0A *%0A * for each i from 0 to N-1, there is 1 exchange, so the totals are N exchanges.%0A * and the total compares is (N-1) + (N-2) + ... + 2 + 1 + 0 = N(N-1)/ ~ pow(N, 2)/2 compares.%0A * %3C/pre%3E
 %0A */
@@ -1163,16 +1163,71 @@
 ort(a);%0A
+        System.out.println(selectionSort.isSorted(a));%0A
         
@@ -1307,16 +1307,16 @@
 3, -1%7D;%0A
-
         
@@ -1338,16 +1338,71 @@
 ort(b);%0A
+        System.out.println(selectionSort.isSorted(b));%0A
         

add comments and improve test output