所以我有一个任务，我给出一个随机的数字列表，我需要使用插入排序对它们进行排序。我必须使用单链表。我查看了其他帖子，但似乎没有任何帮助。我知道插入排序是什么，但我只是不知道如何用代码编写它。
Node* insertion_sort(Node* head) {
Node* temp = head_ptr;
while((head->n < temp->n) && (temp != NULL))
temp = temp->next;
head->next = temp->next;
temp->next = head;
head->prev = temp;
}
我不知道这是否正确或现在该怎么做
让我们考虑一下插入排序是如何工作的：它（理论上）将列表“拆分”为三组：已排序的子集（可能为空）、当前项和未排序的子集（可能为空）。当前项目之前的所有内容都已排序。当前项目之后的所有内容可能会或可能不会排序。该算法检查当前项目，将其与下一个项目进行比较。请记住，当前项之后的第一项属于未排序的子集。
假设您正在按升序对整数进行排序（因此给定“3,1,5,2,4”，您希望得到“1,2,3,4,5”）。您将当前项目设置为列表中的第一项。现在开始排序：
如果下一项大于当前项，则不需要对该项进行排序。只需将其设为“当前项目”并继续。
如果下一项小于当前项，那么您还有一些工作要做。首先，将下一项保存在某处——比如说在一个名为 temp 的指针中——然后通过使 current->next = current->next->next 从列表中“删除”下一项。现在，您需要为删除的项目找到正确的位置。您可以通过两种方式做到这一点：
您继续此过程，直到到达列表的末尾。一旦你到达它，你就知道你已经完成了插入排序并且列表处于正确的排序顺序。
我希望这有帮助。
struct node {
int data;
struct node *next;
};
void insertion(struct node **head) {
if((*head)== NULL || (*head)->next == NULL) {
return;
}
struct node *t1 = (*head)->next;
while(t1 != NULL) {
int sec_data = t1->data;
int found = 0;
struct node *t2 = *head;
while(t2 != t1) {
if(t2->data > t1->data && found == 0) {
sec_data = t2->data;
t2->data = t1->data;
found = 1;
t2 = t2->next;
} else {
if(found == 1) {
int temp = sec_data;
sec_data = t2->data;
t2->data = temp;
}
t2 = t2->next;
}
}
t2->data = sec_data;
t1 = t1->next;
}
}
这是链表上插入排序的Java实现：
- 时间复杂度：O(n^2)
- 空间复杂度：O(1) - 插入排序是就地排序算法
class Solution
{
public ListNode insertionSortList(ListNode head)
{
// Initialize partially sorted list
ListNode dummy = new ListNode(0), prev = dummy, current = head;
while(current != null)
{
if(prev.val > current.val)
prev = dummy;
// Find the right place to insert current node
while(prev.next != null && prev.next.val < current.val)
prev = prev.next;
// Insert current between prev and prev.next
ListNode nextNode = current.next;
current.next = prev.next;
prev.next = current;
current = nextNode;
}
return dummy.next;
}
}
哇，我肯定迟到了派对吧？无论如何，我想在回答这个问题时投入两分钱。根据您提供示例代码的方式，我将假设以下内容：
首先，我将要给你的答案使用我喜欢称之为双指针技术的方法！您使用双指针来帮助您同时引用两个变量，这样您就可以在到达nullptr时避免复杂的测试用例。
好吧，好吧...我通过调用指针对指针 双指针来快速输球，我可能会通过将其称为技术来拉扯你的腿！如果您掌握了指针的概念，那么我将要向您展示的内容应该是微不足道的。我将指针对指针称为一种技术，因为很少有人谈论它或在他们的示例源代码中使用它！以下链接将带您进入 Semmy Purewal 创建的博客，该博客更详细地讨论了这个概念！
forward_list *insertion_sort( forward_list *head )
{
/// Ensure provided linked list is not empty and has more than one element...
if( head == nullptr || head -> next == nullptr )
{
std::cout << "Error: empty or single element linked list provided!\n";
return;
}
/// Initialize separate variable the houses a growing sorted output...
forward_list *sorted = nullptr;
/// Traverse provided singly linked list...
while( head != nullptr )
{
/// Remember current head before popping it off...
forward_list *current_head = head;
/// Double pointer for effective splicing of unsorted singly linked list...
forward_list **trail = &sorted;
/// Now we pop off the current head...
head = head -> next;
/// Iterate through our growing sorted output to figure out where we need to the head...
while( ( *trail ) != nullptr && ( *trail ) -> data > current_head -> data )
{
/// Head does not belong in this current position, move on!
trail = &( *trail ) -> next;
}
/// Insert the head and update our growing sorted output to point to the head...
current_head -> next = ( *trail );
( *trail ) = current_head;
}
/// Return our sorted output...
return sorted;
}
好了，您现在有了一个插入排序的示例实现，它在单链表上运行得非常好！这个实现没有nullptr的混乱测试用例，因为我们使用了一个名为trail的双指针，它跟踪自身和指向我们不断增长的排序输出的指针。因此，当算法遍历排序后的输出时，变量trail在nullptr处被取消引用，它保存最后一个节点的next指针！
总而言之，我希望你发现这个答案既有帮助又有可读性！我知道这个问题是七年前提出的，一年前才活跃，但我希望有人觉得这有点用。咳咳，那我就上路了！
想想这个 - 如果列表是空的，temp最初会是NULL，所以当你这样做时你会得到未定义的行为temp->next = head;。
尝试一些调试，它肯定会有所帮助。您可能还想保留前一个节点，以便之后插入，或者向前看 2 个节点。
我使用类而不是结构对其进行了编码。可以进行更改，但算法将相同。创建节点类和单链表的代码..
#include<iostream>
using namespace std;
class node{
public:
int data;
node* next;
};
class list{
node* head;
public:
list() {
head=NULL;
}
void add(int el) {
node* newNode=new node();
newNode->data=el;
newNode->next=NULL;
if(head==NULL) {
head=newNode;
} else {
node* temp=head;
while(temp->next!=NULL) {
temp=temp->next;
}
temp->next=newNode;
}
}
//Insertion sort code
void insertionSort() {
node* i=head->next;
while (i!=NULL)
{
node* key=i;
node* j=head;
while (j!=i)
{
if (key->data<j->data)
{
int temp=key->data;
key->data=j->data;
j->data=temp;
}
j=j->next;
}
i=i->next;
}
}
void display() {
node* temp=head;
while (temp!=NULL) {
cout<<temp->data<<" ";
temp=temp->next;
}
}
};
用于创建主要：
int main()
{
list l;
l.add(2);
l.add(6);
l.add(0);
l.add(3);
l.add(7);
l.add(4);
l.insertionSort();
l.display();
}
如果不工作或插入排序的标准没有正确实施，请纠正我。
void linked_list::insertion_sort() {
node * p = head;
node * currentNode = head->next; // The node that is being compared at the moment.
node * previousNode = head; // The node previous to the node being compared at the moment.
//We can return from the sorting if the length of the linked list is less than 2.
if (p == nullptr || p->next == nullptr) {
return;
}
while (currentNode != nullptr) {
//If the current node is larger than or equal to the largest element of the sorted linked list on the left, we can move to the next element.
//Helpful for an already sorted array.
if(previousNode->value<=currentNode->value){
currentNode = currentNode->next;
previousNode = previousNode->next;
}
else{
//If the element is the smaller than the head element we need to take care of the head element.
if (head->value > currentNode->value) {
previousNode->next = currentNode->next;
currentNode->next = head;
head = currentNode;
}else {
p = head;
while (p->next != NULL && p->next->value < currentNode->value) {
p = p->next;
}
previousNode->next = currentNode->next;
currentNode->next = p->next;
p->next = currentNode;
}
}
currentNode = previousNode->next;
}
}