插入排序过程中,序列分为已遍历部分和未遍历部分,已遍历序列有序,未遍历序列有序性未知,为了做到这一点,在每遍历每一个数时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);
            }
            // 当前元素是偶数,无须移动
        } 
    }