图书馆排序

十大经典排序算法

在前面我们讲插入排序的时候，需要把待插入位置之后的所有元素都往后挪，等空出位置之后，在把当前元素插入到该位置。而图书馆排序（Library Sort）是对插入排序的改进版，他在每个元素之间都预留了一些的空的位置，以便在插入过程中向后移动元素的时候可以减少移动的次数。

假设一名图书管理员在一个长架上按字母顺序来整理书，从左边A开头的书，一直到右边Z开头的书，书本之间没有空格。如果图书管理员有一本开头为B的新书，当他找到了这本书在B区中的正确位置，他将不得不把从该位置后一直到Z的每一本书向右移动，就只是为了腾出空位放置这本新书。这就是插入排序的原理。但是，如果他在每一字母区后留有额外的空间，只要在B区之后还有空间，他插入书时就只需要移动少数几本书，而不会移动后面所有的书，这是图书馆排序的原理。–来自维基百科

至于预留的空间有多大，可以自己确定，我们假设每个数字后面添加 2 个空格，来看下图书馆排序的步骤。

private void librarySort(int[] nums) {
    int gap = 2;// 每个数字后面空格的数量，可以自己定义。
    int len1 = nums.length;// 原数组的长度
    int len2 = (gap + 1) * len1;// 添加空格之后的数组长度
    int[] newNums = new int[len2];// 新数组
    boolean[] isDigit = new boolean[len2];// 记录哪些是数字哪些是空格。
    while (len1 > 0) {// 初始化新数组值。
        len2 -= gap;
        newNums[--len2] = nums[--len1];
        isDigit[len2] = true;// 标记为数字
    }
    int end = isDigit.length - gap + 1;// 新数组中最后一个有效数字的下标
    for (int i = 1; i < end; i++) {
        if (!isDigit[i])// 如果是空格就跳过。
            continue;
        // 从前往后查找当前数字应该插入的位置。
        for (int j = 0; j < i; j++) {
            if (!isDigit[i] || newNums[j] <= newNums[i])
                continue;
            // tmp是待插入的值，先找到他要插入的位置，然后在插入。
            int tmp = newNums[i];
            // newNums[j]是比tmp大的，先判断他前面有没有空格，如果有就直接插入。
            if (j != 0 && !isDigit[j - 1]) {
                isDigit[j - 1] = true;
                newNums[j - 1] = tmp;
                isDigit[i] = false;
                break;
            }
            // 往后挪，空出需要插入的位置。
            for (int k = i; k > j; k--) {
                newNums[k] = newNums[k - 1];
                isDigit[k] = isDigit[k - 1];
            }
            // 把数字tmp插进去。
            newNums[j] = tmp;
            isDigit[j] = true;
            break;
        }
    }
    // 把新数组中的值取出，放到原数组中。
    int index = 0;
    for (int i = 0; i <= end; i++) {
        if (isDigit[i])
            nums[index++] = newNums[i];
    }
}

往前查找插入位置的时候，是从前往后一个个查找的，实际上这种效率不是很高，既然前面都是有序的了，我们可以使用二分法进行查找，这个大家可以尝试着写下。

相关链接