链接列表插入排序

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

我不知道为什么... I”我在纸上玩过很多电脑，我觉得它应该可以工作......但也许其他人会发现问题。

当前是一个全局指针，它总是具有列表中第一个/顶部元素的位置。

Answer 1

这是因为该功能sortList()是不改变current，“全局” 变量表示的表头。

请不要使用全局变量，当然不能用于链表头。 （你会做什么，当你需要名单？）

我会重新设计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::listlink

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(); 
    } 
}