建站源码,关键词排名关键词优化,长沙h5网站建设,怎么查网站有没有做推广2018年第一次试着写单链表的快速排序。所使用的方法虽然代码非常简洁#xff0c;只有20行#xff0c;但可惜并不是纯正的快速排序#xff0c;而且使用的是数据交换也不是节点链接改变#xff0c;造成效率也有点问题。后来又于2022年重写单链表的快速排序。这一次想出了一种…2018年第一次试着写单链表的快速排序。所使用的方法虽然代码非常简洁只有20行但可惜并不是纯正的快速排序而且使用的是数据交换也不是节点链接改变造成效率也有点问题。后来又于2022年重写单链表的快速排序。这一次想出了一种很容易理的解方法且是比较纯正的快速排序了但可惜代码行数较多近60行了且其中引入了2个局部变量作为辅助并不那么干净。 以上这一切都记录在拙作《单链表的快速排序与归并排序》中了。这篇文章还另外介绍了单链表的归并排序
今天忽有兴趣重写一下单链表的快速排序。写之前没有看以前的代码使得思维并没有受到之前程序的影响。完成后只觉今是而昨非。现在的代码比之前的有了许多进步比如是纯正的快速排序了行数也由近60行缩减到39行了。虽然还觉得有哪里不那么完美奈何水平有限暂且如此吧。
算法本身不再介绍了但在贴出代码之前还是先介绍下具体写法。 首先这是一个函数比如就叫quick_sort_singly_linked_list吧。 第1个问题它返回的是什么有2种写法皆可。 第一种写法它返回一个Node *代表排序后的单链表的首节点 第二种写法它什么也不返回即返回值为void 这也是可以的因为可以将首节点作为一个参数放在参数列表中比如弄一个二级指针。 为简便起见这里还是采用大家耳熟能详的写法即返回Node *.
第2个问题它的参数是什么呢 可以和数组的快速排序做对比。因此应该有2个参数即 (Node * head, Node * tail). 这里的tail是取不到的即需要做排序的节点是在[head, tail)这个区间。这也符合一开始的时候tail为nullptr.
核心的做法是什么呢
使用指针p遍历[head, tail)指针h1代表第一个链表的首节点即所有小于等于head的节点组成的链表指针h1p代表第一个链表的游标因此其最后值代表第一个链表的最后一个节点指针h2代表第二个链表的首节点及所有大于head的节点组成的链表指针h2p代表第二个链表的游标因此其最后的值代表第二个链表的最后一个节点也即tail的前一个节点用nullptr作为h1和h1p的初始值因为一个链表里未必有比head小或等的节点用head作为h2和h2p的初始值一次遍历走完以后需要使用if (h1) h1p-next head;来把第一个链表和第二个链表连接成一个链表之后需根据h1是否为nullptr来判定如何进行递归处理普通情况下以(h1, head)和 (head-next, tail)分别对这2段链表进行递归的快速排序; 然后再用head-next p2;将递归后的2段结果进行连接p2为第二段链表递归调用的返回值若是h1为nullptr的情况则更简单只需对(head-next, tail)进行递归排序等于只是排除了head这一个元素因为它就是最小的最终返回的是递归后的第一个链表的首节点p1(若h1为nullptr, 则将递归的结果赋给head-next, 然后返回head即可
文字写出来实在是太罗嗦了。看代码则简洁很多。
#include iostream
using namespace std;struct Node {int val;Node * next;Node(int v, Node * pnullptr) : val(v), next(p) {}
};void print_linked_list(Node *p) {while (p) {cout p-val ;p p-next;}cout endl;
}void delete_linked_list(Node *p) {while (p ! nullptr) {Node * tmp p-next;delete p;p tmp;}
}// For [head, tail), put the head in the middle, so that,
// left nodes head right nodes
// Return: the latest head node of the singly linked list
Node * quick_sort_singly_linked_list(Node * head, Node * tail)
{if (head tail || head-next tail) return head;Node *h1 nullptr, *h1p nullptr;Node *h2 head, *h2p head;Node * p head-next; while (p ! tail) {if (p-val head-val) {if (h1) {h1p-next p;h1p p;}else { // h1 is nullptr, i.e. this is the first smaller nodeh1 h1p p;}}else { // p-val head-val h2p-next p; h2p p;}p p-next; }// Join the 2 linked list if (h1) h1p-next head;h2p-next tail; if (h1 nullptr) { // head is the minimum node in [head, tail)head-next quick_sort_singly_linked_list(head-next, tail);return head;}Node * p1 quick_sort_singly_linked_list(h1, head);Node * p2 quick_sort_singly_linked_list(head-next, tail);head-next p2;return p1;
}void test_case_01()
{Node * a1 new Node(10);Node * a2 new Node(5);Node * a3 new Node(8);Node * a4 new Node(20);Node * a5 new Node(26);Node * a6 new Node(18);a1-next a2;a2-next a3;a3-next a4;a4-next a5;a5-next a6;print_linked_list(a1);Node * h quick_sort_singly_linked_list(a1, nullptr);print_linked_list(h);delete_linked_list(h);
}int main()
{test_case_01();return 0;
}(END)
