链表的选择排序

Question

我们已经在 class 中了解了选择排序算法如何处理数组数据结构。在本实验中，我们将练习如何对链表 ADT 执行选择排序。 1.将下面的选择排序伪代码转换为升序排序。（selectionSort_asc 函数）一种。在长度为n的链表中找到最小值的节点 b.将最小节点追加到新的结果链表中 C。从原始链表中删除 min d.重复步骤a-c，直到原链表为空 e. Return结果链表 2. 将下面的选择排序伪代码转换为降序排序。（selectionSort_desc 函数）一种。在长度为n的链表中找到最大值的节点 b.在新的结果链表中追加最大节点 C。从原始链表中删除 max d.重复步骤a-c，直到原链表为空 e. Return结果链表

我试过下面这段代码，但它没有给我正确的输出。

public class Sort {
    public static void main(String[] args){
        Node head = initializeList("ilovedata"); 
        System.out.println("\n List Before selectionSort_asc");
        printList(head);
        head = selectionSort_asc(head);
        System.out.println("\n List After selectionSort_asc");
        printList(head);
        // Expected answer: -> a -> a -> d -> e -> i -> l -> o -> t -> v
        head = initializeList("ilovedata"); 
        System.out.println("\n List Before selectionSort_desc");
        printList(head);
        head = selectionSort_desc(head);
        System.out.println("\n List After selectionSort_desc");
        printList(head);
        // Expected answer: -> v -> t -> o -> l -> i -> e -> d -> a -> a
        }
        public static Node selectionSort_asc(Node head){ 
            Node result = null;

            Node curr, prev, min;
            while(head!=null) {
                curr = head;
                prev = null;
                min = head;
                while(curr.next!=null) {
                    curr = curr.next;
                    if(curr.item<min.item) {
                        prev = min;
                        min = curr;
                    }
                }
                //append the min at the end of result list
                Node add_min = new Node(min.item);
                if(result==null)
                    result = add_min;
                else {
                    Node last = result;
                    while(last.next!=null) {
                        last = last.next;
                    }
                    last.next = add_min;
                }
                //delete the min node form original list    
                if(min==head) {
                    head = head.next;
                }
                else if(min.next==null){
                    prev.next = null;
                }else {
                    prev.next = prev.next.next;
                    min.next = null;
                }
            }
            return result;
        }
        public static Node selectionSort_desc(Node head){ 
            Node result = null;

            Node curr, prev, max;           
            while(head!=null) {
                curr = head;
                prev = null;
                max = head;
                //find out the max node
                while(curr.next!=null) {
                    curr = curr.next;
                    if(curr.item>max.item) {
                        prev = max;
                        max = curr;
                    }
                }
                //add max to the end of result list             
                Node add_max = new Node(max.item);
                if(result==null) {
                    result = add_max;
                }
                else {
                    Node last = result;
                    while(last.next!=null) {
                        last = last.next;
                    }
                    last.next = add_max;
                }
                //delete min from original list
                if(max == head) {
                    head = head.next;
                }
                else if(max.next==null){
                    prev.next = null;
                }
                else {
                    prev.next = max.next;
                    max.next = null;
                }

            }           
            return result;
        }
        // Method that takes a string and insert its characters into a linked list
        public static Node initializeList(String str){ 
            Node head= new Node(str.charAt(0)),cur; 
            int i;
            for(cur= head,i=1;i<str.length();i++,cur=cur.next){ 
                cur.next = new Node(str.charAt(i));
            }       
            return head;
        }
        // Method for printing linked list 
        public static void printList(Node head){
               Node cur = head;
               if(head==null) 
                   System.out.print("<EMPTY>"); 
               for(;cur!=null;cur=cur.next){
                   System.out.print("-> "+cur.item+" ");
               }
        }
}

Answer 1

问题与这些代码片段中 prev 变量的分配有关

public static Node selectionSort_asc(Node head){ 
...
    if(curr.item><min.item) {
        prev = min;
        min = curr;
    }
...
}

public static Node selectionSort_desc(Node head){ 
...
    if(curr.item>max.item) {
        prev = max;
        max = curr;
    }
...
}

您目前正在将 prev 分配给旧的 min 和旧的 max，但根据您的代码设计，您希望 prev 成为指向新 min 和新 max 之前的节点，以及从原始链表中删除 min 节点的方式。我的建议是保留另一组名为 beforeMin 和 beforeMax 的变量，并在找到新的最小值或最大值时将它们设置为等于 prev 的当前值。除此之外，您还应该在 while 循环的每次迭代中更新 prev 变量，就像您对 curr 所做的那样。这是 selectionSort_asc 的样子，您可以弄清楚如何调整降序方法以反映它：

public static Node selectionSort_asc(Node head){ 
    Node result = null;

    Node curr, prev, min, beforeMin;
    while(head!=null) {
        curr = head;
        prev = null;
        min = head;
        beforeMin = prev; // new variable
        while(curr.next!=null) {
            prev = curr; // update prev with each iteration
            curr = curr.next;
            if(curr.item<min.item) {
                beforeMin = prev; // variable points to the node before the min node
                min = curr;
            }
        }
        //append the min at the end of result list
        Node add_min = new Node(min.item);
        if(result==null)
            result = add_min;
        else {
            Node last = result;
            while(last.next!=null) {
                last = last.next;
            }
            last.next = add_min;
        }
        //delete the min node form original list    
        if(min==head) {
            head = head.next;
        }
        else if(min.next==null){
            beforeMin.next = null; // no more prev here
        }else {
            beforeMin.next = beforeMin.next.next; // notice how beforeMin is used now
            min.next = null;
        }
    }
    return result;
}

链表的选择排序

Selection sort for linked list

java

singly-linked-list

selection-sort