排序算法之插入排序

思路： 从数组下标为1的地方开始，从前往后遍历，每遍历到一个元素，都将它与它前面的所有元素比较，若有比它大的，则交换位置。 所以当遍历到i时，i左边的元素肯定是有序的了，只需把a[i]一次一次插入即可

代码实现

  public static void main(String[] args) {
        int[] array = {2, 3, -1, 5, 3, 2, 1, 3, 5, 1, 4, 5, 7, 9, -2};
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0 && array[j] < array[j - 1]; j--) { //一直遍历，直到遍历到第一个比 array[j] 小的元素则不遍历了(因为array[j]左边的元素都是有序的了)
                //进行交换
                array[j] = array[j] ^ array[j - 1];
                array[j - 1] = array[j] ^ array[j - 1];
                array[j] = array[j] ^ array[j - 1];
            }
        }
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i] + " ");
        }
    }
复制代码

运行结果

优化

可以在内循环中将较大的元素向右移动而不总是交换两个元素（这样访问数组的次数就能减半） 改进后的代码

 public static void main(String[] args) {
        int[] array = {2, 3, -1, 5, 3, 2, 1, 3, 5, 1, 4, 5, 7, 9, -2};
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i-1;
            for (; j >= 0 && temp < array[j]; j--) { //一直遍历，直到遍历到第一个比 array[j] 小的元素则不遍历了(因为array[j]左边的元素都是有序的了)
                array[j + 1] = array[j];
            }
            array[j+1] = temp; // temp值到达插入位置
        }
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }
复制代码

运行结果