FDS | 常见排序算法实现 C 语言版

无聊写了下 C 语言实现的各种排序算法

预处理

由于 C 语言没有多态, 只考虑对某个类型排序, 以 int 类型为例子

#include<stdio.h>
#include<stdlib.h>
#define ElemType int

辅助函数

定义谓词函数和交换函数

// 表示第一个参数大于第二个参数
int greater(const ElemType* x, const ElemType* y){
    return *x > *y;
}

// 表示第一个参数小于第二个参数
int less(const ElemType* x, const ElemType* y){
    return greater(y, x);
}

void swap(ElemType* x, ElemType* y){
    ElemType tmp;
    tmp = *x, *x = *y, *y = tmp;
}

函数接口

统一接口格式如下

void sort(ElemType* base, size_t n, int (*ptrCompFunc)(const ElemType* x, const ElemType* y));
/*
base:           指向排序数组的首个元素
n:              待排序数组的大小
ptrCompFunc:    排序用的比较函数
*/

具体实现

冒泡排序

Time complexity: $T(N)=O(N^2)$

Space complexity: $T(N)=O(1)$

void bubbleSort(ElemType* base, size_t n, int (*ptrCompFunc)(const ElemType* x, const ElemType* y)){
    for(size_t i = 0; i < n - 1; ++i)
        for(size_t j = i; j < n; ++j)
            if(!(*ptrCompFunc)(base + i, base + j))
                swap(base + i, base + j);
}

插入排序

Time complexity: $T(N)=O(N^2)$

Space complexity: $T(N)=O(1)$

void insertionSort(ElemType* base, size_t n, int (*ptrCompFunc)(const ElemType* x, const ElemType* y)){
    for(size_t i = 1; i < n; ++i){
        size_t tmp = i;
        size_t j;
        for (j = i; j > 0 && (*ptrCompFunc)(base + tmp, base + j - 1); --j)
            base[j] = base[j - 1];
        base[j] = base[tmp];
    }
}

选择排序

Time complexity: $T(N)=O(N^2)$

Space complexity: $T(N)=O(1)$

void selectionSort(ElemType* base, size_t n, int (*ptrCompFunc)(const ElemType* x, const ElemType* y)){
    for(size_t i = 0; i < n - 1; ++i){
        size_t m = i;
        for(size_t j = i + 1; j < n; ++j){
            if((*ptrCompFunc)(base + j, base + m)){
                m = j;
            }
        }
        swap(base + i, base + m);
    }
}

堆排序

原地堆排序, 排序思路是先把数组调整成堆, 再逐个弹出堆顶元素到最后一位

根据排序思路可分析出排序序和堆序的关系

升序: 排序后最大的元素在最后一位, 说明堆顶元素是最大的, 堆序是大根堆
降序: 排序后最小的元素在最后一位, 说明堆顶元素是最小的, 堆序是小根堆

Time complexity: $T(N)=O(N\log N)$

Space complexity: $T(N)=O(1)$

void percolateDown(ElemType* base, size_t begin, size_t end,int (*ptrCompFunc)(const ElemType* x, const ElemType* y)){
    size_t parent, lChild, rChild;
    parent = begin, lChild = 2 * parent + 1, rChild = lChild + 1;
    while(parent < end){
        size_t max = parent;
        if(lChild < end && !(*ptrCompFunc)(base + lChild, base + max))
            max = lChild;
        if(rChild < end && !(*ptrCompFunc)(base + rChild, base + max))
            max = rChild;
        if(parent == max)   break;
        swap(base + parent, base + max);
        parent = max, lChild = 2 * parent + 1, rChild = lChild + 1;
    }
}

void heapSort(ElemType* base, size_t n, int (*ptrCompFunc)(const ElemType* x, const ElemType* y)){
    for(size_t i = n / 2 - 1; ; --i){
        percolateDown(base, i, n, ptrCompFunc);
        if(i == 0)  break;
    }
    for(size_t i = n - 1; ; --i){
        swap(base, base + i);
        percolateDown(base, 0, i, ptrCompFunc);
        if(i == 0)  break;
    }
}

归并排序

用到了辅助数组 buf

Time complexity: $T(N)=O(N\log N)$

Space complexity: $T(N)=O(N)$

void mergeSortImplmt(ElemType* base, size_t begin, size_t end, int (*ptrCompFunc)(const ElemType* x, const ElemType* y)){
    if(end - begin <= 1)    return;
    size_t mid = (begin + end) / 2;
    mergeSortImplmt(base, begin, mid, ptrCompFunc);
    mergeSortImplmt(base, mid, end, ptrCompFunc);
    size_t i, j, k;
    i = begin;
    j = mid;
    k = 0;
    ElemType* buf = (ElemType*)malloc(sizeof(ElemType) * (end - begin));
    while(i < mid && j < end)
        if(ptrCompFunc(base + i, base + j))
            buf[k++] = base[i++];
        else
            buf[k++] = base[j++];
    while(i < mid)
        buf[k++] = base[i++];
    while(j < end)
        buf[k++] = base[j++];
    i = begin;
    k = 0;
    while(i < end)
        base[i++] = buf[k++];
    free(buf);
}

void mergeSort(ElemType* base, size_t n, int (*ptrCompFunc)(const ElemType* x, const ElemType* y)){
    mergeSortImplmt(base, 0, n, ptrCompFunc);
}

快速排序

内存是递归栈消耗的, 本体没有开辅助数组

Time complexity: $T(N)=O(N\log N)$

Space complexity: $T(N)=O(\log N)$

void quickSortImplmt(ElemType* base, size_t begin, size_t end, int (*ptrCompFunc)(const ElemType* x, const ElemType* y)){
    if(end <= begin)    return;
    size_t j = begin + 1;
    for(size_t i = begin + 1; i < end; ++i)
        if((*ptrCompFunc)(base + i, base + begin)){
            swap(base + i, base + j);
            ++j;
        }
    swap(base + begin, base + j - 1);
    arrayPrint_int(base + begin, end - begin);
    quickSortImplmt(base, begin, j - 1, ptrCompFunc);
    quickSortImplmt(base, j, end, ptrCompFunc);
}

void quickSort(ElemType* base, size_t n, int (*ptrCompFunc)(const ElemType* x, const ElemType* y)){
    quickSortImplmt(base, 0, n, ptrCompFunc);
}