双向链表排序,复杂度O(nlogn)
2023-02-18 16:41:44 时间
面试题
请你实现双向链表的排序,复杂度为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);
}