基本排序算法的C语言实现

为了复习DS临时起意，大概率会咕咕咕...

• 插入排序
• 快速排序
• 归并排序
• 堆排序

插入排序

void insertion_sort(int p[], int n) {
    for (int i = 2; i <= n; i++) {
        int j = i, x = p[i];
        while (p[j - 1] > x) {
            p[j] = p[j - 1];
            j--;
        }
        p[j] = x;
    }
}

快速排序

void quicksort(int a[], int l, int r) {
    if (l < r) {
        int i = l, j = r, x = a[l];
        while (i < j) {
            while (i < j && a[j] >= x) j--;
            if (i < j) a[i++] = a[j];
            while (i < j && a[i] < x) i++;
            if (i < j) a[j--] = a[i];
        }
        a[i] = x;
        quicksort(a, l, i - 1);
        quicksort(a, i + 1, r);
    }
}

归并排序

void merge(int a[], int l, int mid, int r) {
    int *tmp = (int*)malloc(sizeof(int) * (r + 1));
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] < a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int i = l; i <= r; i++) a[i] = tmp[i];
    free(tmp);
}

void merge_sort(int p[], int l, int r) {
    if (l < r) {
        int mid = (l + r) / 2;
        merge_sort(p, l, mid);
        merge_sort(p, mid + 1, r);
        merge(p, l, mid, r);
    }
}

堆排序

//不稳定
void sift(int p[], int r, int n) {
    int x = p[r];
    while (2 * r <= n) {
        int k = 2 * r;
        if (k < n && p[k + 1] < p[k]) k++;
        if (p[k] >= x) {break;}
        p[r] = p[k];
        r = k;
    }
    p[r] = x;
}

void build_heap(int p[], int n) {
    //叶子结点已满足堆性质，故从n/2开始sift
    for (int i = n / 2; i >= 1; i--) {
        sift(p, i, n);
    }
}

void heap_sort(int p[], int n) {
    for (int i = n; i >= 2; i--) {
        swap(p[1], p[i]);
        sift(p, 1, i - 1);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build_heap(a, n);
    heap_sort(a, n);
    for (int i = 1; i <= n; i++)
        cout << a[i] <<" ";
    return 0;
}