这篇文章分析一下链表的各种排序方法。
以下排序算法的正确性都可以在LeetCode的链表排序这一题检测。本文用到的链表结构如下(排序算法都是传入链表头指针作为参数,返回排序后的头指针)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
插入排序(算法中是直接交换节点,时间复杂度O(n^2),空间复杂度O(1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
public :
ListNode *insertionSortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if (head == NULL || head->next == NULL) return head;
ListNode *p = head->next, *pstart = new ListNode(0), *pend = head;
pstart->next = head; //为了操作方便,添加一个头结点
while (p != NULL)
{
ListNode *tmp = pstart->next, *pre = pstart;
while (tmp != p && p->val >= tmp->val) //找到插入位置
{tmp = tmp->next; pre = pre->next;}
if (tmp == p)pend = p;
else
{
pend->next = p->next;
p->next = tmp;
pre->next = p;
}
p = pend->next;
}
head = pstart->next;
delete pstart;
return head;
}
}; |
选择排序(算法中只是交换节点的val值,时间复杂度O(n^2),空间复杂度O(1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution {
public :
ListNode *selectSortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
//选择排序
if (head == NULL || head->next == NULL) return head;
ListNode *pstart = new ListNode(0);
pstart->next = head; //为了操作方便,添加一个头结点
ListNode*sortedTail = pstart; //指向已排好序的部分的尾部
while (sortedTail->next != NULL)
{
ListNode*minNode = sortedTail->next, *p = sortedTail->next->next;
//寻找未排序部分的最小节点
while (p != NULL)
{
if (p->val < minNode->val)
minNode = p;
p = p->next;
}
swap(minNode->val, sortedTail->next->val);
sortedTail = sortedTail->next;
}
head = pstart->next;
delete pstart;
return head;
}
}; |
快速排序1(算法只交换节点的val值,平均时间复杂度O(nlogn),不考虑递归栈空间的话空间复杂度是O(1))
这里的partition我们参考数组快排partition的第二种写法(选取第一个元素作为枢纽元的版本,因为链表选择最后一元素需要遍历一遍),具体可以参考here
这里我们还需要注意的一点是数组的partition两个参数分别代表数组的起始位置,两边都是闭区间,这样在排序的主函数中:
void
quicksort(vector<
int
>&arr,
int
low,
int
high)
{
if
(low < high)
{
int
middle = mypartition(arr, low, high);
quicksort(arr, low, middle-1);
quicksort(arr, middle+1, high);
}
}
对左边子数组排序时,子数组右边界是middle-1,如果链表也按这种两边都是闭区间的话,找到分割后枢纽元middle,找到middle-1还得再次遍历数组,因此链表的partition采用前闭后开的区间(这样排序主函数也需要前闭后开区间),这样就可以避免上述问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
class Solution {
public :
ListNode *quickSortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
//链表快速排序
if (head == NULL || head->next == NULL) return head;
qsortList(head, NULL);
return head;
}
void qsortList(ListNode*head, ListNode*tail)
{
//链表范围是[low, high)
if (head != tail && head->next != tail)
{
ListNode* mid = partitionList(head, tail);
qsortList(head, mid);
qsortList(mid->next, tail);
}
}
ListNode* partitionList(ListNode*low, ListNode*high)
{
//链表范围是[low, high)
int key = low->val;
ListNode* loc = low;
for (ListNode*i = low->next; i != high; i = i->next)
if (i->val < key)
{
loc = loc->next;
swap(i->val, loc->val);
}
swap(loc->val, low->val);
return loc;
}
}; |
快速排序2(算法交换链表节点,平均时间复杂度O(nlogn),不考虑递归栈空间的话空间复杂度是O(1))
这里的partition,我们选取第一个节点作为枢纽元,然后把小于枢纽的节点放到一个链中,把不小于枢纽的及节点放到另一个链中,最后把两条链以及枢纽连接成一条链。
这里我们需要注意的是,1.在对一条子链进行partition时,由于节点的顺序都打乱了,所以得保正重新组合成一条新链表时,要和该子链表的前后部分连接起来,因此我们的partition传入三个参数,除了子链表的范围(也是前闭后开区间),还要传入子链表头结点的前驱;2.partition后链表的头结点可能已经改变
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
class Solution {
public :
ListNode *quickSortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
//链表快速排序
if (head == NULL || head->next == NULL) return head;
ListNode tmpHead(0); tmpHead.next = head;
qsortList(&tmpHead, head, NULL);
return tmpHead.next;
}
void qsortList(ListNode *headPre, ListNode*head, ListNode*tail)
{
//链表范围是[low, high)
if (head != tail && head->next != tail)
{
ListNode* mid = partitionList(headPre, head, tail); //注意这里head可能不再指向链表头了
qsortList(headPre, headPre->next, mid);
qsortList(mid, mid->next, tail);
}
}
ListNode* partitionList(ListNode* lowPre, ListNode* low, ListNode* high)
{
//链表范围是[low, high)
int key = low->val;
ListNode node1(0), node2(0); //比key小的链的头结点,比key大的链的头结点
ListNode* little = &node1, *big = &node2;
for (ListNode*i = low->next; i != high; i = i->next)
if (i->val < key)
{
little->next = i;
little = i;
}
else
{
big->next = i;
big = i;
}
big->next = high; //保证子链表[low,high)和后面的部分连接
little->next = low;
low->next = node2.next;
lowPre->next = node1.next; //为了保证子链表[low,high)和前面的部分连接
return low;
}
}; |
归并排序(算法交换链表节点,时间复杂度O(nlogn),不考虑递归栈空间的话空间复杂度是O(1)) 本文地址
首先用快慢指针的方法找到链表中间节点,然后递归的对两个子链表排序,把两个排好序的子链表合并成一条有序的链表。归并排序应该算是链表排序最佳的选择了,保证了最好和最坏时间复杂度都是nlogn,而且它在数组排序中广受诟病的空间复杂度在链表排序中也从O(n)降到了O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
class Solution {
public :
ListNode *mergeSortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
//链表归并排序
if (head == NULL || head->next == NULL) return head;
else
{
//快慢指针找到中间节点
ListNode *fast = head,*slow = head;
while (fast->next != NULL && fast->next->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
fast = slow;
slow = slow->next;
fast->next = NULL;
fast = sortList(head); //前半段排序
slow = sortList(slow); //后半段排序
return merge(fast,slow);
}
}
// merge two sorted list to one
ListNode *merge(ListNode *head1, ListNode *head2)
{
if (head1 == NULL) return head2;
if (head2 == NULL) return head1;
ListNode *res , *p ;
if (head1->val < head2->val)
{res = head1; head1 = head1->next;}
else {res = head2; head2 = head2->next;}
p = res;
while (head1 != NULL && head2 != NULL)
{
if (head1->val < head2->val)
{
p->next = head1;
head1 = head1->next;
}
else
{
p->next = head2;
head2 = head2->next;
}
p = p->next;
}
if (head1 != NULL)p->next = head1;
else if (head2 != NULL)p->next = head2;
return res;
}
}; |
冒泡排序(算法交换链表节点val值,时间复杂度O(n^2),空间复杂度O(1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
public :
ListNode *bubbleSortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
//链表快速排序
if (head == NULL || head->next == NULL) return head;
ListNode *p = NULL;
bool isChange = true ;
while (p != head->next && isChange)
{
ListNode *q = head;
isChange = false ; //标志当前这一轮中又没有发生元素交换,如果没有则表示数组已经有序
for (; q->next && q->next != p; q = q->next)
{
if (q->val > q->next->val)
{
swap(q->val, q->next->val);
isChange = true ;
}
}
p = q;
}
return head;
}
}; |
对于希尔排序,因为排序过程中经常涉及到arr[i+gap]操作,其中gap为希尔排序的当前步长,这种操作不适合链表。
对于堆排序,一般是用数组来实现二叉堆,当然可以用二叉树来实现,但是这么做太麻烦,还得花费额外的空间构建二叉树
文章转自:
相关推荐
主要介绍了C#双向链表LinkedList排序实现方法,涉及C#双向链表的定义与排序技巧,具有一定参考借鉴价值,需要的朋友可以参考下
从链表中的最后一个中查找第 n 个元素 - LinkedList-nthToLast.java 删除链表中的重复数据 - RemoveDuplicateLinkedList.java 用 替换空格 - ReplaceSpace.java 反转字符串 - ReverseString.java 实现堆栈和...
链表算法的实现,该算法从stdin读取用户命令并根据用户指令命令在链表上运行特定功能,例如:PUT n,GET n,LIST,FIRST,LAST,SORT,CLEAR,REMOVE n,EXIT,其中: PUT n-将一个整数n插入到链表中。 GET n-从...
)栈(堆栈)类别(队列)链表(LinkedList)单链表(LinkedList)双链表(DoublyLinkedList)循环链表(CircularLinkedList)判断链表是否成环(LinkedListWithCycle)链表插入排序(InsertionSort)链表快速排序...
Sort 排序 7. Graph 图 8. Algorithm 算法 9. leetcode 刷题 10. 剑指offer 1. LinkedList 链表 代码路径: 主要包含单向链表:com.imyiren.datastructure.linkedlist.SingleLinkedList 包括:单向链表的添加、遍历...
Sort 根据算法导论(中文版第四版)中的伪代码实现的排序算法。 堆排序 HeapSort 快速排序 QuickSort 插入排序 InsertSort 数据结构 Data Structure 二叉搜索树 BinarySearchTree 设计模式 Design Patterns 单例模式...
linkedlist(链表) 两数相加 反转链表 回文链表 环形链表 环形链表II recurrence(递归) 岛屿最大面积 stack(栈) 两个栈实现队列 有效括号 string(字符串) Z字形变换 tree(树) 二叉搜索树的最近公共祖先 二叉树的最近...
链表(LinkedList) 堆(Heap) 排序(Sort) 位运算(BitManipulation) 图(Graph) 并查集(UnionFind) 分治算法(DivideandConquer) 滑动窗口(SlidingWindow) 字典树(Trie) 递归(Recursion) OrderedMap...
排序 1. BubbleSort 2. SelectionSort 3. InsertionSort 4. HeapSort - Library Implementation - Custom Implementation 5. QuickSort 6. MergeSort 链表 1. InsertAtEnd 2. InsertAtBeginning 3. InsertAtPos 4. ...
Sort_Alg 排序算法 Recursion_alg 递归算法 Tree_alg 树算法 LinkedList_alg 链表算法 Graph_alg 图算法 Greedy_alg 贪心算法 BFS/DFS_alg 广/深度算法 Everyday_alg 每日算法 HOT100 leetcode-100热题 UPDATE LOG ...
This is a repository containing notes and examples of common data structure and algorithms. ...InsertionSort: 插入排序,像打牌时改变手牌顺序的步骤一样,对于第i张牌而言,我们认为前i-1张
LinkedList(链表) Tree(树) 2、leetcode (力扣) coding with leetcode 2.1 leetcode list id title created type 001 twoSum 2020/10/6 23:50 Array 206 ReverseNode 2020/10/8 0:16 LinkedList 876 MiddleNode ...
LinkedList:简单的链表实现源代码: 堆栈:基本堆栈实现源代码: 卡片:洗一副卡片。 源代码: 波兰逆向符号:解决问题源代码: 河内塔:解决问题源代码: 排序算法游乐场 BubbleSort:冒泡排序算法实现源代码: ...
linkedList 链表 map 字典法 math 有关数字反转处理或者数学方面 sort 排序 stack 栈 structure 设计数据结构类 sw 滑动窗口 sliding window tree 树 bst 二叉搜索树性质应用 depth 二叉树深度问题 doubleRecursio
反向链表(给定链表反向部分的长度) ListNode start = pre.next; ListNode then = start.next; //key part of reversing given length linkedlist for(int i = 0; i< n-m;i++){ start.next = then.next; then....
排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A.可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1(2分) ...
排序 快排:com.monkey.sort.Code01_QuickSort 链表 倒序单链表:com.monkey.linkedlist.Code01_ReverseLinkedList 字符串 KMP算法: 二叉树 前序,中序,后序遍历: 按层遍历: 动态规划 蓄水池算法:...
排序:Comparable Comparator Collections.sort() ArrayList:底层用数组实现的List 特点:查询效率高,增删效率低 轻量级 线程不安全 LinkedList:底层用双向循环链表 实现的List 特点:查询效率低,增删效率高 ...
“工欲善其事,必先利其器”,在Java程序开发过程中,很多算法(比如:MD5加密算法)、很多数据结构(比如链表LinkedList)已经实现并且大多放在类库的java.util包中,程序员只需要了解各种工具的功能就可以直接调用...
Sort # 排序算法 │ └── Structure # 数据结构 │ ├── ADT # 抽象数据类型 │ ├── Heap # 堆 │ ├── LinkedList # 链表 │ ├── PriorityQueue # 优先队列 │ ├── Queue...