举报

下面这个自然的两路合并排序算法怎么样更精简(C语言)?

0

根据 TAOCP 的算法流程图写的。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdbool.h>

//
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

//
void pointer_swap(int** a, int** b) {
    int* temp = *a;
    *a = *b;
    *b = temp;
}


//
void print_data(int data[static 1], size_t len) {
    for (size_t i = 0; i < len; ++i) {
        printf("%d ", data[i]);
    }

    printf("\n");
}

//自然的两路合并排序
int natural_merge_sort(int data[static 1], size_t len) {
    int* src = data;
    int* dst = (int*)malloc(len*sizeof(int));
    if (!dst) return EXIT_FAILURE;

    int i = 0, j = len - 1;
    int k = 0, l = len - 1;
    int d = 1;

    bool is_next = false;

    for (;;) {
        if (i == j) {
            dst[k] = src[i];
            if (!is_next) {
                break;
            } else {
                i = 0, j = len - 1;
                k = 0, l = len - 1;
                d = 1;
                pointer_swap(&src, &dst);
                is_next = false;
            }
        }

        if (src[j] < src[i]) {
            dst[k] = src[j--];
            k += d;

            if (src[j] < src[j + 1]) {
                do {
                    dst[k] = src[i++];
                    k += d;
                } while (src[i - 1] <= src[i]);

                swap(&k, &l);
                d = -d;

                is_next = true;
            }
        } else {
            dst[k] = src[i++];
            k += d;
            if (src[i] < src[i - 1]) {
                do {
                    dst[k] = src[j--];
                    k += d;
                } while (src[j] >= src[j + 1]);

                swap(&k, &l);
                d = -d;

                is_next = true;
            }
        }
    }

    if (src == data) {
        memcpy(data, dst, len*sizeof(int));
        free(dst);
    } else {
        free(src);
    }

    return EXIT_SUCCESS;
}

int main(int argc, char* argv[argc + 1]) {
    int data[] = {503, 87, 512, 61, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703};
    natural_merge_sort(data, sizeof(data)/sizeof(int));
    print_data(data, sizeof(data)/sizeof(int));

    return EXIT_SUCCESS;
}
ava
避难所

2023-9-24

举报
0

看看还有没有比我更加中精简的,更加丧心病狂的。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int data[] =                        { 503, 87, 512, 61, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703    };

bool swap(int* a, int* b)           { int temp = *a; *a = *b; *b = temp; return true;                                 }
bool pointer_swap(int** a, int** b) { int* temp = *a; *a = *b;  *b = temp; return false;                              }

int natural_merge_sort(int data[], size_t len)
{    int* src = data, * dst = (int*)malloc(len * sizeof(int)); int i = 0, j = len - 1, k = 0, l = len - 1, d = 1; bool is_next = false;
    if (!dst) exit(EXIT_FAILURE);
    for (;;)
    {   if (i == j)
        {    dst[k] = src[i];
            if (!is_next) { break; }
            else { i = 0, j = len - 1, k = 0, l = len - 1, d = 1; is_next = pointer_swap(&src, &dst); }
        }
        if (src[j] < src[i])
        {   dst[k] = src[j--]; k += d;
            if (src[j] < src[j + 1])
            {   do { dst[k] = src[i++]; k += d; } while (src[i - 1] <= src[i]);
                is_next = swap(&k, &l); d = -d;
            } }
        else
        {   dst[k] = src[i++]; k += d;
            if (src[i] < src[i - 1])
            {   do { dst[k] = src[j--];  k += d; } while (src[j] >= src[j + 1]);
                is_next = swap(&k, &l); d = -d;
          } } }
    if (src == data) { memcpy(data, dst, len * sizeof(int)); free(dst); } else { free(src); }
    for (size_t i = 0; i < len; ++i) { printf("%d ", data[i]); } return 0;
}
int main(int argc, char* argv[]) { return natural_merge_sort(data, sizeof(data) / sizeof(int)); }
ava
粥磷酸

2023-9-24

算法精简,不是格式精简。太过紧凑的代码格式,并不能提高执行效率,反倒影响阅读。 -  慢羊羊  2023-9-26
举报
举报
0

二路归并算法是数据结构中的基本内容,你可以参考严明敏的数据结构一书,写的非常详细。

ava
慢羊羊

2023-9-27

技术讨论社区