文章目录
数组排序算法参考：冒泡排序、插入排序、选择排序、归并排序、快速排序算法（C++实现）-CSDN博客
链表排序算法参考：链表排序总结（全）（C++）-CSDN博客
这里主要介绍三种链表排序方法，第一种是借助数组进行排序的方法，第二种是插入排序，第三种是归并排序，当然链表排序也可以用快排等其他方法，这里就不一一介绍了。
借助数组排序
顾名思义，就是通过数组来实现间接的链表排序，大概思路就是先将链表里每个节点的值存在数组里，对数组进行排序（数组排序方法有很多种，也可以直接调用sort函数来排序），将排序好的数组再依次赋值给链表的每个节点。
这个排序方法算是一种不那么正统的排序，时间复杂度和空间复杂度会受数组排序算法的影响。如果基于快排，那时间复杂度就是O(nlogn)，空间复杂度最好为O(logn)，最差为O(n)。
/**
* 数组快排
*/
void quickSort(vector<int> &nums, int begin, int end)
{
if (begin >= end)
{
return;
}
int left = begin;
int right = end;
int key = begin;
while (begin < end)
{
// 选取了左key，一定要右边先移动
while (begin < end && nums[end] >= nums[key])
{
end--;
}
while (begin < end && nums[begin] <= nums[key])
{
begin++;
}
swap(nums[begin], nums[end]);
}
swap(nums[begin], nums[key]);
key = begin;
quickSort(nums, left, key - 1);
quickSort(nums, key + 1, right);
}
/**
* 借助数组排序（基于快排）
* 时间复杂度O(nlogn)
* 空间复杂度跟快排一样：最好为O(logn)，最差为O(n)
*/
void trickSort(listNode *head)
{
if (head == NULL)
{
cout << "link list is empty" << endl;
return;
}
vector<int> nums;
listNode *p = head;
while (p != NULL)
{
nums.push_back(p->val);
p = p->next;
}
quickSort(nums, 0, nums.size() - 1);
p = head;
for (auto num : nums)
{
p->val = num;
p = p->next;
}
}
插入排序
链表的插入排序和数组的插入排序本质上是一样的，但是实现方法上有些不同
时间复杂度：O(n^2)；空间复杂度：O(1)
/**
* 链表插入排序
* 时间复杂度：O(n^2)
* 空间复杂度：O(1)
*/
void linkInsertSort(listNode **head)
{
if (*head == NULL || (*head)->next == NULL)
{
return;
}
// 创建一个哑节点（辅助节点）
listNode *dummy = new listNode(-1);
dummy->next = *head;
listNode *pre = *head;
listNode *cur = (*head)->next;
listNode *temp = dummy;
while (cur != NULL)
{
// 如果当前值比上一次插入点的值要小，就只能从头查找插入点,否则，插入点的查找可以从上一个插入点之后开始查找
if (temp->val > cur->val)
{
temp = dummy;
}
if (cur->val >= pre->val)
{
pre = pre->next;
cur = cur->next;
}
else
{
while (temp->next->val < cur->val)
{
temp = temp->next;
}
pre->next = cur->next;
cur->next = temp->next;
temp->next = cur;
cur = pre->next;
}
}
*head = dummy->next;
}
归并排序
归并排序似乎是链表排序中最常用到的一种排序方法，时间复杂度：O(nlogn)，空间复杂度：O(logn)，由递归决定？也有文章说空间复杂度是O(1)
/**
* 归并排序
* 时间复杂度：O(nlogn)
* 空间复杂度：O(logn)，由递归决定？也有文章说空间复杂度是O(1)
*/
class MergeSort
{
public:
listNode *merge(listNode *left, listNode *right)
{
auto dummy = new listNode(-1);
auto h = dummy;
while (left != NULL && right != NULL)
{
if (left->val < right->val)
{
h->next = left;
left = left->next;
}
else
{
h->next = right;
right = right->next;
}
h = h->next;
}
h->next = left == NULL ? right : left;
return dummy->next;
}
listNode *mergeSort(listNode *head)
{
// 这个是终止条件，一定要有！
if (head->next == NULL)
return head;
listNode *slow = head, *fast = head->next;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
auto r_head = slow->next;
slow->next = NULL;
auto left = mergeSort(head);
auto right = mergeSort(r_head);
return merge(left, right);
}
listNode *sortList(listNode *head)
{
if (head == NULL || head->next == NULL)
{
return head;
}
return mergeSort(head);
}
};
测试用例
#include <iostream>
#include <cstdlib>
#include <random>
#include <algorithm>
#include <vector>
using namespace std;
struct listNode
{
int val;
listNode *next;
// 构造函数
listNode(int x) : val(x), next(nullptr) {}
};
/**
* 生成随机数
*/
int randNum(void)
{
random_device rd;
int gen(rd());
return gen % 100;
}
/**
* 创建单链表
*/
void linkCreate(listNode **head, listNode *p_new)
{
if (*head == NULL)
{
*head = p_new;
return;
}
listNode *p = *head;
while (p->next != NULL)
{
p = p->next;
}
p->next = p_new;
p_new->next = NULL;
}
/**
* 遍历链表
*/
void linkPrint(listNode *head)
{
if (head == NULL)
{
cout << "link list is empty" << endl;
return;
}
listNode *p = head;
while (p != NULL)
{
cout << p->val << " -> ";
p = p->next;
}
cout << "NULL" << endl;
}
/**
* 数组快排
*/
void quickSort(vector<int> &nums, int begin, int end)
{
if (begin >= end)
{
return;
}
int left = begin;
int right = end;
int key = begin;
while (begin < end)
{
// 选取了左key，一定要右边先移动
while (begin < end && nums[end] >= nums[key])
{
end--;
}
while (begin < end && nums[begin] <= nums[key])
{
begin++;
}
swap(nums[begin], nums[end]);
}
swap(nums[begin], nums[key]);
key = begin;
quickSort(nums, left, key - 1);
quickSort(nums, key + 1, right);
}
/**
* 借助数组排序（基于快排）
* 时间复杂度O(nlogn)
* 空间复杂度跟快排一样：最好为O(logn)，最差为O(n)
*/
void trickSort(listNode *head)
{
if (head == NULL)
{
cout << "link list is empty" << endl;
return;
}
vector<int> nums;
listNode *p = head;
while (p != NULL)
{
nums.push_back(p->val);
p = p->next;
}
quickSort(nums, 0, nums.size() - 1);
p = head;
for (auto num : nums)
{
p->val = num;
p = p->next;
}
}
/**
* 链表插入排序
* 时间复杂度：O(n^2)
* 空间复杂度：O(1)
*/
void linkInsertSort(listNode **head)
{
if (*head == NULL || (*head)->next == NULL)
{
return;
}
// 创建一个哑节点（辅助节点）
listNode *dummy = new listNode(-1);
dummy->next = *head;
listNode *pre = *head;
listNode *cur = (*head)->next;
listNode *temp = dummy;
while (cur != NULL)
{
// 如果当前值比上一次插入点的值要小，就只能从头查找插入点,否则，插入点的查找可以从上一个插入点之后开始查找
if (temp->val > cur->val)
{
temp = dummy;
}
if (cur->val >= pre->val)
{
pre = pre->next;
cur = cur->next;
}
else
{
while (temp->next->val < cur->val)
{
temp = temp->next;
}
pre->next = cur->next;
cur->next = temp->next;
temp->next = cur;
cur = pre->next;
}
}
*head = dummy->next;
}
/**
* 归并排序
* 时间复杂度：O(nlogn)
* 空间复杂度：O(logn)，由递归决定？也有文章说空间复杂度是O(1)
*/
class MergeSort
{
public:
listNode *merge(listNode *left, listNode *right)
{
auto dummy = new listNode(-1);
auto h = dummy;
while (left != NULL && right != NULL)
{
if (left->val < right->val)
{
h->next = left;
left = left->next;
}
else
{
h->next = right;
right = right->next;
}
h = h->next;
}
h->next = left == NULL ? right : left;
return dummy->next;
}
listNode *mergeSort(listNode *head)
{
// 这个是终止条件，一定要有！
if (head->next == NULL)
return head;
listNode *slow = head, *fast = head->next;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
auto r_head = slow->next;
slow->next = NULL;
auto left = mergeSort(head);
auto right = mergeSort(r_head);
return merge(left, right);
}
listNode *sortList(listNode *head)
{
if (head == NULL || head->next == NULL)
{
return head;
}
return mergeSort(head);
}
};
int main(int argc, char const *argv[])
{
listNode *head = NULL, *p_new = NULL;
MergeSort mergeTool;
// 创建链表
for (int i = 0; i < 10; i++)
{
p_new = (listNode *)malloc(sizeof(listNode));
p_new->val = randNum();
linkCreate(&head, p_new);
}
// 遍历链表
linkPrint(head);
head = mergeTool.sortList(head);
linkPrint(head);
return 0;
}