单链表快速排序的 Java 程序
原文:https://www . geesforgeks . org/Java-program-for-quick sort-on-single-link-list/
在双链表上快速排序在这里讨论。单链表上的快速排序是作为练习给出的。关于实现的重要事情是，它改变指针而不是交换数据，并且时间复杂度与双链表的实现相同。
在分区()中，我们将最后一个元素视为轴心。我们遍历当前列表，如果一个节点的值大于 pivot，我们将它移到 tail 之后。如果节点的值较小，我们会将其保持在当前位置。
在quick sort recursive()中，我们首先调用 partition()将 pivot 放在正确的位置并返回 pivot。在枢轴被放置在正确的位置之后，我们找到左侧(枢轴之前的列表)的尾部节点，并为左侧列表重现。最后，我们重现正确的列表。
Java 语言(一种计算机语言，尤用于创建网站)
// Java program for Quick Sort on
// Singly Linked List
// Sort a linked list using
// quick sort
public class QuickSortLinkedList
{
static class Node
{
int data;
Node next;
Node(int d)
{
this.data = d;
this.next = null;
}
}
Node head;
void addNode(int data)
{
if (head == null)
{
head = new Node(data);
return;
}
Node curr = head;
while (curr.next != null)
curr = curr.next;
Node newNode = new Node(data);
curr.next = newNode;
}
void printList(Node n)
{
while (n != null)
{
System.out.print(n.data);
System.out.print(" ");
n = n.next;
}
}
// Takes first and last node,
// but do not break any links in
// the whole linked list
Node paritionLast(Node start,
Node end)
{
if (start == end ||
start == null ||
end == null)
return start;
Node pivot_prev = start;
Node curr = start;
int pivot = end.data;
// Iterate till one before the end,
// no need to iterate till the end
// because end is pivot
while (start != end)
{
if (start.data < pivot)
{
// Keep tracks of last
// modified item
pivot_prev = curr;
int temp = curr.data;
curr.data = start.data;
start.data = temp;
curr = curr.next;
}
start = start.next;
}
// Swap the position of curr i.e.
// next suitable index and pivot
int temp = curr.data;
curr.data = pivot;
end.data = temp;
// Return one previous to current
// because current is now pointing
// to pivot
return pivot_prev;
}
void sort(Node start, Node end)
{
if(start == null ||
start == end||
start == end.next )
return;
// Split list and partion recurse
Node pivot_prev = paritionLast(start, end);
sort(start, pivot_prev);
// If pivot is picked and moved to the start,
// that means start and pivot is same
// so pick from next of pivot
if (pivot_prev != null &&
pivot_prev == start)
sort(pivot_prev.next, end);
// If pivot is in between of the list,
// start from next of pivot, since we
// have pivot_prev, so we move two nodes
else if (pivot_prev != null &&
pivot_prev.next != null)
sort(pivot_prev.next.next, end);
}
// Driver Code
public static void main(String[] args)
{
QuickSortLinkedList list =
new QuickSortLinkedList();
list.addNode(30);
list.addNode(3);
list.addNode(4);
list.addNode(20);
list.addNode(5);
Node n = list.head;
while (n.next != null)
n = n.next;
System.out.println(
"Linked List before sorting");
list.printList(list.head);
list.sort(list.head, n);
System.out.println(
"Linked List after sorting");
list.printList(list.head);
}
}
// This code is contributed by trinadumca
输出:
Linked List before sorting
30 3 4 20 5
Linked List after sorting
3 4 5 20 30
详情请参考单链表快速排序整篇文章！
版权属于：月萌API www.moonapi.com，转载请注明出处
