双向链表排序，复杂度O(nlogn)

面试题

请你实现双向链表的排序，复杂度为O(nlogn)

数组的排序可以看之前这篇【c++实现常用排序算法(全)】

然后一般数组的快排可以这样

#include <vector>
#include <iostream>

using namespace std;

void quickSort1(vector<int> &nums, int start, int end) {
    if (start > end) return;
    int left = start, right = end;
    int temp = nums[start];

    while (left!=right) {
        while (left < right && nums[right]>temp) {
            right--;
        }

        while (left < right && nums[left]<=temp) {
            left++;
        }

        if (left < right) swap(nums[left], nums[right]);
    }

    nums[start] = nums[left];
    nums[left] = temp;

    quickSort(nums, start, left - 1);
    quickSort(nums, left + 1, end);

}

void quickSort2(vector<int>& nums, int start, int end) {
    if (start > end) return;
    int left = start, right = end;
    int temp = nums[start];

    while (left != right) {
        while (left < right && nums[right]>=temp) {
            right--;
        }
        swap(nums[left], nums[right]);

        while (left < right && nums[left] <= temp) {
            left++;
        }
        swap(nums[left], nums[right]);
    }
    if (left < right) {
        nums[start] = nums[left];
        nums[left] = temp;
    }

    quickSort(nums, start, left - 1);
    quickSort(nums, left + 1, end);

}

int main() {
    vector<int> nums = { 2,5,12,20,5,56,8 };
    quickSort1(nums, 0, nums.size() - 1);
    for (auto num: nums)
    {
        cout << num << endl;
    }
}

quickSort1和quickSort2方法都是可行的

然后双向链表的实现其实也是参考数组的实现，采用quickSort2方法，quickSort1好像不行

#include <iostream>

using namespace std;

struct pNode {
    int data;
    pNode *next;
    pNode *pre;
    pNode() { next = nullptr; pre = nullptr; data = 0; };
    pNode(int num) { next = nullptr; pre = nullptr; data = num; };
};

//添加元素方法，注意采用双指针，因为指针作为参数参与修改
void push(pNode **p, int value) {
    pNode *newNode = new pNode(value);
    (*p)->next = newNode;
    newNode->pre = *p;
    *p = (*p)->next;
}

//遍历指针方法
void traverse(pNode *node) {
    while (node) {
        cout << node->data << "  ";
        node = node->next;
    }
    cout << endl;
}

void quickSort(pNode *start, pNode *end) {
    if (left == right || !start || !end || !start->next) return;
    pNode *temp = start;
    pNode *left = start, *right = end;
    while (left != right) {
        while (right && left != right && right->data>=temp->data)
            right = right->pre;

        if (left && right) {
            int num = right->data;
            right->data = left->data;
            left->data = num;
        }

        while (left && left != right && left->data<=temp->data)
            left = left->next;

        if (left && right) {
            int num = right->data;
            right->data = left->data;
            left->data = num;
        }
    }

    if(start!=left) quickSort(start, left->pre);
    if(end!=left) quickSort(left->next, end);
}

int main() {
    pNode *node = new pNode(2);
    traverse(node);
    pNode* pivot = node;

    push(&pivot, 5);
    push(&pivot, 12);
    push(&pivot, 20);
    push(&pivot, 5);
    push(&pivot, 56);
    push(&pivot, 8);
    traverse(node);

    pNode* start = node;
    pNode* end = pivot;
    quickSort(start, end);
    traverse(node);

}