用链表排序，数组输出

解题思路:

注意事项:

参考代码:

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

typedef struct be {

    int value;//数据

    //左指针，右指针，伙伴指针

    struct be *left, *right, *huo;

    char runOstop;//0,跳跃，1停止

} TU;

// 函数声明

void isRun(TU *);

void output(TU*, int);

void jumpR(TU*);

TU* findRoot(TU*);

TU* mergeSort(TU*);

TU* split(TU*);

TU* merge(TU* , TU*);

int getListLength(TU*);

int main(int argc, char** argv) {

    int n;

    scanf("%d", &n);

    TU *head = (TU*)calloc(n, sizeof(TU));

    // 输入数据

    for (int i = 0; i < n; i++) {

        scanf("%d", &head[i].value);

        head[i].runOstop = 0;

    }

    // 将数组转换为链表并排序

    TU *list = head;

    for (int i = 1; i < n; i++) {

        list->right = head+i;

        head[i].left = list;

        list = list->right;

    }

    list->right = NULL;

    head[0].left = NULL;

    // 归并排序

    TU *sorted = mergeSort(head);

    // 重新建立循环连接

    TU *last = sorted;

    while (last->right != NULL) {

        last = last->right;

    }

    last->right = sorted;

    sorted->left = last;

    // 处理排序后的链表

    isRun(sorted);

    jumpR(sorted);

    // 输出结果

    output(head, n);

    free(head);

    return 0;

}

// 归并排序实现

TU* mergeSort(TU* head) {

    if (!head || !head->right) return head;

    TU* second = split(head);

    head = mergeSort(head);

    second = mergeSort(second);

    return merge(head, second);

}

// 分割链表

TU* split(TU* head) {

    TU* fast = head;

    TU* slow = head;

    while (fast->right && fast->right->right) {

        fast = fast->right->right;

        slow = slow->right;

    }

    TU* temp = slow->right;

    slow->right = NULL;

    if (temp) temp->left = NULL;

    return temp;

}

// 合并两个有序链表

TU* merge(TU* first, TU* second) {

    if (!first) return second;

    if (!second) return first;

    if (first->value <= second->value) {

        first->right = merge(first->right, second);

        first->right->left = first;

        first->left = NULL;

        return first;

    } else {

        second->right = merge(first, second->right);

        second->right->left = second;

        second->left = NULL;

        return second;

    }

}

// 输出函数

void output(TU *a, int n) {

    for (int i = 0; i < n; i++)

        printf("%d ", a[i].value);

}

// 确定每个节点的伙伴

void isRun(TU *st) {

    TU *p = st;

    do {

        int a = abs(p->value - p->left->value);

        int b = abs(p->right->value - p->value);

        p->huo = (a <= b) ? p->left : p->right;

        p = p->right;

    } while (p != st);

}

// 查找根节点

TU* findRoot(TU* node) {

    TU *root = node;

    while (root->huo->huo != root)

        root = root->huo;

    TU *current = node;

    while (current != root) {

        TU *next = current->huo;

        current->huo = root;

        current = next;

    }

    return root;

}

// 处理跳跃逻辑

void jumpR(TU* st) {

    TU *current = st;

    do {

        if (current->runOstop) {

            current = current->right;

            continue;

        }

        TU *peer = current->huo;

        if (peer->huo == current) {

            int x = current->value, y = peer->value;

            current->value = peer->value = (x + y) / 2;

            current->runOstop = peer->runOstop = 1;

        }

        current = current->right;

    } while (current != st);

    current = st;

    do {

        if (!current->runOstop) {

            TU *root = findRoot(current);

            current->value = root->value;

            current->runOstop = 1;

        }

        current = current->right;

    } while (current != st);

}