所以，我有哪里我给一些随机列表中的任务，我需要用插入排序对它们进行排序。 我必须用一个单向链表。 我看了看周围的其他职位，但似乎没有任何帮助。 我得到了插入排序信息，但我只是不知道如何把它写在代码中。
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;
}
我不知道这是否是正确的还是现在做什么
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;
}
}
让我们想想如何插入排序的工作原理：它“分裂”（理论上）列表分成三组：排序的子集（可能为空），当前项目和未分类的子集（可能为空）。 目前项目之前万事俱备。 当前项目之后一切都可能会或可能不会进行排序。 该算法检查当前的项目，它的下一个项目进行比较。 请记住，当前项目后的第一个项目属于未分类的子集。
让我们假设你是在为了增加（所以给定“3,1,5,2,4”你想获得“1,2,3,4,5”）排序整数。 您当前的项目设置到列表中的第一项。 现在，你开始整理：
如果下一个产品比目前更大的项目，你不需要到该项目进行排序。 只是让“当前项目”，然后继续。
如果下一个项目是小于目前的项目，然后你有一些工作要做。 首先，保存在某个地方的下一个项目 - 让我们在一个指针所谓的气温说 - 然后从列表中选择“删除”的下一个项目，通过使电流 - >未来=电流 - >下一步 - >下一步。 现在，你需要找到已删除的项目正确的地方。 您可以通过两种方式来实现：
直到到达列表的末尾，你继续这一进程。 一旦达到了，你知道你已经完成了插入排序和列表是正确的排序顺序。
我希望这有帮助。
想想这一点-如果列表为空， temp最初是NULL ，所以你得到了一个未定义的行为，当你做temp->next = head; 。
尝试一些调试，它肯定会有所帮助。 你可能既要保持前一个节点为好，这样你就可以插入之后，还是看两个节点向前发展。
这里是插入排序上链表的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;
}
}
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;
}
}
