链接列表插入排序

我在编程的排序部分还不是很先进，所以我正在寻找我的算法的一些帮助。

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 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

我不知道为什么……我在纸上玩了很多电脑，我觉得它应该有用……但也许其他人会发现问题。

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

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