插入排序

插入排序过程中，序列分为已遍历部分和未遍历部分，已遍历序列有序，未遍历序列有序性未知，为了做到这一点，在每遍历每一个数时O(n)，依次在已遍历序列中从后往前比较O(n)，将当前数放入适当位置，直至未遍历部分为空O(n ^ 2)。相当于摸牌将牌组分为，手中的牌和牌组中的牌，手中的牌有序，牌组中的牌有序性未知，每摸一张牌将其插入合适位置，直至牌组为空。

一、插入排序

1、插入排序的实现

public static void insertSort(int[] arr, int start, int end) {
        for (int i = 1; i < arr.length; i++) {
            int value = arr[i];
            int cur = i;
            while (cur > 0 && value < arr[cur - 1]) {
                arr[cur] = arr[cur - 1];
                cur--;
            }
            arr[cur] = value;
        }
    }

2、源码

二、剑指offer[21]

调整数组顺序使奇数位于偶数前面 题解

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变

这道题就是将数组分为奇数部分和偶数部分，每遍历到一个奇数，就迭代地将其放入前面奇数部分，每遍历到一个偶数，就继续遍历。相当于任意奇数都小于任意偶数，所有奇数都相等，所有偶数都相等，然后使用快速排序排序数组。

public void reOrderArray(int [] array) {
        if (array == null || array.length < 2) {
            return;
        }
        int n = array.length;
        for (int i = 1; i < n; i++) {
            // 当前元素是奇数，就移动到奇数序列
            if (array[i] % 2 != 0) {
                int value = array[i];
                int cur = i;
                while (cur > 0 && (array[cur - 1] % 2 == 0)) {
                    array[cur] = array[cur - 1];
                    cur--;
                }
                array[cur] = value;
            }
            // 当前元素是偶数，无须移动
        }
    }

若本题不要求保证奇数与奇数之间，偶数与偶数之间保持原来的顺序，可以用快排的partition的思想，将数组分为奇数部分和偶数部分进行排序。

public void reOrderArray(int [] array) {
        int uneven = -1;
        for (int i = 0; i < array.length; i++) {
            // 当前元素是奇数，就移动到奇数序列
            if (array[i] % 2 != 0) {
                swap(array, ++uneven, i);
            }
            // 当前元素是偶数，无须移动
        } 
    }