时间戳

首页 > 解决方案 > 如何在合并排序和插入排序之间进行选择？

c - 如何在合并排序和插入排序之间进行选择？

问题描述

我需要实现最快的排序算法来对使用标准输入创建的链表进行排序。

我知道合并排序的时间复杂度是 O(n logn) 而插入排序的时间复杂度是 O(n^2) （是链表中元素的数量）。

但是列表是由标准输入创建的，所以在未排序的列表上使用合并排序更有效还是通过插入排序创建列表更有效，这意味着在输入上对列表进行排序？

这是结构：

#define SIZE 50

struct node {
   int num;
   char name[SIZE];
   struct node* next;
};

这些是排序标准：

1. Sorted alphabetically by "name".
2. When the name is the same it's sorted by "num" (from higher to lower).

标签： csortingmergesortinsertion-sort

解决方案

事实上，插入排序是一种在线算法，而合并排序是一种离线算法。然而：

并非每个离线算法都有有效的在线算法。

这也是这里的情况。

当数据已经部分排序时，您应该更喜欢插入排序而不是合并排序，因为前者是一种自适应算法。

注意：对于小型输入，插入排序也是首选。

推荐阅读