链表插入排序

Question

我在编程的排序部分还不是很高级，所以我在寻找一些关于我的算法的帮助。

void sortList()
{
    Item_PTR tmpNxt = current->nextItem;
    Item_PTR tmpPTR = current;
    int a, tmp;

    while(tmpNxt != NULL)
    {   
        a = tmpPTR->value;
        while(tmpNxt != tmpPTR && tmpNxt->value < a)
        {
            tmp = a;
            tmpPTR->value = tmpNxt->value;
            tmpNxt->value = tmp;
            tmpPTR = tmpPTR->nextItem;
        }
        tmpPTR = current;   
        tmpNxt = tmpNxt->nextItem;
    }

}

排序前列表状态:9 8 7 6 5 4 3 2 1排序后:1 9 8 7 6 5 4 3 2

我不知道为什么…我在纸上玩了很多次电脑，我觉得它应该work...but，也许其他人的眼睛会发现问题。

Current是一个全局指针，它将始终具有列表中第一个/顶部元素的位置。

Answer 1

这是因为函数sortList() is not current，"global“变量表示表头。

请不要使用全局变量，当然也不要使用链表头部。(当你需要两个列表时，你会怎么做？)

我会将sortList()函数重新设计为以下两种之一：

/* sort the list pointed to by phead and return the new head after sorting */
Item_PTR sortList( Item_PTR phead );

/* sort the list pointed to by *pphead */
void sortList( Item_PTR * pphead );

此外，要熟悉C++列表标准库std::list link的接口(即使您不能在直接项目中使用它们

Answer 2

除了@Arun Saha建议的更改之外，似乎还有一些逻辑错误(交换后没有更新值)，这就是为什么列表甚至在排序函数中都不能按排序顺序打印的原因。下面的代码应该可以解决这个问题。

void sortList()
{
    Item_PTR tmpNxt = current->nextItem;
    Item_PTR tmpPTR = current;

    while(tmpNxt != NULL)
    {   
        while(tmpNxt != tmpPTR && tmpNxt->value < tmpPTR->value)
        {
            int tmp = tmpPTR->value;
            tmpPTR->value = tmpNxt->value;
            tmpNxt->value = tmp;
            tmpPTR = tmpPTR->nextItem;
        }
        tmpPTR = current;   
        tmpNxt = tmpNxt->nextItem;
    }

}

Answer 3

         **Java code for insertion sort of linked list**





    package LinkedList;

/**
 * Created by dheeraj on 5/1/15.
 */
public class InsertionSortLinkedList {

    private static final class Node {
        int value;
        Node next;

        public Node(int d) {
            value = d;
            next = null;
        }
    }

    private Node root;
    private Node sortedHead;

    private void addData(int data) {
        if (root == null) {
            root = new Node(data);
        } else {
            Node temp = new Node(data);
            temp.next = root;
            root = temp;
        }
    }

    private void printList() {
        Node temp = root;
        while (temp != null) {
            System.out.print(temp.value + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    private void printSortedList() {
        Node temp = sortedHead;
        while (temp != null) {
            System.out.print(temp.value + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    private void insertionSort() {
        Node outer = root;
        Node resultRoot = null;
        if (outer == null) {
            return;
        }
        while (outer != null) {
            if (resultRoot == null) {
                //System.out.println("null");
                resultRoot = new Node(outer.value);
            } else {
                Node t = resultRoot;
                if (outer.value < t.value) {
                    //current outer is smallest
                    //System.out.println("smallest");
                    Node temp = new Node(outer.value);
                    temp.next = t;
                    resultRoot = temp;
                } else {
                    boolean broken = false;
                    while (t.next != null) {
                        if (t.value < outer.value && outer.value <= t.next.value) {
                            Node temp = new Node(outer.value);
                            temp.next = t.next;
                            t.next = temp;
                            broken = true;
                            //System.out.println("middle");
                            break;
                        }
                        //
                        t = t.next;
                    }
                    if (!broken) {
                        //current outer is greatest
                        //System.out.println("largest");
                        t.next = new Node(outer.value);
                    }
                }
            }
            outer = outer.next;
        }
        sortedHead = resultRoot;
    }

    public static void main(String[] args) {
        InsertionSortLinkedList insertionSortLinkedList = new InsertionSortLinkedList();
        insertionSortLinkedList.addData(5);
        insertionSortLinkedList.addData(30);
        insertionSortLinkedList.addData(1);
        insertionSortLinkedList.addData(18);
        insertionSortLinkedList.addData(19);

        insertionSortLinkedList.printList();
        insertionSortLinkedList.insertionSort();
        insertionSortLinkedList.printSortedList();
    }
}