Sort Integers

题目：

Given an integer array, sort it in ascending order. Use selection sort, bubble sort, insertion sort or any O(n2) algorithm.

分析：

感觉这几乎是n^2解法的3种不同的描述方式...

解法：selection sort 就是标准的枚举方法，每次从i+1到end中找到最小元素，并且和i交换

public class Solution {
    public void sortIntegers(int[] A) {
        for (int i = 0; i < A.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < A.length; j++) {
                if (A[j] < A[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = A[i];
            A[i] = A[minIndex];
            A[minIndex] = temp;
        }
    }
}

解法：bubble sort 就是相邻的元素，如果A[i-1] > A[i]就两两互换，这样最大的会换到最后一位。一直到整一遍没有发生互换才跳出。这个解法还可以优化，因为每走一遍，最后一位的元素就固定了。每一遍都可以比上一遍少走一个元素，虽然还是O(n^2)，但是略微快一点

public class Solution {
    public void sortIntegers(int[] A) {
        boolean isSorted = false; //(第一个优化)
        int n = 0; //(第二个优化)
        while (!isSorted) {
            isSorted = true;
            for (int i = 1; i < A.length - n; i++) {
                if (A[i - 1] > A[i]) {
                    isSorted = false;
                    int temp = A[i - 1];
                    A[i - 1] = A[i];
                    A[i] = temp;
                }
            }
            n++;
        }
    }
}

解法：insertion sort 就是通过选出来一个element，插到他应该在的位置，维持前i个有序

public class Solution {
    public void sortIntegers(int[] A) {
        for (int i = 1; i < A.length; i++) {
            int j = i;
            while (j > 0 && A[j - 1] > A[j]) {
                int temp = A[j - 1];
                A[j - 1] = A[j];
                A[j] = temp;
                j--;
            }
        }
    }
}