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

简介:

这节我们就用的最多的算法——排序发起重点的讨论。  

常见的排序分为冒泡排序,快速排序,直接插入排序 ,希尔排序,基数排序 ,简单选择排序 ,堆排序  等等。

一、冒泡排序

冒泡排序(Bubble Sort)的基本思想是:将相邻的记录的关键码进行比较,若前面记录的关键码大于后面记录的关键码,则将它们交换,否则不交换。

设待排序的顺序表 sqList 中有 n 个记录,冒泡排序要进行 n-1 趟,每趟循环均是从最后两个记录开始。 第 1 趟循环到第 2 个记录的关键码与第 1 个记录的关键码比较后终止, 第 2 趟循环到第 3 个记录的关键码与第 2 个记录的关键码比较结束后终止。一般地,第 i 趟循环到第 i+1 个记录的关键码与第 i 个记录的关键码比较后终止,所以,第 n-1 趟循环到第 n 个记录的关键码与第 n-1 个记录的关键码比较后终止。

冒泡排序算法的实现如下所示,算法中记录的比较表示记录关键码的比较,顺序表中只存放了记录的关键码: 实现的源代码如下:


//进行冒泡排序的方法
public void BubbleSort(SeqList<int> sqList) 
    { 
       ///进行交换的变量
         int tmp; 
         for (int i = 0; i < sqList.Last; ++i) 
         { 
              for (int j = sqList.Last - 1; j >= i; --j) 
              { 
                 //如果后面比前面大,  就交换
                  if (sqList[j + 1] < sqList[j]) 
                  { 
                      tmp = sqList[j + 1]; 
                      sqList[j + 1] = sqList[j]; 
                      sqList[j] = tmp; 
                  } 
              } 
         } 
}
//由于是双层循环 算法的时间的复杂度是O(n^2)

冒泡排序算法的最好情况是记录已全部排好序,这时,循环 n-1 次,每次循环都因没有数据交换而退出。因此,冒泡排序算法在最好情况下的时间复杂度为O(n)。

总的移动次数为比较次数的 3 倍, 因为被进行一次比较, 需要进行 3 次移动。因此,冒泡排序算法在最坏情况下的时间复杂度为O(n2)。
冒泡排序算法只需要一个辅助空间用于交换记录,所以,冒泡排序算法是一种稳定的排序方法。什么是稳定的排序算法,就是前面与后面的数字相等的话,不用交换。

二、快速排序

快速排序(Quick Sort)的基本思想是:通过不断比较关键码,以某个记录为界(该记录称为支点) ,将待排序列分成两部分。其中,一部分满足所有记录的关键码都大于或等于支点记录的关键码, 另一部分记录的关键码都小于支点记录的关键码。把以支点记录为界将待排序列按关键码分成两部分的过程,称为一次划分。对各部分不断划分,直到整个序列按关键码有序为止。

设待排序的顺序表 sqList 中有 n 个记录,一般地,第一次划分把第一个记录作为支点。首先,把支点复制到一个临时存储空间中,并设两个指示器,一个指示器 low,指向顺序表的低端(第一个记录所在位置) ,一个指示器 high,指向顺序表的高端(最后一个记录所在位置) 。然后,从 high 所指向的记录开始,将记录的关键码与支点(在临时存储空间中)的关键码进行比较,如果 high 所指向的记录的关键码大于支点的关键码,high 指示器向顺序表的低端方向移动一个记录的位置,否则,将 high 所指的记录复制到 low 所指的存储空间中。接着,又将 low 移到下一个记录,从 low 所指向的记录开始,将记录的关键码与临时存储空间的记录的关键码进行比较, 如果 low 所指向的记录的关键码小于临时存储空间的记录的关键码,low 指示器向顺序表的高端方法移动一个记录的位置,否则,将 low 所指的记录复制到 high 所指的存储空间中,high 指示器向顺序表的低端移动一个记录的位置。如此重复,直到 low 和 high 指示器指向同一个记录,
将临时空间的记录赋给 low 所指向的存储空间,第一次划分结束。如图所示:


快速排序的算法实现如下所示,算法中记录的比较表示记录关键码的比较顺序表中只存放了记录的关键码。相应源代码如下:


1 public void QuickSort(SeqList<int> sqList, int low, int high) 
 2     { 
 3          //头指针
 4           int i = low; 
 5          //尾指针
 6           int j = high; 
 7            //关键码
 8           int tmp = sqList[low]; 
 9           //头指针尾指针位置的变换
10           while (low < high) 
11           { 
12                while ((low < high) && (sqList[high] >= tmp)) 
13                { 
14                     --high; 
15                } 
16                sqList[low] = sqList[high]; 
17                ++low; 
18                while ((low < high) && (sqList[low] <= tmp)) 
19                { 
20                     ++low; 
21                } 
22                sqList[high] = sqList[low]; 
23                --high; 
24            } 
25            sqList[low] = tmp; 
26             //新一轮的变换
27            if (i < low-1) 
28            { 
29                 QuickSort(sqList, i, low-1); 
30            } 
31            //新一轮的递归
32            if (low+1 < j) 
33            { 
34                 QuickSort(sqList, low+1, j); 
35            } 
36     } 
37 }
38 //由于用到递归 循环 时间复杂度是O(nlog2n)

快速排序算法的时间复杂度和每次划分的记录系很大。 如果每次选取的记录都能均分成两个相等的子序列,这样的快速排序过程是一棵完全二叉树结构(即每个结点都把当前待排序列分成两个大小相当的子序列结点,n个记录待排序列的根结点的分解次数就构成了一棵完全二叉树) ,这时分解次数等于完全二叉树的深度log2n。每次快速排序过程无论把待排序列这样划分,全部的比较次数都接近于n-1 次,所以,最好情况下快速排序的时间复杂度为O(nlog2n) 。快速排序算法的最坏情况是记录已全部有序,此时n个记录待排序列的根结点的分解次数就构成了一棵单右支二叉树。 所以在最坏情况下快速排序算法的时间复杂度为O(n2)。一般情况下,记录的分布是随机的,序列的分解次数构成一棵二叉树,这样二叉树的深度接近于log2n,所以快速排序算法在一般情况下的时间复杂度为O(nlog2n) 。 另外,快速排序算法是一种不稳定的排序的方法。不稳定排序的算法 ,前后数字相等要交换。

这节,我们介绍了快速排序和冒泡排序。下节,我们介绍直接插入排序和希尔排序。嘎嘎。


目录
相关文章
|
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