Chemmy's Blog

chengming0916@outlook.com

一、 核心概念与架构

1. 什么是ELK?
ELK是三个开源软件的缩写,构成一套完整的日志集中管理、搜索分析和可视化解决方案:

  • Elasticsearch:分布式搜索和分析引擎,负责存储和索引日志数据。
  • Logstash:数据收集、处理和转发管道,负责从各种来源采集日志,进行过滤、解析,然后输出到存储(如ES)。
  • Kibana:数据可视化平台,为存储在Elasticsearch中的数据提供Web界面,用于搜索、分析和图表展示。

2. 为什么需要ELK?
解决传统日志分析(如 grep, awk)在分布式、大规模环境下的痛点:

  • 日志分散,难以集中管理。
  • 海量日志下,文本搜索效率低下。
  • 缺乏多维度查询和实时分析能力。
  • 无法进行直观的数据可视化。

3. ELK 工作原理

  • 数据流:应用/系统产生日志 -> Logstash (Shipper) 收集 -> 消息队列 (如Redis) 缓冲 -> Logstash (Indexer) 处理 -> Elasticsearch 存储/索引 -> Kibana 查询/展示。
  • Logstash 处理三阶段
    • Input:从文件、Syslog、Redis、Beats等来源读取数据。
    • Filter:使用 grok(解析文本)、mutate(修改字段)、geoip(添加地理位置)等插件对数据进行清洗、解析和丰富。
    • Output:将处理后的数据写入Elasticsearch、文件或其它系统。

二、 环境部署详细步骤

1. 基础环境准备

  • 系统:CentOS 7.1
  • 节点
    • elk-node1 (192.168.1.160):Master节点,部署全套ELK及Redis。
    • elk-node2 (192.168.1.161):Slave节点,部署Elasticsearch作为数据/候选主节点。
  • 前置操作:关闭防火墙、SELinux。

2. Elasticsearch 集群部署

  • 安装:通过配置Yum源安装。
  • 关键配置 (/etc/elasticsearch/elasticsearch.yml):
    1
    2
    3
    4
    5
    6
    7
    cluster.name: huanqiu
    node.name: elk-node1
    path.data: /data/es-data
    network.host: 0.0.0.0
    http.port: 9200
    # 集群发现配置 (node2上需要添加)
    discovery.zen.ping.unicast.hosts: ["192.168.1.160", "192.168.1.161"]
  • 插件安装
    • Head插件:用于集群管理和数据浏览。
    • Kopf插件:用于集群监控。
  • 启动与验证systemctl start elasticsearch,访问 http://<ip>:9200 或通过插件界面查看。

3. Logstash 部署与配置

  • 安装:通过Yum源安装。
  • 核心概念:编写 .conf 配置文件,定义 input, filter, output 部分。
  • 配置示例
    • 收集系统日志:从 /var/log/messages 读取,输出到ES。
    • 收集Nginx JSON日志:配置Nginx输出JSON格式日志,Logstash使用 json codec直接解析。
    • 使用 multiline 处理多行日志(如Java异常堆栈)。
    • 使用 grok 过滤器解析非结构化日志

4. Kibana 部署

  • 安装:下载解压包,配置 /usr/local/kibana/config/kibana.yml
    1
    2
    3
    server.port: 5601
    server.host: "0.0.0.0"
    elasticsearch.url: "http://192.168.1.160:9200"
  • 启动:通过 screen 会话在后台运行 /usr/local/kibana/bin/kibana
  • 使用:访问Web界面,在 Management -> Index Patterns 中创建索引模式(如 system-*),即可在 Discover 页面查询日志。

5. 引入Redis作为缓冲队列(生产环境推荐)

  • 目的:解耦日志收集与处理,提高可靠性,防止ES故障导致数据丢失,并缓冲流量压力。
  • 架构
    1. Shipper端:各应用服务器的Logstash将日志推送到Redis队列。
    2. Indexer端:中心服务器的Logstash从Redis队列拉取日志,处理后写入Elasticsearch。
  • 配置关键
    • 输出到Redis (Shipper):
      1
      2
      3
      4
      5
      6
      7
      output {
      redis {
      host => "192.168.1.160"
      data_type => "list"
      key => "logstash:nginx"
      }
      }
    • 从Redis输入 (Indexer):
      1
      2
      3
      4
      5
      6
      7
      input {
      redis {
      host => "192.168.1.160"
      data_type => "list"
      key => "logstash:nginx"
      }
      }

三、 配置要点与问题排查

  1. Elasticsearch 集群优化

    • 设置 discovery.zen.minimum_master_nodes 防止脑裂(通常为 (master节点数/2) + 1)。
    • 调整 ES_HEAP_SIZE(建议不超过物理内存一半,且小于32GB)。
    • 规划好索引分片(shard)数量和生命周期(按天/月分割)。
  2. Logstash 使用技巧

    • 使用 --configtest 参数测试配置文件语法。
    • 利用 type 字段区分不同日志源,便于后续分流处理。
    • 善用 Grok Debugger 在线工具调试 grok 匹配模式。
  3. Kibana 常见问题

    • 查询超时:在 kibana.yml 中调整 elasticsearch.requestTimeout 设置。
    • 字段被分词导致聚合不准:对字符串字段进行聚合时,使用 .raw 字段(未分析版本)。
  4. Java环境问题:如果系统Java版本与Logstash要求(通常需要Java 8+)冲突,可在 /etc/sysconfig/logstash 和启动脚本中单独为Logstash指定JAVA_HOME。

四、 总结

这份文档完整地展示了从零开始搭建一个具备生产级可靠性的ELK日志平台的过程,涵盖了:

  • 理论:ELK组件角色、架构设计(含缓冲队列)。
  • 实践:逐步安装、配置、集成各个组件。
  • 进阶:多种日志源的收集配置(系统日志、Nginx、Java应用、MySQL慢查询等)、使用Redis解耦、集群配置和基础调优。

通过此部署,可以实现日志的集中采集、实时处理、快速检索和可视化分析,极大提升运维排障效率和系统可观测性。

一、最小-最大搜索(Minimax Search)

核心思想:最小与最大是相对的,且只针对一方(AI)。

原理
AI走一步后,假设对手会走对AI最差的一步;AI需选择使自身收益最大的走法。

示例(搜索深度4):

1
AI走第1步 → 对手走第2步(最差) → AI走第3步(最佳) → 对手走第4步(最差)

→ 深度0时调用 Evaluate() 返回局面评价

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int Max(int depth) {
int best = -INFINITY;
if (depth <= 0) {
return Evaluate();
}
GenerateLegalMoves(); //产生所有合理走法
while (MovesLeft()) {
MakeNextMove(); //走这一步时
val = Min(depth - 1); //接受一个相对最小值
UnmakeMove();
if (val > best) {
best = val;
}
}
return best; //返回一个相对最大的评价(AI 认为的最佳着法)
}

int Min(int depth) {
int best = INFINITY; // 注意这里不同于"最大"算法
if (depth <= 0) {
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = Max(depth - 1); //接受一个相对最大值
UnmakeMove();
if (val < best) { // 注意这里不同于"最大"算法
best = val;
}
}
return best; //返回一个相对最小的评价(对方,人认为的最差走法)
}

调用方式val = MinMax(5); → 返回向前看5步的当前局面评价。


二、负值最大函数(Negamax Search)

优化点:将 Min/Max 合并为单函数,通过取负号处理双方角色切换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int NegaMax(int depth) {
int best = -INFINITY;
if (depth <= 0) {
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = -NegaMax(depth - 1); // 注意这里有个负号
UnmakeMove();
if (val > best) { //始终最优值
best = val;
}
}
return best;
}

优势:省去求 min 函数的步骤,减少代码量,始终求对当前节点的最佳走法。


三、Alpha-Beta搜索

问题:Minimax 需检查整个博弈树,分枝因子大导致效率低。

解决方案:通过维护上下界 alphabeta,剪枝无效分支。

3.1 核心概念

概念 说明
Alpha 当前节点的最优上界(MAX节点的最大值)
Beta 对手节点的最优下界(MIN节点的最小值)
Alpha剪枝 MIN节点:当 alpha >= beta 时终止扩展
Beta剪枝 MAX节点:当 alpha >= beta 时终止扩展

3.2 口袋示例

场景:死敌面前有多个口袋,你挑口袋,他挑物品。

目标:挑出在诸多最糟糕物品中最好的物品所在的口袋。

排序后剪枝示意

  • 节点2最小值200,节点3中150<200
  • 节点1下第一个子节点170 < 200,第二个子节点更小 → 剪裁
  • 节点4类似,第一个子节点50,后面的无需再比较

3.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int AlphaBeta(int depth, int alpha, int beta) {
if (depth == 0) {
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = -AlphaBeta(depth - 1, -beta, -alpha); // Alpha和Beta互换并取负
UnmakeMove();
if (val >= beta) {
return beta; // Beta剪枝
}
if (val > alpha) {
alpha = val; // 更新alpha
}
}
return alpha;
}

3.4 性能关键

依赖搜索顺序:若先搜最差分支,无法触发剪枝,退化为 Minimax。

优化建议:生成全部着法后,排序很重要。


参考文献


待补充

  • 评估函数设计(子力价值、位置优势、残局特征)
  • 迭代加深(Iterative Deepening)优化
  • 实际象棋博弈树规模估算

一、 环境规划

  • 部署模式:单机多节点 Docker 集群
  • 节点数量:3(node1、node2、node3)
  • 集群发现策略:静态节点列表(static)
  • 负载均衡器:Nginx(Stream 模块代理 TCP 流量)

二、 EMQX 集群部署

1. 目录准备与授权
1
2
3
4
5
6
7
8
mkdir -p node1/data node1/logs
mkdir -p node2/data node2/logs
mkdir -p node3/data node3/logs

chown 1000 node1/ node2/ node3/
chown 1000 node1/data/ node1/logs/
chown 1000 node2/data/ node2/logs/
chown 1000 node3/data/ node3/logs/
2. Docker Compose 配置

创建 docker-compose.yml,保留原配置值,仅修正缩进与语法高亮:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
version: '3'
services:
emqx1:
image: emqx:5.3.1
container_name: emqx1
environment:
- "EMQX_NODE_NAME=emqx@node1.emqx.io"
- "EMQX_CLUSTER__DISCOVERY_STRATEGY=static"
- "EMQX_CLUSTER__STATIC__SEEDS=[emqx@node1.emqx.io,emqx@node2.emqx.io,emqx@node3.emqx.io]"
healthcheck:
test: ["CMD", "/opt/emqx/bin/emqx ctl", "status"]
interval: 5s
timeout: 25s
retries: 5
networks:
emqx-bridge:
aliases:
- node1.emqx.io
ports:
- 1883:1883
- 8083:8083
- 8084:8084
- 8883:8883
- 18083:18083
volumes:
- /etc/localtime:/etc/localtime:ro
- ./node1/logs:/opt/emqx/log
- ./node1/data:/opt/emqx/data

emqx2:
image: emqx:5.3.1
container_name: emqx2
environment:
- "EMQX_NODE_NAME=emqx@node2.emqx.io"
- "EMQX_CLUSTER__DISCOVERY_STRATEGY=static"
- "EMQX_CLUSTER__STATIC__SEEDS=[emqx@node1.emqx.io,emqx@node2.emqx.io,emqx@node3.emqx.io]"
healthcheck:
test: ["CMD", "/opt/emqx/bin/emqx ctl", "status"]
interval: 5s
timeout: 25s
retries: 5
networks:
emqx-bridge:
aliases:
- node2.emqx.io
ports:
- 1873:1883
- 8073:8083
- 8074:8084
- 8873:8883
- 18073:18083
volumes:
- /etc/localtime:/etc/localtime:ro
- ./node2/logs:/opt/emqx/log
- ./node2/data:/opt/emqx/data

emqx3:
image: emqx:5.3.1
container_name: emqx3
environment:
- "EMQX_NODE_NAME=emqx@node3.emqx.io"
- "EMQX_CLUSTER__DISCOVERY_STRATEGY=static"
- "EMQX_CLUSTER__STATIC__SEEDS=[emqx@node1.emqx.io,emqx@node2.emqx.io,emqx@node3.emqx.io]"
healthcheck:
test: ["CMD", "/opt/emqx/bin/emqx ctl", "status"]
interval: 5s
timeout: 25s
retries: 5
networks:
emqx-bridge:
aliases:
- node3.emqx.io
ports:
- 1863:1883
- 8063:8083
- 8064:8084
- 8863:8883
- 18063:18083
volumes:
- /etc/localtime:/etc/localtime:ro
- ./node3/logs:/opt/emqx/log
- ./node3/data:/opt/emqx/data

networks:
emqx-bridge:
driver: bridge
3. 启动集群
1
docker-compose up -d

三、 Nginx 负载均衡配置

1. 基础 TCP 代理策略

编辑 nginx.conf,使用 stream 模块代理 MQTT 流量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
user nginx;
worker_processes auto;
error_log /var/log/nginx/error.log warn;
pid /var/run/nginx.pid;

events {
worker_connections 1024;
}

stream {
upstream emqx_tcp_cluster {
server 10.10.1.100:1883 weight=1 max_fails=3 fail_timeout=30s;
server 10.10.1.110:1873 weight=1 max_fails=3 fail_timeout=30s;
server 10.10.1.120:1863 weight=1 max_fails=3 fail_timeout=30s;
}

server {
listen 1893;
proxy_pass emqx_tcp_cluster;
proxy_buffer_size 8k;
tcp_nodelay on;
}
}
2. 扩展调度策略

根据业务需求替换 upstream 块配置:

  • 随机轮询
    1
    2
    3
    4
    5
    6
    upstream emqx_tcp_cluster {
    random;
    server 10.10.1.100:1883;
    server 10.10.1.110:1873;
    server 10.10.1.120:1863;
    }
  • 带权轮询
    1
    2
    3
    4
    5
    upstream emqx_tcp_cluster {
    server 10.10.1.100:1883 weight=1;
    server 10.10.1.110:1873 weight=2;
    server 10.10.1.120:1863 weight=3;
    }
  • 最小连接数
    1
    2
    3
    4
    5
    6
    upstream emqx_tcp_cluster {
    least_conn;
    server 10.10.1.100:1883;
    server 10.10.1.110:1873;
    server 10.10.1.120:1863;
    }
  • IP Hash(会话保持)
    1
    2
    3
    4
    5
    6
    upstream emqx_tcp_cluster {
    ip_hash;
    server 10.10.1.100:1883;
    server 10.10.1.110:1873;
    server 10.10.1.120:1863;
    }

四、 验证与访问

  • Dashboard 访问http://${ip}:18083
  • 默认凭证admin / public(首次登录强制修改)
  • 集群状态验证:进入任意容器执行 /opt/emqx/bin/emqx ctl cluster status,确认三节点状态为 running
  • 负载均衡验证:客户端连接 10.10.1.x:1893,查看 Nginx 访问日志或 EMQX Dashboard 连接分布。

五、 关键注意事项

  • 节点间通过 Docker 自定义网络 emqx-bridge 通信,需确保 EMQX_CLUSTER__STATIC__SEEDS 中的域名解析正确。
  • Nginx stream 模块需编译时启用(官方默认包通常已包含)。
  • 生产环境建议将 10.10.1.x 替换为实际宿主机 IP 或 Docker 网关 IP。
  • 端口映射已做偏移处理(1883/1873/1863),避免宿主机端口冲突。

C#排序算法的比较

首先通过图表比较不同排序算法的时间复杂度和稳定性。

排序方法

平均时间

最坏情况

最好情况

辅助空间

稳定性

直接插入排序

O(n2)

O(n2)

O(n)

O(1)

冒泡排序

O(n2)

O(n2)

O(n)

O(1)

简单选择排序

O(n2)

O(n2)

O(n2)

O(1)

希尔排序-

O(nlog2n)~O(n2)

O(nlog2n)~O(n2)

O(1)

快速排序

O(nlog2n)

O(n2)

O(nlog2n)

O(log2n)

堆排序

O(nlog2n)

O(nlog2n)

O(nlog2n)

O(1)

2-路归并排序

O(nlog2n)

O(nlog2n)

O(nlog2n)

O(n)

基数排序O(d(n + rd))O(d(n + rd))O(d(n + rd))O(rd)

注:1. 算法的时间复杂度一般情况下指最坏情况下的渐近时间复杂度。

        2. 排序算法的稳定性会对多关键字排序产生影响。

下面通过C#代码说明不同的排序算法

插入排序

时间复杂度:平均情况—O(n2) 最坏情况—O(n2) 辅助空间:O(1) 稳定性:稳定

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

希尔排序(shell)

时间复杂度:理想情况—O(nlog2n) 最坏情况—O(n2) 稳定性:不稳定

希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

冒泡排序

时间复杂度:平均情况—O(n2) 最坏情况—O(n2) 辅助空间:O(1) 稳定性:稳定

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

快速排序

时间复杂度:平均情况—O(nlog2n) 最坏情况—O(n2) 辅助空间:O(log2n) 稳定性:不稳定

快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11, 现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j]交换的时刻。

选择排序

时间复杂度:平均情况—O(n2) 最坏情况—O(n2) 辅助空间:O(1) 稳定性:不稳定

选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

堆排序

时间复杂度:平均情况—O(nlog2n) 最坏情况—O(nlog2n) 辅助空间:O(1) 稳定性:不稳定

我们知道堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, …1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法

归并排序

时间复杂度:平均情况—O(nlog2n) 最坏情况—O(nlog2n) 辅助空间:O(n) 稳定性:稳定

归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

C# 经典排序算法大全

Excerpt

文章浏览阅读84次。C# 经典排序算法大全选择排序using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace sorter{ public class SelectionSorter { private int min; …_c# case复杂排序


C# 经典排序算法大全

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class SelectionSorter

{

private int min;

public void Sort(int[] arr)

{

for (int i = 0; i < arr.Length - 1; ++i)

{

min = i;

for (int j = i + 1; j < arr.Length; ++j)

{

if (arr[j] < arr[min])

{

min = j;

}

}

int t = arr[min];

arr[min] = arr[i];

arr[i] = t;

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

SelectionSorter selSor = new SelectionSorter();

selSor.Sort(arrInt);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class EbullitionSorter

{

public void Sort(int[] arr)

{

int i, j, temp;

bool done = false;

j = 1;

while ((j < arr.Length) && (!done))

{

done = true;

for (i = 0; i < arr.Length - j; i++)

{

if (arr[i] > arr[i + 1])

{

done = false;

temp = arr[i];

arr[i] = arr[i + 1];

arr[i + 1] = temp;

}

}

j++;

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

EbullitionSorter selSor = new EbullitionSorter();

selSor.Sort(arrInt);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

高速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class QuickSorter

{

private void swap(ref int l, ref int r)

{

int temp;

temp = l;

l = r;

r = temp;

}

public void Sort(int[] list, int low, int high)

{

int pivot;

int l, r;

int mid;

if (high <= low)

{

return;

}

else if (high == low + 1)

{

if (list[low] > list[high])

{

swap(ref list[low], ref list[high]);

}

return;

}

mid = (low + high) >> 1;

pivot = list[mid];

swap(ref list[low], ref list[mid]);

l = low + 1;

r = high;

do

{

while (l <= r && list[l] < pivot)

{

l++;

}

while (list[r] >= pivot)

{

r--;

}

if (l < r)

{

swap(ref list[l], ref list[r]);

}

} while (l < r);

list[low] = list[r];

list[r] = pivot;

if (low + 1 < r)

{

Sort(list, low, r - 1);

}

if (r + 1 < high)

{

Sort(list, r + 1, high);

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

QuickSorter selSor = new QuickSorter();

selSor.Sort(arrInt, 0, arrInt.Length - 1);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class InsertionSorter

{

public void Sort(int[] arr)

{

for (int i = 1; i < arr.Length; i++)

{

int t = arr[i];

int j = i;

while ((j > 0) && (arr[j - 1] > t))

{

arr[j] = arr[j - 1];

--j;

}

arr[j] = t;

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

InsertionSorter selSor = new InsertionSorter();

selSor.Sort(arrInt);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class ShellSorter

{

public void Sort(int[] arr)

{

int inc;

for (inc = 1; inc <= arr.Length / 9; inc = 3 * inc + 1) ;

for (; inc > 0; inc /= 3)

{

for (int i = inc + 1; i <= arr.Length; i += inc)

{

int t = arr[i - 1];

int j = i;

while ((j > inc) && (arr[j - inc - 1] > t))

{

arr[j - 1] = arr[j - inc - 1];

j -= inc;

}

arr[j - 1] = t;

}

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

ShellSorter selSor = new ShellSorter();

selSor.Sort(arrInt);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Merge

{

public class Function

{

private int Groups;

private int CopyGroups;

private int mergerows;

private int[] Array27;

private static Random ran = new Random();

public Function(int length)

{

Array27 = new int[length];

for (int i = 0; i < length; i++)

Array27[i] = ran.Next(1, 100);

}

public void ToMergeSort()

{

MergeSort(Array27);

}

public void ToRecursiveMergeSort()

{

RecursiveMergeSort(Array27, 0, Array27.Length - 1);

}

public void ToNaturalMergeSort()

{

NaturalMergeSort(Array27);

}

public void RecursiveMergeSort(int[] Array, int left, int right)

{

int middle = (left + right) / 2;

if (left < right)

{

RecursiveMergeSort(Array, left, middle);

RecursiveMergeSort(Array, middle + 1, right);

MergeOne(Array, left, middle, right);

}

}

public void MergeOne(int[] Array, int left, int middle, int right)

{

int leftindex = left;

int rightindex = middle + 1;

int[] merge = new int[right + 1];

int index = 0;

while (leftindex <= middle && rightindex <= right)

merge[index++] = (Array[leftindex] - Array[rightindex]) >= 0 ? Array[rightindex++] : Array[leftindex++];

if (leftindex <= middle)

{

for (int i = leftindex; i <= middle; i++)

merge[index++] = Array[i];

}

if (rightindex <= right)

{

for (int i = rightindex; i <= right; i++)

merge[index++] = Array[i];

}

index = 0;

for (int i = left; i <= right; i++)

Array[i] = merge[index++];

}

public void MergeSort(int[] Array)

{

int[] merge = new int[Array.Length];

int P = 0;

while (true)

{

int index = 0;

int ENumb = (int)Math.Pow(2, P);

if (ENumb < Array.Length)

{

while (true)

{

int TorFAndrightindex = index;

if (TorFAndrightindex <= Array.Length - 1)

MergeTwo(Array, merge, index, ENumb);

else

break;

index += 2 * ENumb;

}

}

else

break;

P++;

}

}

public void MergeTwo(int[] Array, int[] merge, int index, int ENumb)

{

int left = index;

int middle = left + ENumb - 1;

if (middle >= Array.Length)

{

middle = index;

}

int mergeindex = index;

int right;

int middleTwo = (index + ENumb - 1) + 1;

right = index + ENumb + ENumb - 1;

if (right >= Array.Length - 1)

{

right = Array.Length - 1;

}

while (left <= middle && middleTwo <= right)

{

merge[mergeindex++] = Array[left] >= Array[middleTwo] ? Array[middleTwo++] : Array[left++];

}

if (left <= middle)

{

while (left <= middle && mergeindex < merge.Length)

merge[mergeindex++] = Array[left++];

}

if (middleTwo <= right)

{

while (middleTwo <= right)

merge[mergeindex++] = Array[middleTwo++];

}

if (right + 1 >= Array.Length)

Copy(Array, merge);

}

public void NaturalMergeSort(int[] Array)

{

int[,] PointsSymbol = LinearPoints(Array);

if (PointsSymbol[0, 1] == Array.Length - 1)

return;

else

NaturalMerge(Array, PointsSymbol);

}

public void NaturalMerge(int[] Array, int[,] PointsSymbol)

{

int left;

int right;

int leftend;

int rightend;

mergerows = GNumberTwo(Groups);

CopyGroups = Groups;

int[] TempArray = new int[Array.Length];

while (true)

{

int[,] TempPointsSymbol = new int[mergerows, 2];

int row = 0;

do

{

if (row != CopyGroups - 1)

{

left = PointsSymbol[row, 0];

leftend = PointsSymbol[row, 1];

right = PointsSymbol[row + 1, 0];

rightend = PointsSymbol[row + 1, 1];

MergeThree(Array, TempArray, left, leftend, right, rightend);

MergePointSymbol(PointsSymbol, TempPointsSymbol, row);

}

else

{

默认剩下的单独一个子数组已经虚拟合并。然后Copy进TempArray。

int TempRow = PointsSymbol[row, 0];

int TempCol = PointsSymbol[row, 1];

while (TempRow <= TempCol)

TempArray[TempRow] = Array[TempRow++];

TempPointsSymbol[row / 2, 0] = PointsSymbol[row, 0];

TempPointsSymbol[row / 2, 1] = PointsSymbol[row, 1];

break;

}

row += 2;

if (TempPointsSymbol[0, 1] == Array.Length - 1)

break;

}

while (row <= CopyGroups - 1);

Copy(Array, TempArray);

UpdatePointSymbol(PointsSymbol, TempPointsSymbol, row);

mergerows = GNumber(mergerows);

CopyGroups = GNumberTwo(CopyGroups);

if (PointsSymbol[0, 1] == Array.Length - 1)

break;

}

}

public int GNumber(int Value)

{

if (Value % 2 == 0)

Value /= 2;

else

Value -= 1;

return Value;

}

public int GNumberTwo(int Value)

{

if (Value % 2 == 0)

mergerows = Value / 2;

else

mergerows = Value / 2 + 1;

return mergerows;

}

public void MergeThree(int[] Array, int[] Temp, int left, int leftend, int right, int rightend)

{

int index = left;

while (left <= leftend && right <= rightend)

Temp[index++] = Array[left] >= Array[right] ? Array[right++] : Array[left++];

while (left <= leftend)

Temp[index++] = Array[left++];

while (right <= rightend)

Temp[index++] = Array[right++];

}

public void MergePointSymbol(int[,] PointsSymbol, int[,] TempPointsSymbol, int row)

{

int rowindex = row / 2;

TempPointsSymbol[rowindex, 0] = PointsSymbol[row, 0];

TempPointsSymbol[rowindex, 1] = PointsSymbol[row + 1, 1];

}

public void UpdatePointSymbol(int[,] PointsSymbol, int[,] TempPointsSymbol, int rows)

{

int row = 0;

for (; row < TempPointsSymbol.GetLength(0); row++)

{

for (int col = 0; col < 2; col++)

PointsSymbol[row, col] = TempPointsSymbol[row, col];

}

for (; row < PointsSymbol.GetLength(0); row++)

{

for (int col2 = 0; col2 < 2; col2++)

PointsSymbol[row, col2] = 0;

}

补剩下的index组,

// int row3 = TempPointsSymbol.GetLength(0); // PointsSymbol[row3, 0] = PointsSymbol[rows, 0]; // PointsSymbol[row3, 1] = PointsSymbol[rows, 1]; // //后面的清零 // for (int row4 = row3 + 1; row4 < PointsSymbol.GetLength(0); row4++) // { // for (int col4 = 0; col4 < 2; col4++) // PointsSymbol[row4, col4] = 0; // } //} } public int[,] LinearPoints(int[] Array) { Groups = 1; int StartPoint = 0; int row = 0; int col = 0; //最糟糕的情况就是有Array.Length行。 int[,] PointsSet = new int[Array.Length, 2]; //线性扫描Array,划分数组 //初始前index=0 PointsSet[row, col] = 0; do { //推断升序子数组终于的index开关 bool Judge = false; //从Array第二个数推断是否要结束或者是否是升序子数组. while (++StartPoint < Array.Length && Array[StartPoint] < Array[StartPoint - 1]) { //打开第一个升序子数组结束的index开关 Judge = true; //又一次開始第二个升序子数组的前index PointsSet[row, col + 1] = StartPoint - 1; //计算子数组个数 Groups++; //换行记录自然子数组的index row++; break; //–StartPoint; } //升序子数组结束index if (Judge) PointsSet[row, col] = StartPoint; //else // –StartPoint; } while (StartPoint < Array.Length); //终于index=StartPoint - 1,可是糟糕情况下还有剩余若干行为: 0,0 … PointsSet[row, col + 1] = StartPoint - 1; //调用展示方法 DisplaySubarray(Array, PointsSet, Groups); return PointsSet; } public void DisplaySubarray(int[] Array, int[,] PointsSet, int Groups) { Console.WriteLine(“Subarray is {0}:”, Groups); //展示子数组的前后index for (int r = 0; r < Groups; r++) { for (int c = 0; c < PointsSet.GetLength(1); c++) { Console.Write(PointsSet[r, c]); if (c < PointsSet.GetLength(1) - 1) Console.Write(“,”); } Console.Write(“\t\t”); } Console.WriteLine(); //展示分出的子数组 for (int v = 0; v < Groups; v++) { int i = 1; for (int r = PointsSet[v, 0]; r <= PointsSet[v, 1]; r++) { Console.Write(Array[r] + “ “); i++; } if (i <= 3) Console.Write(“\t\t”); else Console.Write(“\t”); if (PointsSet[v, 1] == Array.Length) break; } } public void Copy(int[] Array, int[] merge) { //一部分排好序的元素替换掉原来Array中的元素 for (int i = 0; i < Array.Length; i++) { Array[i] = merge[i]; } } //输出 public override string ToString() { string temporary = string.Empty; foreach (var element in Array27) temporary += element + “ “; temporary += “\n”; return temporary; } } class Program { static void Main(string[] args) { while (true) { Console.WriteLine(“请选择:”); Console.WriteLine(“1.归并排序(非递归)”); Console.WriteLine(“2.归并排序(递归)”); Console.WriteLine(“3.归并排序(自然合并)”); Console.WriteLine(“4.退出”); int Arraynum = Convert.ToInt32(Console.ReadLine()); switch (Arraynum) { case 4: Environment.Exit(0); break; case 1: Console.WriteLine(“Please Input Array Length”); int Leng271 = Convert.ToInt32(Console.ReadLine()); Function obj1 = new Function(Leng271); Console.WriteLine(“The original sequence:”); Console.WriteLine(obj1); Console.WriteLine(“‘MergeSort’ Finaly Sorting Result:”); obj1.ToMergeSort(); Console.WriteLine(obj1); break; case 2: Console.WriteLine(“Please Input Array Length”); int Leng272 = Convert.ToInt32(Console.ReadLine()); Function obj2 = new Function(Leng272); Console.WriteLine(“The original sequence:”); Console.WriteLine(obj2); Console.WriteLine(“‘RecursiveMergeSort’ Finaly Sorting Result:”); obj2.ToRecursiveMergeSort(); Console.WriteLine(obj2); break; case 3: Console.WriteLine(“Please Input Array Length”); int Leng273 = Convert.ToInt32(Console.ReadLine()); Function obj3 = new Function(Leng273); Console.WriteLine(“The original sequence:”); Console.WriteLine(obj3); obj3.ToNaturalMergeSort(); Console.WriteLine(); Console.WriteLine(); Console.WriteLine(“‘NaturalMergeSort’ Finaly Sorting Result:”); Console.WriteLine(obj3); break; } } } } }

基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Merge

{

public class RadixSorter

{

public int[] RadixSort(int[] ArrayToSort, int digit)

{

for (int k = 1; k <= digit; k++)

{

int[] tmpArray = new int[ArrayToSort.Length];

int[] tmpCountingSortArray = new int[10] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

for (int i = 0; i < ArrayToSort.Length; i++)

{

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;

}

}

class Program

{

static void Main(string[] args)

{

int[] intArray = new int[] { 5, 3, 7, 4, 8, 2, 9, 1, 0, 6 };

int[] newIntArray = intArray;

RadixSorter rS=new RadixSorter();

newIntArray = rS.RadixSort(intArray, intArray.Length);

foreach (int i in intArray)

{

Console.Write(i + " ");

}

Console.ReadKey();

}

}

}

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Merge

{

class Program

{

/// 要求: /// arrayToSort的元素必须大于等于0。或者经过一定的转换使其元素在 /// 大于等于0范围内。比如有例如以下序列(-1,-8,10,11),那么依据最小值8, /// 将各个数字加8转化为(7,0,18,19),然后进行计数排序。结果为(0,7,18,19), /// 然后再将结果个数字减8即为(-8,-1,10,11) /// /// 要排序的数组 /// 数组的最大值加一 /// 计数排序后的结果 public static int[] CountingSort(int[] arrayToSort, int k) { // 排序后的结果存储 int[] sortedArray = new int[arrayToSort.Length]; // 计数数组 int[] countingArray = new int[k]; // 计数数组初始化 for (int i = 0; i < countingArray.Length; i++) { countingArray[i] = 0; } // 单个元素计数(经过该步骤countingArray[i]的含义为数字i的个数为countingArray[i]) for (int i = 0; i < arrayToSort.Length; i++) { countingArray[arrayToSort[i]] = countingArray[arrayToSort[i]] + 1; } // 计算小于等于某数的个数(经过该步骤countingArray[i]的含义为小于等于数字i的元素个数为countingArray[i]) for (int i = 1; i < countingArray.Length; i++) { countingArray[i] += countingArray[i - 1]; } // 得到排序后的结果 for (int i = 0; i < sortedArray.Length; i++) { int numIndex = countingArray[arrayToSort[i]] - 1; sortedArray[numIndex] = arrayToSort[i]; countingArray[arrayToSort[i]] = countingArray[arrayToSort[i]] - 1; } return sortedArray; } static void Main(string[] args) { int[] intArray = new int[] { 5, 3, 7, 4, 8, 2, 9, 1, 0, 6 }; int[] intNewArray = intArray; intNewArray = CountingSort(intArray, intArray.Length); foreach (int i in intNewArray) { Console.Write(i + “ “); } Console.ReadKey(); } } }

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Merge

{

class Program

{

private static void HeapSortFunction(int[] array)

{

try

{

BuildMaxHeap(array);

for (int i = array.Length - 1; i > 0; i--)

{

Swap(ref array[0], ref array[i]);

MaxHeapify(array, 0, i);

}

}

catch (Exception ex)

{

Console.Write(ex.Message);

}

}

private static void BuildMaxHeap(int[] array)

{

try

{

for (int i = array.Length / 2 - 1; i >= 0; i--)

{

MaxHeapify(array, i, array.Length);

}

}

catch (Exception ex)

{

Console.Write(ex.Message);

}

}

private static void MaxHeapify(int[] array, int currentIndex, int heapSize)

{

try

{

int left = 2 * currentIndex + 1;

int right = 2 * currentIndex + 2;

int large = currentIndex;

if (left < heapSize && array[left] > array[large])

{

large = left;

}

if (right < heapSize && array[right] > array[large])

{

large = right;

}

if (currentIndex != large)

{

Swap(ref array[currentIndex], ref array[large]);

MaxHeapify(array, large, heapSize);

}

}

catch (Exception ex)

{

Console.Write(ex.Message);

}

}

private static void Swap(ref int a, ref int b)

{

int temp = 0;

temp = a;

a = b;

b = temp;

}

static void Main(string[] args)

{

int[] intArray = new int[] { 5, 3, 7, 4, 8, 2, 9, 1, 0, 6 };

HeapSortFunction(intArray);

foreach (int i in intArray)

{

Console.Write(i + " ");

}

Console.ReadKey();

}

}

}

排序的分类/稳定性/时间复杂度和空间复杂度总结

版权声明:本文博客原创文章。博客,未经同意,不得转载。

冒泡排序算法(C#实现) - Eric Sun - 博客园

Excerpt

简单的冒泡排序算法,代码如下://冒泡排序(从数组的起始位置开始遍历,以大数为基准:大的数向下沉一位)privatestaticvoid BubbleSortFunction(int[] array) { try { int length = array.Length; int temp; bool


简单的冒泡排序算法,代码如下:

复制代码

1
<span>//</span><span>冒泡排序(从数组的起始位置开始遍历,以大数为基准:大的数向下沉一位)</span><span><br></span><span>private</span><span>static</span><span>void</span><span> BubbleSortFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> length </span><span>=</span><span> array.Length;<br>                </span><span>int</span><span> temp;<br>                </span><span>bool</span><span> hasExchangeAction; </span><span>//</span><span>记录此次大循环中相邻的两个数是否发生过互换(如果没有互换,则数组已经是有序的)</span><span><br></span><span><br>                </span><span>for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>0</span><span>; i </span><span>&lt;</span><span> length </span><span>-</span><span>1</span><span>; i</span><span>++</span><span>)    </span><span>//</span><span>数组有N个数,那么用N-1次大循环就可以排完</span><span><br></span><span>                {<br>                    hasExchangeAction </span><span>=</span><span>false</span><span>;  </span><span>//</span><span>每次大循环都假设数组有序</span><span><br></span><span><br>                    </span><span>for</span><span> (</span><span>int</span><span> j </span><span>=</span><span>0</span><span>; j </span><span>&lt;</span><span> length </span><span>-</span><span> i </span><span>-</span><span>1</span><span>; j</span><span>++</span><span>)    </span><span>//</span><span>从数组下标0处开始遍历,(length - i - 1 是刨除已经排好的大数)</span><span><br></span><span>                    {<br>                        </span><span>if</span><span> (array[j] </span><span>&gt;</span><span> array[j </span><span>+</span><span>1</span><span>])    </span><span>//</span><span>相邻两个数进行比较,如果前面的数大于后面的数,则将这相邻的两个数进行互换</span><span><br></span><span>                        {<br>                            temp </span><span>=</span><span> array[j];<br>                            array[j] </span><span>=</span><span> array[j </span><span>+</span><span>1</span><span>];<br>                            array[j </span><span>+</span><span>1</span><span>] </span><span>=</span><span> temp;<br>                            hasExchangeAction </span><span>=</span><span>true</span><span>;   </span><span>//</span><span>发生过互换</span><span><br></span><span>                        }<br>                    }<br><br>                    </span><span>if</span><span> (</span><span>!</span><span>hasExchangeAction) </span><span>//</span><span>如果没有发生过互换,则数组已经是有序的了,跳出循环</span><span><br></span><span>                    {<br>                        </span><span>break</span><span>;<br>                    }<br>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }</span>

复制代码

。。。。。

posted @ 2011-08-17 16:02  Eric Sun  阅读(7637)  评论()  编辑  收藏  举报

归并排序算法(C#实现)

Excerpt

自顶向下的归并排序:是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为:1)划分子表 2)合并半子表


     归并排序(Merge Sort)是利用”归并”技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。归并排序有两种方式:1): 自底向上的方法 2):自顶向下的方法

 1、 自底向上的方法
(1) 自底向上的基本思想
     自底向上的基本思想是:第1趟归并排序时,将待排序的文件R[1..n]看作是n个长度为1的有序子文件,将这些子文件两两归并,若n为偶数,则得到n/2个长度为2的有序子文件;若n为奇数,则最后一个子文件轮空(不参与归并)。故本趟归并完成后,前n/2 - 1个有序子文件长度为2,但最后一个子文件长度仍为1;第2趟归并则是将第1趟归并所得到的n/2个有序的子文件两两归并,如此反复,直到最后得到一个长度为n的有序文件为止。
     上述的每次归并操作,均是将两个有序的子文件合并成一个有序的子文件,故称其为”二路归并排序”。类似地有k(k>2)路归并排序。   

2、自顶向下的方法(本文主要介绍此种方法,下面的文字都是对此种方法的解读)

(1) 自顶向下的基本思想
     采用分治法进行自顶向下的算法设计,形式更为简洁。
     自顶向下的归并排序:是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为:

      1)划分子表

      2)合并半子表

(1)分治法的三个步骤
     设归并排序的当前区间是R[low..high],分治法的三个步骤是:
①分解:将当前区间一分为二,即求分裂点
②求解:递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序;
③组合:将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
  递归的终结条件:子区间长度为1(一个记录自然有序)。

如下演示递归的整个过程:

递归便是深度遍历(如下由左至右进行遍历):假设有这样的一列数组{9,8,7,6,5,4,3,2,1}进行划分的顺序如下:

{9,8,7,6,5,4,3,2,1} –> {9,8,7,6,5},{4,3,2,1}

{9,8,7,6,5} –> {9,8,7},{6,5}

                        {9,8,7} –> {9,8},{7}

                                          {9,8} –> {9},{8}

                        {6,5} –>{6},{5}

{4,3,2,1} –> {4,3},{2,1}

                      {4,3} –>{4},{3}

                      {2,1} –>{2},{1}

当深度划分到左右数组都只剩1个元素的时候,进行上述逆序的合并:

{9},{8} –> {8,9} 然后和 {7} –> {7,8,9}

                                {6},{5} –> {5,6}    然后 {7,8,9}和{5,6} –> {5,6,7,8,9}

                                     {2},{1} –> {1,2}

                                     {4},{3} –> {3,4}   然后 {1,2}和 {3,4} –> {1,2,3,4}

                                                                                                                         最终{5,6,7,8,9}和{1,2,3,4} –> {1,2,3,4,5,6,7,8,9}

具体实现代码如下所示:

复制代码

1
<span>//</span><span>归并排序(目标数组,子表的起始位置,子表的终止位置)</span><span><br></span>        <span>private</span> <span>static</span> <span>void</span> MergeSortFunction(<span>int</span>[] array, <span>int</span> first, <span>int</span> last)<br>        {<br>            <span>try</span><br>            {<br>                <span>if</span> (first &lt; last)   <span>//</span><span>子表的长度大于1,则进入下面的递归处理</span><span><br></span>                {<br>                    <span>int</span> mid = (first + last) / <span>2</span>;   <span>//</span><span>子表划分的位置</span><span><br></span>                    MergeSortFunction(array, first, mid);   <span>//</span><span>对划分出来的左侧子表进行递归划分</span><span><br></span>                    MergeSortFunction(array, mid + <span>1</span>, last);    <span>//</span><span>对划分出来的右侧子表进行递归划分</span><span><br></span>                    MergeSortCore(array, first, mid, last); <span>//</span><span>对左右子表进行有序的整合(归并排序的核心部分)</span><span><br></span>                }<br>            }<br>            <span>catch</span> (Exception ex)<br>            { }<br>        }<br><br>        <span>//</span><span>归并排序的核心部分:将两个有序的左右子表(以mid区分),合并成一个有序的表</span><span><br></span>        <span>private</span> <span>static</span> <span>void</span> MergeSortCore(<span>int</span>[] array, <span>int</span> first, <span>int</span> mid, <span>int</span> last)<br>        {<br>            <span>try</span><br>            {<br>                <span>int</span> indexA = first; <span>//</span><span>左侧子表的起始位置</span><span><br></span>                <span>int</span> indexB = mid + <span>1</span>;   <span>//</span><span>右侧子表的起始位置</span><span><br></span>                <span>int</span>[] temp = <span>new</span> <span>int</span>[last + <span>1</span>]; <span>//</span><span>声明数组(暂存左右子表的所有有序数列):长度等于左右子表的长度之和。</span><span><br></span>                <span>int</span> tempIndex = <span>0</span>;<br>                <span>while</span> (indexA &lt;= mid &amp;&amp; indexB &lt;= last) <span>//</span><span>进行左右子表的遍历,如果其中有一个子表遍历完,则跳出循环</span><span><br></span>                {<br>                    <span>if</span> (array[indexA] &lt;= array[indexB]) <span>//</span><span>此时左子表的数 &lt;= 右子表的数</span><span><br></span>                    {<br>                        temp[tempIndex++] = array[indexA++];    <span>//</span><span>将左子表的数放入暂存数组中,遍历左子表下标++</span><span><br></span>                    }<br>                    <span>else</span><span>//</span><span>此时左子表的数 &gt; 右子表的数</span><span><br></span>                    {<br>                        temp[tempIndex++] = array[indexB++];    <span>//</span><span>将右子表的数放入暂存数组中,遍历右子表下标++</span><span><br></span>                    }<br>                }<br>                <span>//</span><span>有一侧子表遍历完后,跳出循环,将另外一侧子表剩下的数一次放入暂存数组中(有序)</span><span><br></span>                <span>while</span> (indexA &lt;= mid)<br>                {<br>                    temp[tempIndex++] = array[indexA++];<br>                }<br>                <span>while</span> (indexB &lt;= last)<br>                {<br>                    temp[tempIndex++] = array[indexB++];<br>                }<br><br>                <span>//</span><span>将暂存数组中有序的数列写入目标数组的制定位置,使进行归并的数组段有序</span><span><br></span>                tempIndex = <span>0</span>;<br>                <span>for</span> (<span>int</span> i = first; i &lt;= last; i++)<br>                {<br>                    array[i] = temp[tempIndex++];<br>                }<br>            }<br>            <span>catch</span> (Exception ex)<br>            { }<br>        }

复制代码

       对于N个元素的数组来说, 如此划分需要的层数是以2为底N的对数, 每一层中, 每一个元素都要复制到结果数组中, 并复制回来, 所以复制2N次, 那么对于归并排序,它的时间复杂度为O(N*logN), 而比较次数会少得多, 最少需要N/2次,最多为N-1次, 所以平均比较次数在两者之间. 它的主要问题还是在于在内存中需要双倍的空间.

插入排序算法C#实现

Excerpt

插入排序算法主要分为:直接插入算法,折半排序算法(二分插入算法),希尔排序算法,后两种是直接插入算法的改良。因此直接插入算法是基础,这里先进行直接插入算法的分析与编码。直接插入算法的排序思想:假设有序数组从小到大为array[0],array[1],array[2],….,array[n-2],


插入排序算法主要分为:直接插入算法,折半排序算法(二分插入算法),希尔排序算法,后两种是直接插入算法的改良。因此直接插入算法是基础,这里先进行直接插入算法的分析与编码。

直接插入算法的排序思想:假设有序数组从小到大为array[0],array[1],array[2],….,array[n-2],array[n-1],那么将待排数值array[n]与前面的有序数组从后向前依次比较,直到在有序数组中找到小于待排数值array[n]的位置,将array[n]插入到此位置,并入组合成新的有序数组。

直接插入算法--代码如下所示:

复制代码

1
<span>     //</span><span>直接插入排序算法(传递待排数组名,即:数组的地址。故形参数组的各种操作反应到实参数组上)</span><span><br></span><span>     private </span><span>static </span><span>void</span><span> InsertSortionFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> temp </span><span>=</span><span>0</span><span>;   </span><span>//</span><span>临时变量,存储待排的数值</span><span><br></span><span>         for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>1</span><span>; i </span><span>&lt;</span><span> array.Length; i</span><span>++</span><span>)  </span><span>//</span><span>将无序的所有数值依次插入到有序数组中,注:下标从1开始,因为操作的是同一个数组</span><span><br></span><span>                {<br>                    temp </span><span>=</span><span> array[i];    </span><span>//</span><span>记录待插入前面有序数组的数值</span><span><br></span><span>            int</span><span> index </span><span>=</span><span> i </span><span>-</span><span>1</span><span>;  </span><span>//</span><span>记录前方有序数组的末尾位置</span><span><br></span><span>            while</span><span> (index </span><span>&gt;=</span><span>0</span><span>&amp;&amp;</span><span> array[index] </span><span>&gt;</span><span> temp)   </span><span>//</span><span>循环遍历前面的有序数组,并且从大到小依次与待排数值进行比较</span><span><br></span><span>                    {<br>                        array[index </span><span>+</span><span>1</span><span>] </span><span>=</span><span> array[index];    </span><span>//</span><span>如果index&gt;=0并且此时的值大于待排数值,将此处的值向后移动一位</span><span><br></span><span>                        index</span><span>--</span><span>;    </span><span>//</span><span>index--向前遍历有序数组</span><span><br></span><span>                    }<br>                    array[index </span><span>+</span><span>1</span><span>] </span><span>=</span><span> temp;    </span><span>//</span><span>由于前面的index--,所以temp插入的位置是index+1</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }</span>

复制代码

折半排序算法是对直接插入算法的一种优化,优化的核心是:通过折半查看有序数组中间位置的数值(a)与待插入的数值(temp)的大小,如果a>=temp,则转向折半的左区间继续折半查找; 如果a<temp,则转向折半后的右区间继续折半查找。直到左右下标相同时,此时折半的下标也指向相同的位置,再做最后一次循环,最终的结果是:左右下标相差1,并且原来左侧的下标指向大于temp的位置,原来右侧的下标指向了小于temp的位置,即:array[biggerIndex] < temp < array[smallerIndex]。

折半排序算法--代码如下:

复制代码

1
<span>  &nbsp;   </span><span>//</span><span>折半排序算法(传递待排数组名,即:数组的地址。故形参数组的各种操作反应到实参数组上)</span>
1
<span>        private </span><span>static </span><span>void</span><span> BinaryInsertionSortFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> smallerIndex </span><span>=</span><span>0</span><span>; </span><span>//</span><span>记录有序数组的起始位置</span><span><br></span><span>          int</span><span> biggerIndex </span><span>=</span><span>0</span><span>; </span><span>//</span><span>记录有序数组的终止位置</span><span><br></span><span>          int</span><span> midIndex </span><span>=</span><span>0</span><span>; </span><span>//</span><span>记录获取有序数组的中间位置(折半法的关键:折半的位置)</span><span><br></span><span>          int</span><span> temp;  </span><span>//</span><span>记录带排的数值</span><span><br></span><span>          for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>1</span><span>; i </span><span>&lt;</span><span> array.Length; i</span><span>++</span><span>)  </span><span>//</span><span>循环向有序数组中插入数值(i从1开始,因为操作的是同一个数组)</span><span><br></span><span>                {<br>                    temp </span><span>=</span><span> array[i];   </span><span>//</span><span>记录待插入有序数组的数值</span><span><br></span><span>                    biggerIndex </span><span>=</span><span> i </span><span>-</span><span>1</span><span>;<br>                    </span><span>//</span><span>当smallerIndex==biggerIndex时,进入最后一次循环:smallerIndex指向大于temp的数组位置,biggerIndex指向小于temp的数组位置</span><span><br></span><span>            while</span><span> (smallerIndex </span><span>&lt;=</span><span> biggerIndex)   <br>                    {<br>                        midIndex </span><span>=</span><span> (smallerIndex </span><span>+</span><span> biggerIndex) </span><span>/</span><span>2</span><span>; </span><span>//</span><span>确定折半的位置</span><span><br></span><span>              if</span><span>(array[midIndex] </span><span>&gt;=</span><span> temp)  </span><span>//</span><span>折半位置的数值 &gt;= temp</span><span><br></span><span>                        {<br>                            biggerIndex </span><span>=</span><span> midIndex </span><span>-</span><span>1</span><span>;    </span><span>//</span><span>biggerIndex以midIndex为基础向前移动一位</span><span><br></span><span>                        }<br>                        </span><span>else</span><span><br>                        {<br>                            smallerIndex </span><span>=</span><span> midIndex </span><span>+</span><span>1</span><span>;  </span><span>//</span><span>smallerIndex以midIndex为基础向后移动一位</span><span><br></span><span>                        }<br>                    }<br>                    </span><span>for</span><span> (</span><span>int</span><span> j </span><span>=</span><span> i </span><span>-</span><span>1</span><span>; j </span><span>&gt;</span><span>biggerIndex; j</span><span>--</span><span>) </span><span>//</span><span>将有序数组中大于temp的数值分别向后移动一位</span><span><br></span><span>                    {<br>                        array[j </span><span>+</span><span>1</span><span>] </span><span>=</span><span> array[j];  </span><span>//<br></span><span>                    }<br>                    array[biggerIndex </span><span>+</span><span>1</span><span>] </span><span>=</span><span> temp;   </span><span>//</span><span>将temp插入biggerIndex + 1,因为此时array[biggerIndex]&lt;temp&lt;array[smallerIndex]</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }</span>

复制代码

希尔排序同样是直接插入排序算法的一种改进,基本思想是:将无序的数列划分为若干小的子序列,然后对子序列进行直接插入排序。
时间性能优于直接插入排序算法,但是一种不稳定的排序,时间复杂度为O(nlogn)。
希尔排序算法主要分为3重循环:
第一重循环–>按照gap的大小进行分组,初始化从array.Length/2开始,依次递减到1
第二重循环–>对所有分组进行排序
第三重循环–>组内进行直接插入排序

希尔排序算法--代码如下:

复制代码

1
<span>      private </span><span>static </span><span>void</span><span> ShellSortFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> length </span><span>=</span><span> array.Length;<br>                </span><span>int</span><span> temp </span><span>=</span><span>0</span><span>;<br>                </span><span>for</span><span> (</span><span>int</span><span> gap </span><span>=</span><span> length </span><span>/</span><span>2</span><span>; gap </span><span>&gt;</span><span>0</span><span>; gap</span><span>--</span><span>)  </span><span>//</span><span>第一重循环,按照gap的大小进行分组</span><span><br></span><span>                {<br>                    </span><span>for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>0</span><span>; i </span><span>&lt;</span><span> gap; i</span><span>++</span><span>)   </span><span>//</span><span>第二重循环,对所有分组进行排序</span><span><br></span><span>                    {<br>                        </span><span>for</span><span> (</span><span>int</span><span> j </span><span>=</span><span> i; j </span><span>&lt;</span><span> length; j </span><span>=</span><span> j </span><span>+</span><span> gap)    </span><span>//</span><span>第三重循环,组内进行直接插入排序</span><span><br></span><span>                        {<br>                            temp </span><span>=</span><span> array[j];<br>                            </span><span>int</span><span> index </span><span>=</span><span> j </span><span>-</span><span> gap;<br>                            </span><span>while</span><span> (index </span><span>&gt;=</span><span>0</span><span>&amp;&amp;</span><span> array[index] </span><span>&gt;</span><span> temp)<br>                            {<br>                                array[index </span><span>+</span><span> gap] </span><span>=</span><span> array[index];<br>                                index </span><span>=</span><span> index </span><span>-</span><span> gap;<br>                            }<br>                            array[index </span><span>+</span><span> gap] </span><span>=</span><span> temp;<br>                        }<br>                    }<br>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }</span>

复制代码

。。。。

安装

1
2
3
4
5
6
7
8
9

sudo apt install lm-sensors curl hddtemp # 安装工具

sensors-detect # 检测传感器

sudo apt install conky # 安装

conky & # 运行conky

传感器数据样例

1
2
3
4
5
6
7
8
9
acpitz-virtual-0-
Adapter: Virtual device
temp1: +49.5°C (crit = +99.0°C)

coretemp-isa-0000
Adapter: ISA adapter
Physical id 0: +49.0°C (high = +100.0°C, crit = +100.0°C)
Core 0: +49.0°C (high = +100.0°C, crit = +100.0°C)
Core 1: +49.0°C (high = +100.0°C, crit = +100.0°C)

:TODO conky 默认运行效果截图

conky默认以一个弹窗的形式运行,并使用位于/etc/conky/conky.conf的基础配置文件

集成到桌面

1
2
cp /etc/conky/conky.conf /home/$USER/.conkyrc # 复制默认配置文件

添加删除

1
2
3
4
5
6
7
8
9
10
11
12
13
# 查看虚拟机
virsh list --all

# 创建虚拟机
virt-install -virt-type=kvm --name={虚拟机名} --vcpus=4 \
--memory=1024 --location={iso文件} \
--disk path={虚拟机硬盘存放路径}.qcow2,size=30,format=qcow2 \
--network bridge=virbr0 --graphics none --extra-args='console=ttyS0'
--force

# 删除虚拟机
virsh undefine {虚拟机名}

开关机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 开启虚拟机
virsh start {虚拟机名}

# 关闭虚拟机
virsh shutdown {虚拟机名}

# 强制关机
virsh destroy {虚拟机名}

# 挂起虚拟机
virsh suspend {虚拟机名}

# 恢复挂起的
virsh resume {虚拟机名}

# 设置虚拟机和物理机开机一起启动
virsh autostart {虚拟机名}

# 取消虚拟机开机启动
virsh autostart {虚拟机名}

备份克隆

1
2
3
4
5
6
7
8
9
10
11
12
13

# 通过配置文件启动
virsh create /etc/libvirt/qemu/{虚拟机名}.xml

# 备份虚拟机配置文件
virsh dumpxml {虚拟机名} > {存储路径}

# 恢复备份虚拟机
virsh create {虚拟机名}

# 虚拟机克隆
virt-clone -o {虚拟机名} -n localhost -f /virtual/KVM/{虚拟机名}.qcow2

快照

1
2
3
4
5
6
7
8
9
10
11
# 创建快照
virsh snapshot-create {虚拟机名}

# 查看快照
virsh snapshot-list {虚拟机名}

# 恢复快照
virsh snapshot-revert {虚拟机名} {快照名称}

# 删除快照
virsh snapshot-delete {虚拟机名} {快照名称}
0%