网上做兼职网站有哪些/培训网

插入排序 O(n^2)

利用vector来进行插入排序，这里展示了较标准的插入排序

leetcode执行16ms的实例

1.从链表中的第二个节点和第一个节点比，如果小于，就得插入到链表头，这里可以创建哑头部来简化操作
2.从链表中把要插入的节点取出后，从哑头部遍历该插入的位置（由于需要知道待插入位置的前驱，就必须从哑头部开始，并判别其后继的值）

ListNode* insertionSortList(ListNode* head) {if(head == nullptr) return nullptr;int len = 0;ListNode* last = head; //判断第二个节点与其前驱值的大小，我们必须知道其前驱ListNode* dummy = new ListNode(0); //创建哑头部，用于便利处理插入头部的情况dummy->next = head;while(last->next){if(last->next->val >= last->val){ //后一个比较大，不必排序  必须用第二个元素和前一个比较last = last->next;}else{//为了应对插入的可能是头部，需要从哑头部开始ListNode* cur = dummy;while(cur->next->val < last->next->val) cur = cur->next;//去除需要插入的节点ListNode* aim = last->next;last->next = aim->next;//插入新位置aim->next = cur->next;cur->next = aim;}}return dummy->next;}

归并排序 O(nlgn)
对数组做归并排序的空间复杂度为 O(n)，分别由新开辟数组O(n)和递归函数调用O(logn)组成，而根据链表特性：数组额外空间：链表可以通过修改引用来更改节点顺序，无需像数组一样开辟额外空间；递归额外空间：递归调用函数将带来O(logn)O(logn)的空间复杂度，因此若希望达到O(1)O(1)空间复杂度，则不能使用递归。
通过递归实现链表归并排序，有以下两个环节：

1. 分割 cut 环节： 找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。找到中点 slow 后，执行 slow.next = None 将链表切断。递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。cut 递归终止条件： 当head.next == None时，说明只有一个节点了，直接返回此节点。
2. 合并 merge 环节： 将两个排序链表合并，转化为一个排序链表。双指针法合并，建立辅助ListNode h 作为头部。设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。返回辅助ListNode h 作为头部的下个节点 h.next。时间复杂度 O(l + r)，l, r 分别代表两个链表长度。
3. 截止条件：当题目输入的 head == None 时，直接返回None。
   

class Solution {public ListNode sortList(ListNode head) {if (head == null || head.next == null)return head;ListNode fast = head.next, slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}ListNode tmp = slow.next;slow.next = null;ListNode left = sortList(head);ListNode right = sortList(tmp);ListNode h = new ListNode(0);ListNode res = h;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 ? left : right;return res.next;}
}

ListNode* sortList(ListNode* head) {//截止条件：head为零或者head只有一个节点if(head == nullptr || head->next == nullptr) return head;//拆分//偶数个节点，slow指向中点右侧，奇数个节点，slow指向中间节点的下一个节点//ListNode* fast = head;//ListNode* slow = head;//while(fast){//fast = fast->next;//slow = slow->next;//if(fast == nullptr) break;//fast = fast->next;//}//这里需要的是偶数个节点，slow指向中点左侧，奇数个节点，slow指向中间节点，可以方便断链ListNode* fast = head->next;ListNode* slow = head;while(fast != nullptr && fast->next != nullptr){slow = slow->next;fast = fast->next->next;}ListNode* tmp = slow->next;slow->next = nullptr;ListNode* left = sortList(head);ListNode* right = sortList(tmp);//合并 外排 利用哑头部ListNode dummyhead(0);ListNode* dummytail = &dummyhead;while(left != nullptr && right != nullptr){if(left->val < right->val){dummytail->next = left;left = left->next;}else{dummytail->next = right;right = right->next;}dummytail = dummytail->next;}dummytail->next = (left == nullptr ? right : left);return dummyhead.next;}

归并排序（从底至顶直接合并） 此方法时间复杂度O(nlogn)，空间复杂度O(1)。

1. 对于非递归的归并排序，需要使用迭代的方式替换cut环节：我们知道，cut环节本质上是通过二分法得到链表最小节点单元，再通过多轮合并得到排序结果。
2. 每一轮合并merge操作针对的单元都有固定长度intv，例如：第一轮合并时intv = 1，即将整个链表切分为多个长度为1的单元，并按顺序两两排序合并，合并完成的已排序单元长度为2。第二轮合并时intv = 2，即将整个链表切分为多个长度为2的单元，并按顺序两两排序合并，合并完成已排序单元长度为4。以此类推，直到单元长度intv >= 链表长度，代表已经排序完成。
3. 根据以上推论，我们可以仅根据intv计算每个单元边界，并完成链表的每轮排序合并，例如:当intv = 1时，将链表第1和第2节点排序合并，第3和第4节点排序合并，……当intv = 2时，将链表第1-2和第3-4节点排序合并，第5-6和第7-8节点排序合并，……。当intv = 4时，将链表第1-4和第5-8节点排序合并，第9-12和第13-16节点排序合并，……。
   
   算法流程，模拟上述的多轮排序合并：
4. 统计链表长度length，用于通过判断intv < length判定是否完成排序；
5. 额外声明一个节点res，作为头部后面接整个链表，用于：intv *= 2即切换到下一轮合并时，可通过res.next找到链表头部h；执行排序合并时，需要一个辅助节点作为头部，而res则作为链表头部排序合并时的辅助头部pre；后面的合并排序可以将上次合并排序的尾部tail用做辅助节点。
6. 在每轮intv下的合并流程：根据intv找到合并单元1和单元2的头部h1, h2。由于链表长度可能不是2^n，需要考虑边界条件：在找h2过程中，如果链表剩余元素个数少于intv，则无需合并环节，直接break，执行下一轮合并；若h2存在，但以h2为头部的剩余元素个数少于intv，也执行合并环节，h2单元的长度为c2 = intv - i。合并长度为c1, c2的h1, h2链表，其中：合并完后，需要修改新的合并单元的尾部pre指针指向下一个合并单元头部h。（在寻找h1, h2环节中，h指针已经被移动到下一个单元头部）。合并单元尾部同时也作为下次合并的辅助头部pre。当h == None，代表此轮intv合并完成，跳出。
7. 每轮合并完成后将单元长度×2，切换到下轮合并：intv *= 2。

ListNode* cut(ListNode* head, int n){ListNode* ptr = head;while(--n && ptr){ptr = ptr->next;}if(!ptr) return nullptr;  //如果数量不足以划分，就返回nullptrListNode* next = ptr->next;   //p是指向前链表的尾节点ptr->next = nullptr;return next;}//利用哑头节点进行外排ListNode* merge(ListNode* l1, ListNode* l2){ListNode dummyHead(0);ListNode* dummyTail = &dummyHead;while(l1&&l2){if(l1->val < l2->val){dummyTail->next = l1;l1 = l1->next;}else{dummyTail->next = l2;l2 = l2->next;}dummyTail=dummyTail->next;}dummyTail->next = (l1 == nullptr ? l2 : l1);return dummyHead.next;}ListNode* sortList(ListNode* head) {//非递归方式//使用哑头部ListNode dummyHead(0);dummyHead.next = head;//统计链表长度ListNode* ptr = head;int length = 0;while(ptr){length++;ptr = ptr->next;}for(int intv = 1; intv < length; intv <<= 1){ListNode* cur = dummyHead.next;ListNode* tail = &dummyHead;while(cur){ListNode* left = cur;ListNode* right = cut(left,intv); //left->@ right->@->@->@->@...cur = cut(right,intv);  //left->@ right->@ cur->@->@->@...tail->next = merge(left,right);while(tail->next){tail = tail->next;}}    }     return dummyHead.next;}