Java LambdaQueryWrapper连表查询 java对链表的数据进行排序

在最后一篇博客中，它解释了九种内部排序算法，一些算法也提供了代码实现，但这些代码实现是基于数组排序的。本博客通过链表排序为读者实现了几种常见的排序算法。

实现链表的快速排序

算法思想：对于链表，以head节点的值作为key，然后通过节点，可以得到小于key的链表和大于等于key的链表；因此，递归可以分别快速执行两个链表。这里使用了快速排序的想法，即在排序后，可以将小于key的元素放在一边，并将大于等于key的元素放在另一边。

代码实现：

1     //快速排序 2     public static void quickSort(ListNode begin, ListNode end){ 3         if(begin == null || begin == end) 4             return; 5          6         ListNode index = paration(begin, end); 7         quickSort(begin, index); 8         quickSort(index.next, end); 9     }10     11     /**12      * 划分函数，以头结点值为基准元素划分13      * @param begin14      * @param end15      * @return16      */17     public static ListNode paration(ListNode begin, ListNode end){18         if(begin == null || begin == end)19             return begin;20         21         int val = begin.val;  ///基准元素22         ListNode index = begin, cur = begin.next;23         24         while(cur != end){25             if(cur.val < val){  //交换26                 index = index.next;27                 int tmp = cur.val;28                 cur.val = index.val;29                 index.val = tmp;30             }31             cur = cur.next;32         }33         34         35         begin.val = index.val;36         index.val = val;37         38         return index;39     }

实现链表的合并排序

算法理念：与数组相比，单链表只能按顺序访问每个元素。因此，在使用二路并购排序时，关键是找到链表的中间结点，将链表分为两个部分：您可以同时使用快速和慢速指针来访问单链表。当步长为2的指针指向链表的最后一个结点或最后一个结点的下一个结点时，步长为1的指针指向链表的中间结点。然后是两个有序单链表的合并。时间复杂度为O(N*logN)，O(1)空间复杂度。

代码实现：

1     ///合并排序 2     public static ListNode mergeSort(ListNode head){ 3         if(head == null || head.next == null)  //空链表或只有单个结点 4             return head; 5         ListNode slow = head, fast = head.next; 6          7         while(fast != null && fast.next != null){  ///用快慢指针寻找中间指针 结点 8             slow = slow.next; 9             10             fast = fast.next;11             if(fast.next != null)12                 fast = fast.next;        13         }14         15         ListNode ptr1 = slow.next;16         slow.next = null;17         18         ListNode tmp1 = mergeSort(head);19         ListNode tmp2 = mergeSort(ptr1);20         return merge(tmp1, tmp2);21     }22     23     24     public static ListNode merge(ListNode start1，  ListNode start2{25         ListNode header = new ListNode(-1);26         ListNode pre = header;27         28         ListNode ptr1 = start1， ptr2 = start2;29         while(ptr1 != null && ptr2 != null){30             if(ptr1.val <= ptr2.val){31                 pre.next = ptr1;32                 pre = ptr1;33                 ptr1 = ptr1.next;34             }else{35                 pre.next = ptr2;36                 pre = ptr2;37                 ptr2 = ptr2.next;38             }39         }40         while(ptr1 != null){41             pre.next = ptr1;42             pre = ptr1;43             ptr1 = ptr1.next;44         }45         46         while(ptr2 != null){47             pre.next = ptr2;48             pre = ptr2;49             ptr2 = ptr2.next;50         }51         52         53         return header.next;54         55     }

实现了冒泡排序链表

算法思想：依次相邻的结点，如果是逆序，则交换两个结点

代码实现：

1     //冒泡排序 2     public static ListNode bubbleSort(ListNode head){ 3         if(head == null || head.next == null)  //链表是空的，或者只有一个结点 4             return head; 5          6         ListNode cur = null, tail = null; 7          8         cur = head; 9         10         while(cur.next != tail){11             while(cur.next != tail){12                 if(cur.val > cur.next.val){13                     int tmp = cur.val;14                     cur.val = cur.next.val;15                     cur.next.val = tmp;16                 }17                 cur = cur.next;18             }19             20             tail = cur;  ///下一次遍历的结尾点是当前的结点(仔细想想里面的道路)21             cur = head;     ////遍历起始结点重置为头结点    22         }23         24         return head;25         26         27     }

先写这些，再想想。。。

本文是转载内容，我们尊重原作者对文章的权利。如有内容错误或侵权行为，请联系我们更正或删除文章。