排序算法总结

.排序所关心的问题

  内排与外排: 内外是就存储而言的. 内排所有数据在内存中, 而外排由于数据过大, 需要借助磁盘完成排序.

  稳定性:  待排序数 ..., a, ...,  b; 且 a == b; 如果排序后为 ..., b, ..., a 则为不稳定排序, 反之为稳定排序.

.冒泡排序

void bubble_sort(key *keys, int len, comp_func compare) {
    int     step = 0;
    int     i = 0;
    int     is_swap = 0;

    /* 比较步数控制 */
    for (step = len-1; step > 0; --step) {

        /* 每一遍, 将最大的数放到末尾 */
        is_swap = 0;
        for (i = 0; i < step; ++i) {
            if (compare(keys[i], keys[i+1]) > 0) {
                swap(&keys[i], &kyes[i+1])
                is_swap = True;
            }
        }

        /* 如果某一遍中没有交换, 说明数据以有序 */ 
        if (!is_swap) break;
    }

    return;
}

.插入排序

  插入排序就如我们玩扑克, 边接边排扑克

void insertion_sort(key *keys, int len, comp_func compare) {
    int     step = 0;
    int     i = 0;
    key     temp;

    // 此时手中有一张牌 keys[0]; 依次接 keys[2:]
    for (step = 1; step < len; ++step) {

        temp = keys[step]; // 接到的牌

        // 手中的牌从左到右为从小到大的顺序, 我们从大到小找插入位置
        for (i = step-1; i >= 0; --i) {

            // 如果接到的牌比第 i 张小, 
            if (compare(keys[i], temp) > 0) {
                // 空开插入位置
                keys[i+1] = keys[i]

            // 如果接到的牌比第 i 张大, 则插到 i 后边, 完成
            } else {
                keys[i+1] = temp;
                break;

            }
        }

    }

    return;
}

.希尔排序

void shell_sort(int *keys, int len) {
    int     step, h;
    int     i;
    int     temp;

    // 生成初始分割组数 h
    // 若 h 为 1, 则为普通的插入排序
    for (h = 1; h <= len / 9; h = 3 * h + 1)
        ;

    // 每次缩小分组数, 直到为 1 组
    for ( ; h > 0; h /=3 ) {

        // 此时和插入排序相似, 唯一不同的是跳跃 h 插入
        for (step = h; step < len; ++step) {

            temp = keys[step];
            for (i = step - h; i >= 0; i -= h) {
                if (temp < keys[i]) {
                    keys[i+h] = keys[i];

                } else {
                    break;
                }

            }
        }
        keys[i+h] = temp;
    }

    return;
}

.快排

void quick_sort(int *keys, int left, int right) {
    if (right > left) {
        int i, j;

        // 将 keys[right] 作为分割点
        i = left - 1;
        j = right;

        for (;;) {

            // 从左边开始找到 > keys[right] 的元素
            while (keys[++i] <= keys[right])
                ;

            // 从右到左找到 < keys[right] 的元素
            while (j > 0) {
                if (keys[--j] < keys[right]) {
                    break;
                }
            }

            // 若 i >= j, 则说明数据已经以 keys[right] 分开
            if (i >= j) break;

            // 交换这两个数
            swap(&keys[i], &keys[j]);

        }

        // 将 keys[right] 放到分割点位置
        swap(&keys[i], &keys[right]);

        // 递归处理
        quick_sort(keys, left, i-1);
        quick_sort(keys, i+1, right);
    }
}

.堆排序

static void downheap(int *keys, int first, int last) {
    int child, parent, i;

    // 递归, 将孩子节点较大的与父节点交换 
    for (i = first; (child = i * 2 + 1) <= last; i = child) {
        if (child + 1 < last && keys[child+1] > keys[child]) 
            child += 1;

        swap(&keys[i], &keys[child]);

    }

    // 回溯, 原来父节点的值与较大字节的值比较, 将最大的值放到父节点
    while (1) {
        parent = (i - 1) / 2;
        if (parent < first || parent == i || keys[parent] > keys[i]) 
            break;

        swap(&keys[i], &keys[parent]);

    }
}

void heap_sort(int *keys, int len) {
    int i;

    // 使len为最大索引
    len -= 1;

    // 构造大顶堆, 此时保证 keys[0] 为最大元素
    for (i = (len-1)/ 2; i >= 0; --i)
        downheap(keys, i, len);

    for (i = len; i > 0; ) {
        // 将 keys[0] 放到尾部,
        swap(&keys[i], &keys[0]);

        // 移除最大元素, 重新构建堆 
        downheap(keys, 0, --i);
    }
}