如何使用LinkedList实现归并排序?
How to implement merge sort using LinkedList?
我正在尝试使用 LinkedList 实现合并排序,到目前为止,
class Node{
Node next;
int data;
public Node (){
}
public Node(int _data){
this.data = _data;
}
}
public class myTest{
private static Node head;
private static Node current;
public void myTest(){
this.head = null;
this.current = null;
}
public static void insert( int data ){
Node newNode = new Node(data);
if (head == null){
head = newNode;
current = head;
}
else {
current.next = newNode;
current = newNode;
}
}
public static void display(Node cur ){
while( cur != null){
if (cur.next != null){
System.out.print(cur.data + " -> ");
}
else{
System.out.print(cur.data +" ");
}
cur = cur.next;
}
System.out.println();
}
private static Node mergeSort(Node headOriginal ){
if (headOriginal == null || headOriginal.next == null ){
return headOriginal;
}
Node a = headOriginal;
Node b = headOriginal.next;
while( b != null && b.next != null ){
headOriginal = headOriginal.next;
b = (b.next).next;
}
// split in 2 parts
b = headOriginal.next;
headOriginal.next = null;
return merge( mergeSort(a), mergeSort(b) );
}
// sort among the 2 parts
public static Node merge(Node a, Node b) {
Node c = new Node();
Node head_1 = c;
while ((a != null) && (b != null)) {
if ( a.data <= b.data ){
c.next = a;
c = a;
a = a.next;
}
else {
c.next = b;
c = b;
b = b.next;
}
}
c.next = (a == null) ? b : a;
return head_1.next;
}
public static void main(String[] args ){
int [] arr = {12, 34, 5, 6, 7};
for (int j =0; j < arr.length; j++){
insert( arr[j] );
}
mergeSort(head);
display(head);
}
}
mergeSort 函数采用从 生成的 LikedList 的原始头部插入 函数。我相信该函数正确地创建了一个升序排序的 LL。 display 函数假设打印 LL。在这种情况下,它仅从原始头 (12) 打印到已排序 LL 的末尾并打印 '12->34' 。我假设如果我可以通过新创建的排序 LL 的头部,它将能够打印整个排序的 LL。
- 我的程序没问题还是需要一些改进才能实现归并排序?
- 如何让已排序的 LL 的头部在 display 方法中传递?
我想这是出于学术目的,因为 Sandeep 的评论是正确的,即 LinkedList 不是适合归并排序的数据结构。并且编写自己的链表也可能不是一个好主意,因为 Java API 数据结构经过精心设计和测试!
但是对于您的代码,它工作得非常好!唯一的错误是您没有使用合并排序的结果,而是使用了对 head 的 "old" 引用。如果你更新你的参考应该没问题。尝试:
head = mergeSort(head);
display(head);
在您的主要方法中,它应该可以正常工作!
我正在尝试使用 LinkedList 实现合并排序,到目前为止,
class Node{
Node next;
int data;
public Node (){
}
public Node(int _data){
this.data = _data;
}
}
public class myTest{
private static Node head;
private static Node current;
public void myTest(){
this.head = null;
this.current = null;
}
public static void insert( int data ){
Node newNode = new Node(data);
if (head == null){
head = newNode;
current = head;
}
else {
current.next = newNode;
current = newNode;
}
}
public static void display(Node cur ){
while( cur != null){
if (cur.next != null){
System.out.print(cur.data + " -> ");
}
else{
System.out.print(cur.data +" ");
}
cur = cur.next;
}
System.out.println();
}
private static Node mergeSort(Node headOriginal ){
if (headOriginal == null || headOriginal.next == null ){
return headOriginal;
}
Node a = headOriginal;
Node b = headOriginal.next;
while( b != null && b.next != null ){
headOriginal = headOriginal.next;
b = (b.next).next;
}
// split in 2 parts
b = headOriginal.next;
headOriginal.next = null;
return merge( mergeSort(a), mergeSort(b) );
}
// sort among the 2 parts
public static Node merge(Node a, Node b) {
Node c = new Node();
Node head_1 = c;
while ((a != null) && (b != null)) {
if ( a.data <= b.data ){
c.next = a;
c = a;
a = a.next;
}
else {
c.next = b;
c = b;
b = b.next;
}
}
c.next = (a == null) ? b : a;
return head_1.next;
}
public static void main(String[] args ){
int [] arr = {12, 34, 5, 6, 7};
for (int j =0; j < arr.length; j++){
insert( arr[j] );
}
mergeSort(head);
display(head);
}
}
mergeSort 函数采用从 生成的 LikedList 的原始头部插入 函数。我相信该函数正确地创建了一个升序排序的 LL。 display 函数假设打印 LL。在这种情况下,它仅从原始头 (12) 打印到已排序 LL 的末尾并打印 '12->34' 。我假设如果我可以通过新创建的排序 LL 的头部,它将能够打印整个排序的 LL。
- 我的程序没问题还是需要一些改进才能实现归并排序?
- 如何让已排序的 LL 的头部在 display 方法中传递?
我想这是出于学术目的,因为 Sandeep 的评论是正确的,即 LinkedList 不是适合归并排序的数据结构。并且编写自己的链表也可能不是一个好主意,因为 Java API 数据结构经过精心设计和测试!
但是对于您的代码,它工作得非常好!唯一的错误是您没有使用合并排序的结果,而是使用了对 head 的 "old" 引用。如果你更新你的参考应该没问题。尝试:
head = mergeSort(head);
display(head);
在您的主要方法中,它应该可以正常工作!