10年IT老兵重学数据结构与算法（二）

书接上回，还是从排序算法说起，说下O（n^2）时间复杂度的排序，如插入排序，选择排序

具体如下：加入有数组 3,2,1,5,4；需要针对该数组正序排序，数组长度为5，一共需要经过5轮。

第0轮，无需比较

第一轮，取出2，和3比较，比3小，和3交换位置，变为2,3,1,5,4

第二轮，取出1，以此和3，和2比较，均需交换位置，该轮比较两次，比较后结果为1,2,3,5,4

第三轮，取出5,改数字比前面的都大，无需移动

第四轮，取出4，比5小，需要移动，继续往前移动，比3大，终止，无需比较，

最后结果为12345

关键代码如下：

public class TestSort {


    public static void insertSort(int[] a, int n) {


        for (int i = 0; i < n; i++) {

            for (int j = i; j > 0; j--) {
                if (a[j] < a[j - 1]) {
                    swap(a, j, j - 1);
                }else{
                    break;
                }
            }
        }
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 2, 1, 5, 4};
        System.out.println("第一趟排序后:" + Arrays.toString(array));

        insertSort(array, array.length);
        System.out.println("排序后:" + Arrays.toString(array));

    }
}