鏈接列表插入排序

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