[Elementary-Algorythms/5]插入排序的进化

这节作者讲了最简单的排序算法－插入排序，以及排序算法的改进。也分改进一、改进二和最终改进，但是由于整节都比较简单，就记录在一篇文章中，不分开记录了。代码中涉及到简单的递归、二分查找、链表和上节学的二叉搜索树。作者细讲的内容就不贴出来了，主要是把写的代码贴出来讲下。

---

其中两个头文件和实现文件可在这看到wtlSet.h/wtlBSTree.h。

/* * File: wtlInsertionSort.c * Author: WangTaL * Copyright: 5/21/2018 */
#include <stdio.h>
#include "wtlSet.h"
#include "wtlBSTree.h"

// 二分查找，迭代版。从含有ｎ个元素的数组ａ中查找元素ｘ的下标
int wtlBinarySearch_Iteration(int* a, int n, int x){
    // 0　... n,l和u分别表示当前所在数组下标的最低位和最高位
    int l = 0;
    int u = n;

    // 排好序的数组可以用二分法查找元素
    while (l < u) {
        // 二分查找就是每次都和中间元素对比，这样每次都可以排除一半元素
        int m = (l + u) / 2;

        // 相等，则表示m就是x在a中的下标
        if (a[m] == x) {
            return m;
        } else if (a[m] < x) {　// x要大，则继续在右半边找，左半边排除了
            l = m + 1;　// 此时，右半边这个数组的最低位和最高位下标分别是m+1和u
        } else { // x要小，在左半边找，右半边排除
            u = m;　// 此时，左半边这个数组的最低位和最高位下标分别是l和m
        }
    }

    // 注意，这个函数只能查找存在与a中的x。没有处理不存在的情况
    return l;
}

// 二分查找，递归版。从含有ｎ个元素的数组ａ中查找元素ｘ的下标
int wtlBinarySearch_Recursion(int* a, int n, int x){
    // 为了统一参数,将递归部分新定义一个函数。l和u的含义和迭代版的一样
    // 这是一个尾递归,因为递归函数的参数每次都可以确定，且函数内部不存在不确定的变量
    int wtlBinarySearch_Raw(int* a, int l, int u, int x){
        // l==u是递归的结束条件之一，表示ｘ可能为数组的第一个元素或最后一个
        if (l == u) {
            // 这里同样没有处理不存在的情况
            return l;
        }

        int m = (l + u) / 2;
        // 递归结束的条件之二，表示ｘ刚好为数组的中间一个元素
        if (a[m] == x) {
            return m;
        } else if (a[m] < x) {
            // ｘ比中间元素大，递归地在右半边的数组中进行二分查找
            return wtlBinarySearch_Raw(a, m + 1, u, x);
        } else {
            // ｘ比中间元素小，递归地在左半边的数组中进行二分查找
            return wtlBinarySearch_Raw(a, l, m, x);
        }
    }

    // 调用上面定义的递归函数
    return wtlBinarySearch_Raw(a, 0, n, x);
}

// 向数组ａ中插入ｘ，ｎ为数组长度，ｐ为插入的下标
void wtlInsertX(int* a, int n, int x, int p){
    // 这里是从数组右边开始查找插入位置的，这样可以变查找，边移动数组元素
    for (int i = n - 1; i >= p; i--) {
        a[i + 1] = a[i];
    }
    a[p] = x;
}

// 插入排序，改进一。使用二分查找，使查找插入位置的时间复杂度达到O(lg n)【递归版】
// 对含有ｎ个元素的无序数组ａ进行排序
int* wtlInsertionSort_Recursion(int* a, int n){
    // 将递归部分新定义为一个函数
    // l既表示左边数组的元素个数，又是将插入左边数组的那个元素的下标，r是右边数组的元素个数
    // 要明白这里的意思，看下原文作者的介绍就知道了
    int* wtlInsertionSort_Raw(int* a, int l, int r){
        // 右边数组元素的个数为0，表示排序完了，结束递归。注意是小于0，而不是等于0
        // 等于0时，此时还需要对最后一个元素进行排序
        if (r < 0) {
            // 返回排好序的数组
            return a;
        }

        // 二分查找元素a[l]在含有l个元素的数组a中需要插入的位置(下标)
        int p = wtlBinarySearch_Recursion(a, l, a[l]);
        // 找到后调用插入函数插入
        wtlInsertX(a, l, a[l], p);

        // 递归地对剩下的元素排序。插入一个元素后，此时下次的排序
        // 左边的数组元素个数增加1,右边的数组元素个数减1
        wtlInsertionSort_Raw(a, ++l, --r);
    }

    // 调用上面定义的递归函数
    return wtlInsertionSort_Raw(a, 1, n - 2);
}

// 插入排序，改进一。使用二分查找，使查找插入位置的时间复杂度达到O(lg n)【迭代版】
// 对含有ｎ个元素的无序数组ａ进行排序
int* wtlInsertionSort_Iteration(int* a, int n){
    // 循环遍历ｎ个元素
    for (int i = 1; i < n; i++) {
        // 二分查找每个元素需要插入的位置(下标)
        int p = wtlBinarySearch_Iteration(a, i, a[i]);
        // 找到后调用插入函数插入
        wtlInsertX(a, i, a[i], p);
    }

    // 返回排好序的数组
    return a;
}

// 插入排序，改进二。利用链表，使插入操作的时间复杂度达到O(1)
// 数组可以二分查找，但是插入的时候要一个一个的移动元素
// 链表不可以二分查找，但是插入的时候不用移动元素
int* wtlInsertionSort_Set(int* a, int n){
    // 创建一个链表
    wtlSET* set = wtlSet_Create();

    // 将元素一个一个地插入到链表中
    for (int i = 0; i < n; i++) {
        // 链表的插入算法支持排序
        wtlSet_Insert(set, a[i]);
    }

    // 链表的长度
    int len = wtlSet_Length(set);
    // 将链表中排好序的元素赋值给数组
    for (int i = 0; i < len; i++) {
        // 每次获取链表的第一个元素
        a[i] = wtlSet_GetFirst(set);
    }

    // 销毁链表
    wtlSet_Destroy(&set);

    // 返回排好序的数组
    return a;
}

// 使用二叉搜索树的最终改进。使插入排序算法的时间复杂度达到O(lg n)
// 二叉搜索树既支持二分查找，又不用在插入的时候移动元素
int* wtlInsertionSort_BSTree(int* a, int n) {
    // 创建一颗二叉搜索树
    wtlBSTREE* bstree = wtlBSTree_Create();

    // 将每个元素插入到树中
    for (int i = 0; i < n; i++) {
        // 根据二叉搜索树的定义进行插入
        wtlBSTree_InsertValue(&bstree, a[i]);
    }

    int i = 0;
    // 获取树中最小的元素
    wtlBSTREE_NODE* current = wtlBSTree_Min(bstree);
    // 将排好序的元素赋值给数组
    while (current) {
        // 获取节点中的数据赋值给对应数组位置
        a[i++] = wtlBSTREE_NodeValue(current);
        // 通过不断查找当前节点的后继节点，就可以将下个元素赋值个数组了
        current = wtlBSTree_Successor(bstree, wtlBSTREE_NodeValue(current));
    }

    // 销毁树
    wtlBSTree_Destroy(&bstree);

    // 返回排好序的数组
    return a;
}

// 测试(没什么好说的了)
int main(int argc, char* argv[])
{
    int a0[] = {7, 9, 2, 5, 0, 3, 6, 8, 4, 1};
    int a1[] = {4, 3, 8, 1, 0, 9, 6, 2, 7, 5};
    int a2[] = {7, 0, 8, 5, 9, 6, 3, 1, 4, 2};
    int a3[] = {9, 3, 8, 5, 7, 4, 6, 2, 0, 1};

    wtlInsertionSort_Recursion(a0, sizeof(a0) / sizeof(a0[0]));
    for (int i = 0; i < 10; i++) {
        printf("%d ", a0[i]);
    }
    printf("\n");

    wtlInsertionSort_Iteration(a1, sizeof(a1) / sizeof(a1[0]));
    for (int i = 0; i < 10; i++) {
        printf("%d ", a1[i]);
    }
    printf("\n");

    wtlInsertionSort_Set(a2, sizeof(a2) / sizeof(a2[0]));
    for (int i = 0; i < 10; i++) {
        printf("%d ", a2[i]);
    }
    printf("\n");

    wtlInsertionSort_BSTree(a3, sizeof(a3) / sizeof(a3[0]));
    for (int i = 0; i < 10; i++) {
        printf("%d ", a3[i]);
    }
    printf("\n");

    return 0;
}

---

解释就是上面那样了，我觉得挺详细的，如果不懂，看下原文就行了:)