在单向链表上使用插入排序

2022-01-01 00:00:00 list linked-list sorting c++ insertion-sort

所以我有一个作业，我给出了一个随机数字列表，我需要使用插入排序对它们进行排序.我必须使用单链表.我环顾了其他帖子，但似乎没有任何帮助.我知道插入排序是什么，但我只是不知道如何在代码中编写它.

So I have an assignment where I'm giving a random list of number and I need to sort them using insertion sort. I must use a singly linked list. I looked around at other posts but none seem to help. I get what insertion sort is but I just don't know how to write it in code. 

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

我不知道这是否正确或现在该怎么办

I dont know if this is right or what to do now

推荐答案

让我们考虑一下插入排序的工作原理:它将列表拆分"(理论上)三组:已排序的子集(可能为空)、当前项目和未排序的子集(可能为空).当前项目之前的所有内容都已排序.当前项目之后的所有内容可能会或可能不会被排序.该算法检查当前项目，并将其与下一个项目进行比较.请记住，当前项之后的第一项属于未排序的子集.

Let's think about how Insertion Sort works: It "splits" (in theory) the list into three groups: the sorted subset (which may be empty), the current item and the unsorted subset (which may be empty). Everything before the current item is sorted. Everything after the current item may or may not be sorted. The algorithm checks the current item, comparing it with the next item. Remember that the first item after the current item belongs to the unsorted subset.

让我们假设您按递增顺序对整数进行排序(因此给定3,1,5,2,4"，您希望得到1,2,3,4,5").您将当前项目设置为列表中的第一项.现在开始排序:

Let's assume that you are sorting integers in increasing order (so given "3,1,5,2,4" you want to get "1,2,3,4,5"). You set your current item to the first item in the list. Now you begin sorting:

如果下一项大于当前项，则不需要对该项进行排序.只需将其设为当前项目"并继续.

If the next item is greater than the current item, you don't need to sort that item. Just make it "current item" and continue.

如果下一个项目小于当前项目，那么您有一些工作要做.首先，将下一项保存在某处――假设在一个名为 temp 的指针中――然后通过使 current->next = current->next->next 从列表中删除"下一项.现在，您需要为已删除的项目找到正确的位置.您可以通过两种方式执行此操作:

If the next item is less than the current item then you have some work to do. First, save the next item somewhere - let's say in a pointer called temp - and then "remove" the next item from the list, by making current->next = current->next->next. Now, you need to find right place for the removed item. You can do this in two ways:

  1. 要么从列表的开头开始，一直向前直到找到正确的位置.完成后，您在那里插入项目并继续您的插入排序.如果您有一个单向链表，这是最简单的解决方案.
  2. 您向后退，直到找到该项目的正确位置.完成后，您在那里插入项目并继续您的插入排序.这有点复杂，但如果你有一个双向链表，它可以很好地工作.

您继续此过程，直到到达列表的末尾.到达它后，您就知道您已完成插入排序，并且列表的排序顺序正确.

You continue this process until you reach the end of the list. Once you reach it, you know that you have completed your insertion sort and the list is in the correct sorted order.

我希望这会有所帮助.

相关文章