C#数据结构与算法揭秘19

简介:

这节,我们介绍基数排序和归并排序。

一、基数排序

基数排序(Radix Sort)的设计思想与前面介绍的各种排序方法完全不同。前面介绍的排序方法主要是通过关键码的比较和记录的移动这两种操作来实现排序的,而基数排序不需要进行关键码的比较和记录的移动。基数排序是一种借助于多关键码排序的思想,是将单关键码按基数分成多关键码进行排序的方法,是一种分配排序。

下面用一个具体的例子来说明多关键码排序的思想。
一副扑克牌有 52 张牌,可按花色和面值进行分类,其大小关系如下:
花色:梅花<方块<红心<黑心
面值:2<3<4<5<6<7<8<9<10<J<Q<K<A
在对这 52 张牌进行升序排序时,有两种排序方法:
方法一:可以先按花色进行排序,将牌分为 4 组,分别是梅花组、方块组、红心组和黑心组,然后,再对这 4 个组的牌分别进行排序。最后,把 4 个组连接起来即可。
方法二:可以先按面值进行排序,将牌分为 13 组,分别是 2 号组、3 号组、4 号组、…、A 号组,再将这 13 组的牌按花色分成 4 组,最后,把这四组的牌连接起来即可。
设序列中有n个记录,每个记录包含d个关键码{k1,k2,…,kd},序列有序指的对序列中的任意两个记录ri和rj(1≤i≤j≤n) ,(ki1, ki2,…, kid)<( kj1, kj2,…, kjd) 其中,k1称为最主位关键码,kd称为最次位关键码。

其中,k1称为最主位关键码,kd称为最次位关键码。

多关键码排序方法按照从最主位关键码到最次位关键码或从最次位关键码到最主位关键码的顺序进行排序,分为两种排序方法:
(1)最高位优先法(MSD法) 。先按k1排序,将序列分成若干子序列,每个子序列中的记录具有相同的k1值;再按k2排序,将每个子序列分成更小的子序列;然后,对后面的关键码继续同样的排序分成更小的子序列,直到按kd排序分组分成最小的子序列后,最后将各个子序列连接起来,便可得到一个有序的序列。前面介绍的扑克牌先按花色再按面值进行排序的方法就是MSD法。
(2)最次位优先法(LSD法) 。先按kd排序,将序列分成若干子序列,每个子序列中的记录具有相同的kd值; 再按kd-1排序, 将每个子序列分成更小的子序列;然后,对后面的关键码继续同样的排序分成更小的子序列,直到按k1排序分组分成最小的子序列后,最后将各个子序列连接起来,便可得到一个有序的序列。前面介绍的扑克牌先按面值再花色按进行排序的方法就是LSD法。

基数的源代码如下:


//基数排序的方法
public int[] RadixSort(int[] ArrayToSort, int digit,int len)
        {
         
           // 从低位到高位的方法
            for (int k = 1; k <= digit; k++)
            {
                // 临时的数组存储里面的十进制的排序的结果
                int[] tmpArray = new int[ArrayToSort.Length];

                
                //临时的数组存储计数的结果
                int[] tmpCountingSortArray = new int[len];

                //基数的数组1            
                    for (int i = 0; i < ArrayToSort.Length; i++)
                {
                    //截取实际值   570-570/10*10
                    int tmpSplitDigit = ArrayToSort[i] / (int)Math.Pow(10, k - 1) - (ArrayToSort[i] / (int)Math.Pow(10, k)) * 10;
                    tmpCountingSortArray[tmpSplitDigit] += 1;
                }

                for (int m = 1; m < 10; m++)
                {
                    tmpCountingSortArray[m] += tmpCountingSortArray[m - 1];
                }

                //   输出的结果
                for (int n = ArrayToSort.Length - 1; n >= 0; n--)
                {
                    int tmpSplitDigit = ArrayToSort[n] / (int)Math.Pow(10, k - 1) - (ArrayToSort[n] / (int)Math.Pow(10, k)) * 10;
                    tmpArray[tmpCountingSortArray[tmpSplitDigit] - 1] = ArrayToSort[n];
                    tmpCountingSortArray[tmpSplitDigit] -= 1;
                }

                //  拷贝排序的数组
                for (int p = 0; p < ArrayToSort.Length; p++)
                {
                    ArrayToSort[p] = tmpArray[p];
                }
            }

            return ArrayToSort;
        }
//双层的循环    时间的复杂度是O(n2)

      如图所示:

基数排序是稳定的排序,时间的复杂度是O(n2).

二、归并排序

归并排序(merge Sort)主要是二路归并排序。二路归并排序的基本思想是:将两个有序表合并为一个有序表。
假设顺序表 sqList 中的 n 个记录为 n 个长度为1的有序表,从第1个有序表开始,把相邻的两个有序表两两进行合并成一个有序表,得到 n/2 个长度为2的有序表。如此重复,最后得到一个长度为 n 的有序表。
一趟二路归并排序算法的实现如下所示, 算法中记录的比较代表记录关键码的比较,顺序表中只存放了记录的关键码:

对于n个记录的顺序表,将这n个记录看作叶子结点,若将两两归并生成的子表看作它们的父结点, 则归并过程对应于由叶子结点向根结点生成一棵二叉树的过程。所以,归并趟数约等于二叉树的高度减1,即log2n,每趟归并排序记录关键码比较的次数都约为n/2,记录移动的次数为2n(临时顺序表的记录复制到原顺序表中记录的移动次数为n) 。 因此, 二路归并排序的时间复杂度为O (nlog2n) 。
而二路归并排序使用了n个临时内存单元存放记录,所以,二路归并排序算法的空间复杂度为O(n) 。归并排序,如图所示:

一趟二路归并排序算法的实现如下所示, 算法中记录的比较代表记录关键码的比较,顺序表中只存放了记录的关键码,相应的源代码如下:


public void Merge(SeqList<int> sqList, int len) 
   { 
        int m = 0;                 //临时顺序表的起始位置 
int l1 = 0;                 //第1个有序表的起始位置 
        int h1;                    //第1个有序表的结束位置 
int l2;                    //第2个有序表的起始位置 
int h2;                     //第2个有序表的结束位置 
        int i = 0; 
int j = 0;  
 
        //临时表,用于临时将两个有序表合并为一个有序表 
        SeqList<int> tmp = new SeqList<int>(sqList.GetLength()); 
 
       //归并处理 
        while (l1 + len < sqList.GetLength()) 
       {    
           l2 = l1 + len;           //第2个有序表的起始位置 
           h1 = l2 - 1;             //第1个有序表的结束位置 
 
          //第2个有序表的结束位置 
           h2 = (l2 + len - 1 < sqList.GetLength())  
? l2 + len - 1 : sqList.Last; 
 
           j = l2; 
           i = l1; 
 
           //两个有序表中的记录没有排序完 
           while ((i<=h1) && (j<=h2)) 
           { 
                //第1个有序表记录的关键码小于第2个有序表记录的关键码 
                if (sqList[i] <= sqList[j])     
                { 
                    tmp[m++] = sqList[i++]; 
                } 
                //第2个有序表记录的关键码小于第1个有序表记录的关键码
else 
                { 
                    tmp[m++] = sqList[j++]; 
                } 
            } 
 
            //第1个有序表中还有记录没有排序完 
            while (i <= h1) 
            { 
                tmp[m++] = sqList[i++]; 
            } 
 
            //第2个有序表中还有记录没有排序完 
            while (j <= h2) 
            { 
                tmp[m++] = sqList[j++]; 
            } 
 
            l1 = h2 + 1; 
        } 
 
        i = l1; 
        //原顺序表中还有记录没有排序完 
        while (i < sqList.GetLength()) 
        { 
            tmp[m++] = sqList[i++]; 
        } 
 
        //临时顺序表中的记录复制到原顺序表,使原顺序表中的记录有序 
       for (i = 0; i < sqList.GetLength(); ++i) 
        { 
            sqList[i] = tmp[i]; 
} 
} 
二路归并排序算法的实现如下: 
public void MergeSort(SeqList<int> sqList) 
     { 
          int k = 1;     //归并增量 
 
          while (k < sqList.GetLength()) 
          { 
               Merge(sqList, k); 
               k *= 2; 
           }
  }

对于n个记录的顺序表,将这n个记录看作叶子结点,若将两两归并生成的子表看作它们的父结点, 则归并过程对应于由叶子结点向根结点生成一棵二叉树的过程。所以,归并趟数约等于二叉树的高度减1,即log2n,每趟归并排序记录关键码比较的次数都约为n/2,记录移动的次数为2n(临时顺序表的记录复制到原顺序表中记录的移动次数为n) 。 因此, 二路归并排序的时间复杂度为O (nlog2n)。而二路归并排序使用了n个临时内存单元存放记录,所以,二路归并排序算法的空间复杂度为O(n) 。

C#数据结构,就此结束了,这是我的一点总结。


目录
相关文章
|
3月前
|
存储 运维 监控
基于 C# 语言的 Dijkstra 算法在局域网内监控软件件中的优化与实现研究
本文针对局域网监控系统中传统Dijkstra算法的性能瓶颈,提出了一种基于优先队列和邻接表优化的改进方案。通过重构数据结构与计算流程,将时间复杂度从O(V²)降至O((V+E)logV),显著提升大规模网络环境下的计算效率与资源利用率。实验表明,优化后算法在包含1000节点、5000链路的网络中,计算时间缩短37.2%,内存占用减少21.5%。该算法适用于网络拓扑发现、异常流量检测、故障定位及负载均衡优化等场景,为智能化局域网监控提供了有效支持。
84 5
|
4月前
|
存储 算法 安全
如何控制上网行为——基于 C# 实现布隆过滤器算法的上网行为管控策略研究与实践解析
在数字化办公生态系统中,企业对员工网络行为的精细化管理已成为保障网络安全、提升组织效能的核心命题。如何在有效防范恶意网站访问、数据泄露风险的同时,避免过度管控对正常业务运作的负面影响,构成了企业网络安全领域的重要研究方向。在此背景下,数据结构与算法作为底层技术支撑,其重要性愈发凸显。本文将以布隆过滤器算法为研究对象,基于 C# 编程语言开展理论分析与工程实践,系统探讨该算法在企业上网行为管理中的应用范式。
137 8
|
4月前
|
存储 监控 算法
解析公司屏幕监控软件中 C# 字典算法的数据管理效能与优化策略
数字化办公的时代背景下,企业为维护信息安全并提升管理效能,公司屏幕监控软件的应用日益普及。此软件犹如企业网络的 “数字卫士”,持续记录员工电脑屏幕的操作动态。然而,伴随数据量的持续增长,如何高效管理这些监控数据成为关键议题。C# 中的字典(Dictionary)数据结构,以其独特的键值对存储模式和高效的操作性能,为公司屏幕监控软件的数据管理提供了有力支持。下文将深入探究其原理与应用。
97 4
|
5月前
|
机器学习/深度学习 监控 算法
员工上网行为监控软件中基于滑动窗口的C#流量统计算法解析​
在数字化办公环境中,员工上网行为监控软件需要高效处理海量网络请求数据,同时实时识别异常行为(如高频访问非工作网站)。传统的时间序列统计方法因计算复杂度过高,难以满足低延迟需求。本文将介绍一种基于滑动窗口的C#统计算法,通过动态时间窗口管理,实现高效的行为模式分析与流量计数。
135 2
|
5月前
|
人工智能 运维 算法
基于 C# 深度优先搜索算法的局域网集中管理软件技术剖析
现代化办公环境中,局域网集中管理软件是保障企业网络高效运行、实现资源合理分配以及强化信息安全管控的核心工具。此类软件需应对复杂的网络拓扑结构、海量的设备信息及多样化的用户操作,而数据结构与算法正是支撑其强大功能的基石。本文将深入剖析深度优先搜索(Depth-First Search,DFS)算法,并结合 C# 语言特性,详细阐述其在局域网集中管理软件中的应用与实现。
126 3
|
3月前
|
监控 算法 数据处理
内网实时监控中的 C# 算法探索:环形缓冲区在实时数据处理中的关键作用
本文探讨了环形缓冲区在内网实时监控中的应用,结合C#实现方案,分析其原理与优势。作为固定长度的循环队列,环形缓冲区通过FIFO机制高效处理高速数据流,具备O(1)时间复杂度的读写操作,降低延迟与内存开销。文章从设计逻辑、代码示例到实际适配效果展开讨论,并展望其与AI结合的潜力,为开发者提供参考。
183 2
|
3月前
|
监控 算法 安全
公司电脑监控软件关键技术探析:C# 环形缓冲区算法的理论与实践
环形缓冲区(Ring Buffer)是企业信息安全管理中电脑监控系统设计的核心数据结构,适用于高并发、高速率与短时有效的多源异构数据处理场景。其通过固定大小的连续内存空间实现闭环存储,具备内存优化、操作高效、数据时效管理和并发支持等优势。文章以C#语言为例,展示了线程安全的环形缓冲区实现,并结合URL访问记录监控应用场景,分析了其在流量削峰、关键数据保护和高性能处理中的适配性。该结构在日志捕获和事件缓冲中表现出色,对提升监控系统效能具有重要价值。
97 1
|
4月前
|
存储 监控 算法
基于 C# 的局域网计算机监控系统文件变更实时监测算法设计与实现研究
本文介绍了一种基于C#语言的局域网文件变更监控算法,通过事件驱动与批处理机制结合,实现高效、低负载的文件系统实时监控。核心内容涵盖监控机制选择(如事件触发机制)、数据结构设计(如监控文件列表、事件队列)及批处理优化策略。文章详细解析了C#实现的核心代码,并提出性能优化与可靠性保障措施,包括批量处理、事件过滤和异步处理等技术。最后,探讨了该算法在企业数据安全监控、文件同步备份等场景的应用潜力,以及未来向智能化扩展的方向,如文件内容分析、智能告警机制和分布式监控架构。
125 3
|
4月前
|
存储 监控 算法
局域网上网记录监控的 C# 基数树算法高效检索方案研究
在企业网络管理与信息安全领域,局域网上网记录监控是维护网络安全、规范网络行为的关键举措。随着企业网络数据量呈指数级增长,如何高效存储和检索上网记录数据成为亟待解决的核心问题。基数树(Trie 树)作为一种独特的数据结构,凭借其在字符串处理方面的卓越性能,为局域网上网记录监控提供了创新的解决方案。本文将深入剖析基数树算法的原理,并通过 C# 语言实现的代码示例,阐述其在局域网上网记录监控场景中的具体应用。
124 7
|
4月前
|
存储 监控 算法
基于 C# 时间轮算法的控制局域网上网时间与实践应用
在数字化办公与教育环境中,局域网作为内部网络通信的核心基础设施,其精细化管理水平直接影响网络资源的合理配置与使用效能。对局域网用户上网时间的有效管控,已成为企业、教育机构等组织的重要管理需求。这一需求不仅旨在提升员工工作效率、规范学生网络使用行为,更是优化网络带宽资源分配的关键举措。时间轮算法作为一种经典的定时任务管理机制,在局域网用户上网时间管控场景中展现出显著的技术优势。本文将系统阐述时间轮算法的核心原理,并基于 C# 编程语言提供具体实现方案,以期深入剖析该算法在局域网管理中的应用逻辑与实践价值。
103 5