在本文中，我们将给您介绍关于C#SortedList类的详细内容，此外，我们还将为您提供关于.NET/C#–将列表转换为SortedList、.Net数据结构：ArrayList、List、HashT

在本文中，我们将给您介绍关于C# SortedList类的详细内容，此外，我们还将为您提供关于.NET / C# – 将列表转换为SortedList、.Net数据结构：ArrayList、List、HashTable、Dictionary、SortedList、SortedDictionary——速度、内存以及何时使用它们？、Algorithm - Sorting a partially sorted List、C# SortedDictionary以及SortedList的浅谈的知识。

• C# SortedList类
• .NET / C# – 将列表转换为SortedList
• .Net数据结构：ArrayList、List、HashTable、Dictionary、SortedList、SortedDictionary——速度、内存以及何时使用它们？
• Algorithm - Sorting a partially sorted List
• C# SortedDictionary以及SortedList的浅谈

C# SortedList类

using System;
using System.Collections;

namespace CollectionsApplication {

   class Program {

      static void Main(string[] args) {
         SortedList sl = new SortedList();

         sl.Add(001, Zara Ali);
         sl.Add(002, Abida Rehman);
         sl.Add(003, Joe Holzner);
         sl.Add(004, Mausam Benazir Nur);
         sl.Add(005, M. Amlan);
         sl.Add(006, M. Arif);
         sl.Add(007, Ritesh Saikia);

         if (sl.ContainsValue(Nuha Ali)) {
            Console.WriteLine(This student name is already in the list);
         } else {
            sl.Add(008, Nuha Ali);
         }

         // get a collection of the keys. 
         ICollection key = sl.Keys;

         foreach (string k in key) {
            Console.WriteLine(k + :  + sl[k]);
         }
      }
   }
}

.NET / C# – 将列表转换为SortedList

var list = new List<string>();
var sortedList = new SortedList<string,string>(list.ToDictionary(s => s));

.Net数据结构：ArrayList、List、HashTable、Dictionary、SortedList、SortedDictionary——速度、内存以及何时使用它们？

.NET 有很多复杂的数据结构。不幸的是，其中一些非常相似，我并不总是确定什么时候使用一个，什么时候使用另一个。我的大部分 C# 和 VB
书籍都在一定程度上谈到了它们，但它们从未真正深入任何真正的细节。

Array、ArrayList、List、Hashtable、Dictionary、SortedList 和 SortedDictionary 有什么区别？

哪些是可枚举的（IList – 可以执行“foreach”循环）？哪些使用键/值对（IDict）？

内存占用呢？插入速度？检索速度？

还有其他值得一提的数据结构吗？

我仍在寻找有关内存使用和速度的更多详细信息（Big-O 表示法）

答案1

在我的头顶上：

• Array* - 代表一个老式的内存数组 - 有点像普通type[]数组的别名。可以列举。不能自动生长。我会假设非常快的插入和检索速度。

• ArrayList- 自动增长的数组。增加更多开销。可以枚举，可能比普通数组慢，但仍然相当快。这些在 .NET 中被大量使用

• List- 我的最爱之一 - 可以与泛型一起使用，因此您可以拥有一个强类型数组，例如List<string>. 除此之外，行为非常像ArrayList

• Hashtable- 普通的旧哈希表。O(1) 到 O(n) 最坏的情况。可以枚举 value 和 keys 属性，并做 key/val 对

• Dictionary- 与上述相同，仅通过泛型进行强类型化，例如Dictionary<string, string>

• SortedList- 排序的通用列表。插入速度变慢，因为它必须弄清楚把东西放在哪里。可以枚举，在检索时可能相同，因为它不必求助，但删除会比普通的旧列表慢。

我倾向于一直使用List-Dictionary一旦你开始使用泛型强类型的它们，就很难回到标准的非泛型。

还有很多其他的数据结构——KeyValuePair你可以用它来做一些有趣的事情，还有一个SortedDictionary也很有用。

Algorithm - Sorting a partially sorted List

给定一个list，里面每个元素都是partially sorted的，所谓partially sorted的意思是说，每个元素距离他们sorted好后的位置在一定范围[0,k]内

set i=n-2k;

while i>=0:

    sort [i, i+2k] range of elements in List;

Time complexity: (n/k)*(2k*log2k)=O(nlgk)

解释：每次sort 2k个元素其实是保证了第[k, 2k]sort完成，好好想想。

C# SortedDictionary以及SortedList的浅谈

msdn叙述：
The SortedDictionary<TKey, TValue> generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this, it is similar to the SortedList<TKey, TValue> generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

SortedList<TKey, TValue> uses less memory than SortedDictionary<TKey,
TValue>.

SortedDictionary<TKey, TValue> has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList<TKey, TValue>.

If the list is populated all at once from sorted data, SortedList<TKey,
TValue> is faster than SortedDictionary<TKey, TValue>.
译文：
SortedDictionary<TKey, TValue>泛型类是检索O(log n)的二叉搜索树，其中n是字典中的元素数。在这里，它类似于SortedList<TKey, TValue>泛型类。这两个类有相似的对象模型，并且都有O(log n)检索。这两个类的不同之处在于内存的使用以及插入和删除的速度:
SortedList<TKey, TValue>比SortedDictionary<TKey, TValue >使用更少的内存.
SortedDictionary<TKey, TValue>对于未排序的数据O(log n)具有更快的插入和删除操作，而SortedList<TKey, TValue>的插入和删除都是O(n)
如果列表是由已排序的数据一次填充的，那么SortedList<TKey, TValue>要比SortedDictionary<TKey, TValue>快。

两者基本叙述：
SortedList：是一个已序的数组（基于KeyValuePair的数组）。基于键值排序的键值对数组，使用二分查找(log n)检索key，也可根据index检索(log 1)，add和remove都是o(n)。SortedList为了保持数组的排序，它会移动位于插入的元素位置之后的所有元素（使用Array.Copy()）,由于每次的插入都会重新排序，导致插入时的性能很差，因此并不推荐使用SortedList排序一个数组。

SortedDictionary: 是一个BST，基于二叉查找树实现，使用二分查找检索(key)，add和remove都是o(log n)

两者性能比较：

两者实现比较：

参考：
https://stackoverflow.com/questions/935621/whats-the-difference-between-sortedlist-and-sorteddictionary
https://stackoverflow.com/questions/1376965/when-to-use-a-sortedlisttkey-tvalue-over-a-sorteddictionarytkey-tvalue

今天的关于C# SortedList类的分享已经结束，谢谢您的关注，如果想了解更多关于.NET / C# – 将列表转换为SortedList、.Net数据结构：ArrayList、List、HashTable、Dictionary、SortedList、SortedDictionary——速度、内存以及何时使用它们？、Algorithm - Sorting a partially sorted List、C# SortedDictionary以及SortedList的浅谈的相关知识，请在本站进行查询。