Chemmy's Blog

chengming0916@gmail.com

0%

发表于 更新于 分类于 ， Valine：

堆排序算法（C#实现）

Excerpt

在软件设计相关领域，“堆（Heap）”的概念主要涉及到两个方面：一种是数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。另一种是垃圾收集存储区，是软件系统可以编程的内存区域。本文所说的堆指的是前者，另外，这篇文章中堆中元素的值均以整形为例堆排序的时间复杂度是O(nlog2n),与快速

在软件设计相关领域，“堆（Heap）”的概念主要涉及到两个方面：

一种是数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。

另一种是垃圾收集存储区，是软件系统可以编程的内存区域。

本文所说的堆指的是前者，另外，这篇文章中堆中元素的值均以整形为例

堆排序的时间复杂度是O(nlog2n),与快速排序达到相同的时间复杂度. 但是在实际应用中,我们往往采用快速排序而不是堆排序. 这是因为快速排序的一个好的实现,往往比堆排序具有更好的表现. 堆排序的主要用途,是在形成和处理优先级队列方面. 另外, 如果计算要求是类优先级队列(比如, 只要返回最大或者最小元素, 只有有限的插入要求等), 堆同样是很适合的数据结构.

**堆排序
**堆排序是一种选择排序。是不稳定的排序方法。时间复杂度为O(nlog2n)。
堆排序的特点是：在排序过程中，将排序数组看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。

基本思想
1.将要排序的数组创建为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置例入有序区，然后将新的无序区调整为大根堆。
重复操作，无序区在递减，有序区在递增。
初始时，整个数组为无序区，第一次交换后无序区减一，有序区增一。
每一次交换，都是大根堆的堆顶元素插入有序区，所以有序区保持是有序的。

大根堆和小根堆
堆：是一颗完全二叉树。
大根堆：所有节点的子节点比其自身小的堆
小根堆：所有节点的子节点比其自身大的堆

堆与数组的关系

堆是一种逻辑结构（形象的表示数据的存储格式），数组则是数据的实际存储结构（对应数据的存储地址），堆中的根节点与左右子节点在存储数组中的位置关系如下：假设根节点在数组中的位置（数组下标）为 i ，那么左节点在数组中的位置（数组下标）为 i * 2 + 1 ， 右节点在数组中的位置（数组下标）为 i * 2 + 2 。

以上是基本的知识点，具体代码如下所示：

1
<span>        //</span><span>堆排序算法（传递待排数组名，即：数组的地址。故形参数组的各种操作反应到实参数组上）</span><span><br></span><span>　　　　 private </span><span>static </span><span>void</span><span> HeapSortFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                BuildMaxHeap(array);    </span><span>//</span><span>创建大顶推（初始状态看做：整体无序）</span><span><br></span><span>　　　　　　　　　for</span><span> (</span><span>int</span><span> i </span><span>=</span><span> array.Length </span><span>-</span><span>1</span><span>; i </span><span>&gt;</span><span>0</span><span>; i</span><span>--</span><span>)<br>                {<br>                    Swap(</span><span>ref</span><span> array[</span><span>0</span><span>], </span><span>ref</span><span> array[i]); </span><span>//</span><span>将堆顶元素依次与无序区的最后一位交换（使堆顶元素进入有序区）</span><span><br></span><span>                    MaxHeapify(array, </span><span>0</span><span>, i); </span><span>//</span><span>重新将无序区调整为大顶堆</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }<br><br>        </span><span>///</span><span>&lt;summary&gt;</span><span><br>        </span><span>///</span><span> 创建大顶推（根节点大于左右子节点）<br>        </span><span>///</span><span>&lt;/summary&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="array"&gt;</span><span>待排数组</span><span>&lt;/param&gt;</span><span><br></span><span>　　　　 private </span><span>static </span><span>void</span><span> BuildMaxHeap(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>//</span><span>根据大顶堆的性质可知：数组的前半段的元素为根节点，其余元素都为叶节点</span><span><br></span><span>　　　　　　　　　for</span><span> (</span><span>int</span><span> i </span><span>=</span><span> array.Length </span><span>/</span><span>2</span><span>-</span><span>1</span><span>; i </span><span>&gt;=</span><span>0</span><span>; i</span><span>--</span><span>) </span><span>//</span><span>从最底层的最后一个根节点开始进行大顶推的调整</span><span><br></span><span>                {<br>                    MaxHeapify(array, i, array.Length); </span><span>//</span><span>调整大顶堆</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }<br><br>        </span><span>///</span><span>&lt;summary&gt;</span><span><br>        </span><span>///</span><span> 大顶推的调整过程<br>        </span><span>///</span><span>&lt;/summary&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="array"&gt;</span><span>待调整的数组</span><span>&lt;/param&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="currentIndex"&gt;</span><span>待调整元素在数组中的位置（即：根节点）</span><span>&lt;/param&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="heapSize"&gt;</span><span>堆中所有元素的个数</span><span>&lt;/param&gt;</span><span><br></span><span>　　　　 private </span><span>static </span><span>void</span><span> MaxHeapify(</span><span>int</span><span>[] array, </span><span>int</span><span> currentIndex, </span><span>int</span><span> heapSize)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> left </span><span>=</span><span>2</span><span>*</span><span> currentIndex </span><span>+</span><span>1</span><span>;    </span><span>//</span><span>左子节点在数组中的位置</span><span><br></span><span>　　　　　　　　　int</span><span> right </span><span>=</span><span>2</span><span>*</span><span> currentIndex </span><span>+</span><span>2</span><span>;   </span><span>//</span><span>右子节点在数组中的位置</span><span><br></span><span>　　　　　　　　　int</span><span> large </span><span>=</span><span> currentIndex;   </span><span>//</span><span>记录此根节点、左子节点、右子节点 三者中最大值的位置</span><span><br></span><span><br>                </span><span>if</span><span> (left </span><span>&lt;</span><span> heapSize </span><span>&amp;&amp;</span><span> array[left] </span><span>&gt;</span><span> array[large])  </span><span>//</span><span>与左子节点进行比较</span><span><br></span><span>                {<br>                    large </span><span>=</span><span> left;<br>                }<br>                </span><span>if</span><span> (right </span><span>&lt;</span><span> heapSize </span><span>&amp;&amp;</span><span> array[right] </span><span>&gt;</span><span> array[large])    </span><span>//</span><span>与右子节点进行比较</span><span><br></span><span>                {<br>                    large </span><span>=</span><span> right;<br>                }<br>                </span><span>if</span><span> (currentIndex </span><span>!=</span><span> large)  </span><span>//</span><span>如果 currentIndex != large 则表明 large 发生变化（即：左右子节点中有大于根节点的情况）</span><span><br></span><span>                {<br>                    Swap(</span><span>ref</span><span> array[currentIndex], </span><span>ref</span><span> array[large]);    </span><span>//</span><span>将左右节点中的大者与根节点进行交换（即：实现局部大顶堆）</span><span><br></span><span>                    MaxHeapify(array, large, heapSize); </span><span>//</span><span>以上次调整动作的large位置（为此次调整的根节点位置），进行递归调整</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }<br><br>        </span><span>///</span><span>&lt;summary&gt;</span><span><br>        </span><span>///</span><span> 交换函数<br>        </span><span>///</span><span>&lt;/summary&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="a"&gt;</span><span>元素a</span><span>&lt;/param&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="b"&gt;</span><span>元素b</span><span>&lt;/param&gt;</span><span><br></span><span>　　　　　private </span><span>static </span><span>void</span><span> Swap(</span><span>ref</span><span>int</span><span> a, </span><span>ref</span><span>int</span><span> b)<br>        {<br>            </span><span>int</span><span> temp </span><span>=</span><span>0</span><span>;<br>            temp </span><span>=</span><span> a;<br>            a </span><span>=</span><span> b;<br>            b </span><span>=</span><span> temp;<br>        }</span>

发表于 更新于 分类于 ， Valine：

YOLOv8目标检测：使用ONNX模型进行推理_onnx模型推理-CSDN博客

Excerpt

文章浏览阅读8.2k次，点赞46次，收藏119次。本文详细介绍了如何在COCO数据集上使用YOLOv8目标检测模型进行推理，涉及环境配置、代码实现（包括图像、视频和摄像头检测），以及展示ONNX模型在不同大小版本（YOLOv8n,YOLOv8s,YOLOv8m,YOLOv8l,YOLOv8x）上的实验结果。

基于COCO数据集的YOLOv8目标检测onnx模型推理

在本博客中，我们将探讨如何使用YOLOv8目标检测模型进行推理，包括图片，视频文件，摄像头实时检测，特别是ONNX在不同大小（YOLOv8n, YOLOv8s, YOLOv8m, YOLOv8l, YOLOv8x）的模型上进行的实验。我们还将讨论所需的环境配置，代码实现，以及如何展示推理结果。

环境配置

在详细描述环境配置和安装步骤之前，请确保您的系统已经安装了Python和pip。下面是详细的环境配置步骤，适用于基于YOLOv8模型进行目标检测的项目。

1. 安装必要的Python库

1
pip install onnxruntime-gpu==1.13.1 opencv-python==4.7.0.68 numpy==1.24.1 Pillow==9.4.0 -i https://pypi.tuna.tsinghua.edu.cn/simple/

如果您没有GPU或者不打算使用GPU，可以安装onnxruntime而不是onnxruntime-gpu：

1
pip install onnxruntime==1.13.1 opencv-python==4.7.0.68 numpy==1.24.1 Pillow==9.4.0 -i https://pypi.tuna.tsinghua.edu.cn/simple/

2. 验证安装

安装完成后，您可以通过运行Python并尝试导入安装的包来验证是否成功安装了所有必要的库：

1
import onnxruntime import cv2 import numpy import PIL

如果上述命令没有引发任何错误，那么恭喜您，您已成功配置了运行环境。

小贴士

  • 如果您在安装过程中遇到任何问题，可能需要更新pip到最新版本：pip install --upgrade pip。
  • 对于使用NVIDIA GPU的用户，确保您的系统已安装CUDA和cuDNN。onnxruntime-gpu要求系统预装这些NVIDIA库以利用GPU加速。

按照这些步骤，您应该能够成功配置环境并运行基于YOLOv8的目标检测项目了。

权重下载

YOLOv8模型的权重可以通过以下百度网盘链接下载：

请确保下载适合您需求的模型版本。

代码实现

以下是进行目标检测的整体代码流程，包括模型加载、图像预处理、推理执行、后处理及结果展示的步骤。

1
import cv2 import onnxruntime as ort from PIL import Image import numpy as np # 置信度 confidence_thres = 0.35 # iou阈值 iou_thres = 0.5 # 类别 classes = {0: 'person', 1: 'bicycle', 2: 'car', 3: 'motorcycle', 4: 'airplane', 5: 'bus', 6: 'train', 7: 'truck', 8: 'boat', 9: 'traffic light', 10: 'fire hydrant', 11: 'stop sign', 12: 'parking meter', 13: 'bench', 14: 'bird', 15: 'cat', 16: 'dog', 17: 'horse', 18: 'sheep', 19: 'cow', 20: 'elephant', 21: 'bear', 22: 'zebra', 23: 'giraffe', 24: 'backpack', 25: 'umbrella', 26: 'handbag', 27: 'tie', 28: 'suitcase', 29: 'frisbee', 30: 'skis', 31: 'snowboard', 32: 'sports ball', 33: 'kite', 34: 'baseball bat', 35: 'baseball glove', 36: 'skateboard', 37: 'surfboard', 38: 'tennis racket', 39: 'bottle', 40: 'wine glass', 41: 'cup', 42: 'fork', 43: 'knife', 44: 'spoon', 45: 'bowl', 46: 'banana', 47: 'apple', 48: 'sandwich', 49: 'orange', 50: 'broccoli', 51: 'carrot', 52: 'hot dog', 53: 'pizza', 54: 'donut', 55: 'cake', 56: 'chair', 57: 'couch', 58: 'potted plant', 59: 'bed', 60: 'dining table', 61: 'toilet', 62: 'tv', 63: 'laptop', 64: 'mouse', 65: 'remote', 66: 'keyboard', 67: 'cell phone', 68: 'microwave', 69: 'oven', 70: 'toaster', 71: 'sink', 72: 'refrigerator', 73: 'book', 74: 'clock', 75: 'vase', 76: 'scissors', 77: 'teddy bear', 78: 'hair drier', 79: 'toothbrush'} # 随机颜色 color_palette = np.random.uniform(100, 255, size=(len(classes), 3)) # 判断是使用GPU或CPU providers = [ ('CUDAExecutionProvider', { 'device_id': 0, # 可以选择GPU设备ID，如果你有多个GPU }), 'CPUExecutionProvider', # 也可以设置CPU作为备选 ] def calculate_iou(box, other_boxes): """ 计算给定边界框与一组其他边界框之间的交并比（IoU）。 参数： - box: 单个边界框，格式为 [x1, y1, width, height]。 - other_boxes: 其他边界框的数组，每个边界框的格式也为 [x1, y1, width, height]。 返回值： - iou: 一个数组，包含给定边界框与每个其他边界框的IoU值。 """ # 计算交集的左上角坐标 x1 = np.maximum(box[0], np.array(other_boxes)[:, 0]) y1 = np.maximum(box[1], np.array(other_boxes)[:, 1]) # 计算交集的右下角坐标 x2 = np.minimum(box[0] + box[2], np.array(other_boxes)[:, 0] + np.array(other_boxes)[:, 2]) y2 = np.minimum(box[1] + box[3], np.array(other_boxes)[:, 1] + np.array(other_boxes)[:, 3]) # 计算交集区域的面积 intersection_area = np.maximum(0, x2 - x1) * np.maximum(0, y2 - y1) # 计算给定边界框的面积 box_area = box[2] * box[3] # 计算其他边界框的面积 other_boxes_area = np.array(other_boxes)[:, 2] * np.array(other_boxes)[:, 3] # 计算IoU值 iou = intersection_area / (box_area + other_boxes_area - intersection_area) return iou def custom_NMSBoxes(boxes, scores, confidence_threshold, iou_threshold): # 如果没有边界框，则直接返回空列表 if len(boxes) == 0: return [] # 将得分和边界框转换为NumPy数组 scores = np.array(scores) boxes = np.array(boxes) # 根据置信度阈值过滤边界框 mask = scores > confidence_threshold filtered_boxes = boxes[mask] filtered_scores = scores[mask] # 如果过滤后没有边界框，则返回空列表 if len(filtered_boxes) == 0: return [] # 根据置信度得分对边界框进行排序 sorted_indices = np.argsort(filtered_scores)[::-1] # 初始化一个空列表来存储选择的边界框索引 indices = [] # 当还有未处理的边界框时，循环继续 while len(sorted_indices) > 0: # 选择得分最高的边界框索引 current_index = sorted_indices[0] indices.append(current_index) # 如果只剩一个边界框，则结束循环 if len(sorted_indices) == 1: break # 获取当前边界框和其他边界框 current_box = filtered_boxes[current_index] other_boxes = filtered_boxes[sorted_indices[1:]] # 计算当前边界框与其他边界框的IoU iou = calculate_iou(current_box, other_boxes) # 找到IoU低于阈值的边界框，即与当前边界框不重叠的边界框 non_overlapping_indices = np.where(iou <= iou_threshold)[0] # 更新sorted_indices以仅包含不重叠的边界框 sorted_indices = sorted_indices[non_overlapping_indices + 1] # 返回选择的边界框索引 return indices def draw_detections(img, box, score, class_id): """ 在输入图像上绘制检测到的对象的边界框和标签。 参数: img: 要在其上绘制检测结果的输入图像。 box: 检测到的边界框。 score: 对应的检测得分。 class_id: 检测到的对象的类别ID。 返回: 无 """ # 提取边界框的坐标 x1, y1, w, h = box # 根据类别ID检索颜色 color = color_palette[class_id] # 在图像上绘制边界框 cv2.rectangle(img, (int(x1), int(y1)), (int(x1 + w), int(y1 + h)), color, 2) # 创建标签文本，包括类名和得分 label = f'{classes[class_id]}: {score:.2f}' # 计算标签文本的尺寸 (label_width, label_height), _ = cv2.getTextSize(label, cv2.FONT_HERSHEY_SIMPLEX, 0.5, 1) # 计算标签文本的位置 label_x = x1 label_y = y1 - 10 if y1 - 10 > label_height else y1 + 10 # 绘制填充的矩形作为标签文本的背景 cv2.rectangle(img, (label_x, label_y - label_height), (label_x + label_width, label_y + label_height), color, cv2.FILLED) # 在图像上绘制标签文本 cv2.putText(img, label, (label_x, label_y), cv2.FONT_HERSHEY_SIMPLEX, 0.5, (0, 0, 0), 1, cv2.LINE_AA) def preprocess(img, input_width, input_height): """ 在执行推理之前预处理输入图像。 返回: image_data: 为推理准备好的预处理后的图像数据。 """ # 获取输入图像的高度和宽度 img_height, img_width = img.shape[:2] # 将图像颜色空间从BGR转换为RGB img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB) # 将图像大小调整为匹配输入形状 img = cv2.resize(img, (input_width, input_height)) # 通过除以255.0来归一化图像数据 image_data = np.array(img) / 255.0 # 转置图像，使通道维度为第一维 image_data = np.transpose(image_data, (2, 0, 1)) # 通道首 # 扩展图像数据的维度以匹配预期的输入形状 image_data = np.expand_dims(image_data, axis=0).astype(np.float32) # 返回预处理后的图像数据 return image_data, img_height, img_width def postprocess(input_image, output, input_width, input_height, img_width, img_height): """ 对模型输出进行后处理，提取边界框、得分和类别ID。 参数: input_image (numpy.ndarray): 输入图像。 output (numpy.ndarray): 模型的输出。 input_width (int): 模型输入宽度。 input_height (int): 模型输入高度。 img_width (int): 原始图像宽度。 img_height (int): 原始图像高度。 返回: numpy.ndarray: 绘制了检测结果的输入图像。 """ # 转置和压缩输出以匹配预期的形状 outputs = np.transpose(np.squeeze(output[0])) # 获取输出数组的行数 rows = outputs.shape[0] # 用于存储检测的边界框、得分和类别ID的列表 boxes = [] scores = [] class_ids = [] # 计算边界框坐标的缩放因子 x_factor = img_width / input_width y_factor = img_height / input_height # 遍历输出数组的每一行 for i in range(rows): # 从当前行提取类别得分 classes_scores = outputs[i][4:] # 找到类别得分中的最大得分 max_score = np.amax(classes_scores) # 如果最大得分高于置信度阈值 if max_score >= confidence_thres: # 获取得分最高的类别ID class_id = np.argmax(classes_scores) # 从当前行提取边界框坐标 x, y, w, h = outputs[i][0], outputs[i][1], outputs[i][2], outputs[i][3] # 计算边界框的缩放坐标 left = int((x - w / 2) * x_factor) top = int((y - h / 2) * y_factor) width = int(w * x_factor) height = int(h * y_factor) # 将类别ID、得分和框坐标添加到各自的列表中 class_ids.append(class_id) scores.append(max_score) boxes.append([left, top, width, height]) # 应用非最大抑制过滤重叠的边界框 indices = custom_NMSBoxes(boxes, scores, confidence_thres, iou_thres) # 遍历非最大抑制后的选定索引 for i in indices: # 根据索引获取框、得分和类别ID box = boxes[i] score = scores[i] class_id = class_ids[i] # 在输入图像上绘制检测结果 draw_detections(input_image, box, score, class_id) # 返回修改后的输入图像 return input_image def init_detect_model(model_path): # 使用ONNX模型文件创建一个推理会话，并指定执行提供者 session = ort.InferenceSession(model_path, providers=providers) # 获取模型的输入信息 model_inputs = session.get_inputs() # 获取输入的形状，用于后续使用 input_shape = model_inputs[0].shape # 从输入形状中提取输入宽度 input_width = input_shape[2] # 从输入形状中提取输入高度 input_height = input_shape[3] # 返回会话、模型输入信息、输入宽度和输入高度 return session, model_inputs, input_width, input_height def detect_object(image, session, model_inputs, input_width, input_height): # 如果输入的图像是PIL图像对象，将其转换为NumPy数组 if isinstance(image, Image.Image): result_image = np.array(image) else: # 否则，直接使用输入的图像（假定已经是NumPy数组） result_image = image # 预处理图像数据，调整图像大小并可能进行归一化等操作 img_data, img_height, img_width = preprocess(result_image, input_width, input_height) # 使用预处理后的图像数据进行推理 outputs = session.run(None, {model_inputs[0].name: img_data}) # 对推理结果进行后处理，例如解码检测框，过滤低置信度的检测等 output_image = postprocess(result_image, outputs, input_width, input_height, img_width, img_height) # 返回处理后的图像 return output_image if __name__ == '__main__': # 模型文件的路径 model_path = "yolov8n.onnx" # 初始化检测模型，加载模型并获取模型输入节点信息和输入图像的宽度、高度 session, model_inputs, input_width, input_height = init_detect_model(model_path) # 三种模式 1为图片预测，并显示结果图片；2为摄像头检测，并实时显示FPS； 3为视频检测，并保存结果视频 mode = 1 if mode == 1: # 读取图像文件 image_data = cv2.imread("street.jpg") # 使用检测模型对读入的图像进行对象检测 result_image = detect_object(image_data, session, model_inputs, input_width, input_height) # 将检测后的图像保存到文件 cv2.imwrite("output_image.jpg", result_image) # 在窗口中显示检测后的图像 cv2.imshow('Output', result_image) # 等待用户按键，然后关闭显示窗口 cv2.waitKey(0) elif mode == 2: # 打开摄像头 cap = cv2.VideoCapture() # 0表示默认摄像头，如果有多个摄像头可以尝试使用1、2等 # 检查摄像头是否成功打开 if not cap.isOpened(): print("Error: Could not open camera.") exit() # 初始化帧数计数器和起始时间 frame_count = 0 start_time = time.time() # 循环读取摄像头视频流 while True: # 读取一帧 ret, frame = cap.read() # 检查帧是否成功读取 if not ret: print("Error: Could not read frame.") break # 使用检测模型对读入的帧进行对象检测 output_image = detect_object(frame, session, model_inputs, input_width, input_height) # 计算帧速率 frame_count += 1 end_time = time.time() elapsed_time = end_time - start_time fps = frame_count / elapsed_time print(f"FPS: {fps:.2f}") # 将FPS绘制在图像上 cv2.putText(output_image, f"FPS: {fps:.2f}", (10, 30), cv2.FONT_HERSHEY_SIMPLEX, 1, (255, 255, 255), 2, cv2.LINE_AA) # 在窗口中显示当前帧 cv2.imshow("Video", output_image) # 按下 'q' 键退出循环 if cv2.waitKey(1) & 0xFF == ord('q'): break # 释放摄像头资源 cap.release() # 关闭窗口 cv2.destroyAllWindows() elif mode == 3: # 输入视频路径 input_video_path = 'kun.mp4' # 输出视频路径 output_video_path = 'kun_det.mp4' # 打开视频文件 cap = cv2.VideoCapture(input_video_path) # 检查视频是否成功打开 if not cap.isOpened(): print("Error: Could not open video.") exit() # 读取视频的基本信息 frame_width = int(cap.get(3)) frame_height = int(cap.get(4)) fps = cap.get(cv2.CAP_PROP_FPS) # 定义视频编码器和创建VideoWriter对象 fourcc = cv2.VideoWriter_fourcc(*'mp4v') # 根据文件名后缀使用合适的编码器 out = cv2.VideoWriter(output_video_path, fourcc, fps, (frame_width, frame_height)) # 初始化帧数计数器和起始时间 frame_count = 0 start_time = time.time() while True: ret, frame = cap.read() if not ret: print("Info: End of video file.") break # 对读入的帧进行对象检测 output_image = detect_object(frame, session, model_inputs, input_width, input_height) # 计算并打印帧速率 frame_count += 1 end_time = time.time() elapsed_time = end_time - start_time if elapsed_time > 0: fps = frame_count / elapsed_time print(f"FPS: {fps:.2f}") # 将处理后的帧写入输出视频 out.write(output_image) #（可选）实时显示处理后的视频帧 cv2.imshow("Output Video", output_image) if cv2.waitKey(1) & 0xFF == ord('q'): break # 释放资源 cap.release() out.release() cv2.destroyAllWindows() else: print("输入错误，请检查mode的赋值")

请根据您的需求调整置信度阈值、IOU阈值以及模型和mode的值（1为图片预测；2为摄像头检测； 3为视频检测）。

结果展示

推理完成后，您可以查看处理后的图像，如下所示：

  • 原始图片：

  • 检测后的图片：

请替换为您自己的图像路径来查看效果；或者其他两种模式（摄像头实时检测、视频文件检测）进行尝试。

总结

通过以上步骤，我们展示了如何使用YOLOv8进行目标检测的完整流程，从环境配置到代码实现和结果展示。此过程适用于YOLOv8目标检测任意模型进行检测任务。

希望这篇博客能够帮助您理解和实现基于YOLOv8的目标检测项目。如果有任何问题或需要进一步的帮助，请随时留言讨论。

发表于 更新于 分类于 ， Valine：

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个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

发表于 更新于 分类于 ， Valine：

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();

}

}

}

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

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

发表于 更新于 分类于 ， Valine：

冒泡排序算法（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)  评论()  编辑  收藏  举报

发表于 更新于 分类于 ， Valine：

归并排序算法（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次, 所以平均比较次数在两者之间. 它的主要问题还是在于在内存中需要双倍的空间.

发表于 更新于 分类于 ， Valine：

插入排序算法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>

。。。。

发表于 更新于 分类于 ， Valine：

Qt配置onnx_runtime

首先，onnx_runtime官方也给编译好的release版本，下载即可。但是在qt中配置有一个坑。
在这里插入图片描述
在Qt Creator中正常添加外部库，但是你会发现构建会找不到onnxruntime.lib，这是如果你替换成全路径，即把注释的部分换成下面的lib路径，直接指明onnxruntime.lib。这时构建成功，可以include <onnxruntime_cxx_api.h>，但是在运行你会遇到应用程序无法启动。
在这里插入图片描述
根据百度把onnxruntime.dll复制到.exe目录下。

OK，启动成功。

opencv读取视频流

居中显示，随意拉伸。
在这里插入图片描述
在这里插入图片描述
实现居中的逻辑：

1
// 调整QImage的大小以匹配QLabel的大小 QPixmap scaledPixmap = QPixmap::fromImage(qimg).scaled(ui->Origin_Video->size(), Qt::KeepAspectRatio, Qt::FastTransformation);

而在界面当中需要对窗口随意拉伸，这是就需要界面允许缩放。修改QLabel的属性：
在这里插入图片描述
修改成minimum，并给定最小宽度和高度。（还不知道原因，等有空学习一下）

最后opencv读取视频流并拉取每一帧显示在QLabel中，这里采用的是用一个Qtimer，定时去获取视频帧。

1
// 创建定时器，每隔一定时间显示下一帧 timer = new QTimer(this); connect(timer, &QTimer::timeout, this, &MainWindow::showNextFrame); timer->start(33); // 设置帧率为30FPS，即每隔33毫秒显示一帧

完整代码如下：

1
// 在槽函数中处理视频的加载和显示 void MainWindow::on_actionvideo_triggered() { camera->stop(); viewfinder->close(); QString curPath = QDir::homePath(); QString dlgTitle = "选择视频文件"; QString filter = "视频文件(*.wmv *.mp4);;所有文件(*.*)"; QString aFile = QFileDialog::getOpenFileName(this, dlgTitle, curPath, filter); if (aFile.isEmpty()) { return; } ui->dir_Edit->setText(aFile); currentSource = File; // 更新当前视频源为视频文件 displayVideo(); // 显示视频 } // 根据当前视频源显示视频的函数 void MainWindow::displayVideo() { if (currentSource == File) { std::string video_path = ui->dir_Edit->text().toLocal8Bit().constData(); cap.open(video_path); if (!cap.isOpened()) { qDebug() << "Error: Unable to open the video file"; return; } // 创建定时器，每隔一定时间显示下一帧 timer = new QTimer(this); connect(timer, &QTimer::timeout, this, &MainWindow::showNextFrame); timer->start(33); // 设置帧率为30FPS，即每隔33毫秒显示一帧 } else if (currentSource == Camera) { // 创建定时器，每隔一定时间显示下一帧 timer = new QTimer(this); connect(timer, &QTimer::timeout, this, &MainWindow::viewfinderchange); timer->start(33); // 设置帧率为30FPS，即每隔33毫秒显示一帧 // cameras = QCameraInfo::availableCameras(); //获取所有相机的列表 // camera = new QCamera(cameras[0]); //camera指向指定的摄像头 camera->setCaptureMode(QCamera::CaptureStillImage); //设定捕获模式 camera->setViewfinder(viewfinder); //设置取景器 camera->start(); } } // 显示下一帧的槽函数 void MainWindow::showNextFrame() { cv::Mat frame; cap >> frame; // 从视频流中获取一帧 if (frame.empty()) { cap.set(cv::CAP_PROP_POS_FRAMES, 0); // 如果视频结束，重新开始播放 cap >> frame; } currentFrame = frame; // 保存当前帧 displayCurrentFrame(); // 显示当前帧 } void MainWindow::displayCurrentFrame() { // 将OpenCV帧转换为QImage QImage qimg(currentFrame.data, currentFrame.cols, currentFrame.rows, currentFrame.step, QImage::Format_RGB888); qimg = qimg.rgbSwapped(); // 将格式从BGR转换为RGB // 调整QImage的大小以匹配QLabel的大小 QPixmap scaledPixmap = QPixmap::fromImage(qimg).scaled(ui->Origin_Video->size(), Qt::KeepAspectRatio, Qt::FastTransformation); // 将调整大小后的图像居中显示在QLabel中 centerImageInLabel(ui->Origin_Video, scaledPixmap); }

QCamra

居中显示，随意拉伸
在这里插入图片描述
QCamera其实同理，中间拉伸也用了一个QTimer定时获取QLabel的size。
QCamera的使用包括初始化一个camera和设置取景器viewfinder，viewfinder的作用就是控制图像在空间中的展示。

1
void MainWindow::on_actioncamera_triggered() { cameras = QCameraInfo::availableCameras(); //获取所有相机的列表 //qDebug() << "this is camera: "; if (cameras.count() > 0) { for(const QCameraInfo &cameraInfo:cameras) { qDebug() << cameraInfo.description(); } camera = new QCamera(cameras.at(0)); //初始化实例化一个相机对象 } //设置取景器 viewfinder = new QCameraViewfinder(ui->Origin_Video); camera->setViewfinder(viewfinder); centerCameraViewfinderInLabel(viewfinder, ui->Origin_Video); camera->start(); //开启相机 //设置默认摄像头参数 QCameraViewfinderSettings set; // set.setResolution(640, 480); //设置显示分辨率 set.setMaximumFrameRate(30); //设置帧率 camera->setViewfinderSettings(set); stopVideo(); ui->Origin_Video->setPixmap(QPixmap("")); currentSource = Camera; // 更新当前视频源为摄像头 viewfinder->show(); displayVideo(); // 显示视频 }

yolov8 onnx 推理

1
void MainWindow::on_actionTest_triggered() { // std::string projectBasePath = "./"; // Set your ultralytics base path QString qs = QCoreApplication::applicationDirPath(); std::string projectBasePath = qs.toLocal8Bit().constData(); bool runOnGPU = false; // Note that in this example the classes are hard-coded and 'classes.txt' is a place holder. Inference inf(projectBasePath + "/moust_best.onnx", cv::Size(640, 640), "mouse.txt", runOnGPU); std::string video_path = ui->dir_Edit->text().toLocal8Bit().constData(); // 读取视频文件 // cv::VideoCapture cap(projectBasePath + "/video/video.mp4"); cv::VideoCapture cap(video_path); if (!cap.isOpened()) { std::cout << "Error opening video file" << std::endl; return ; } cv::Mat frame; while (cap.read(frame)) { // 推断开始... std::vector<Detection> output = inf.runInference(frame); int detections = output.size(); std::cout << "Number of detections:" << detections << std::endl; for (int i = 0; i < detections; ++i) { Detection detection = output[i]; cv::Rect box = detection.box; cv::Scalar color = detection.color; // Detection box cv::rectangle(frame, box, color, 2); // Detection box text std::string classString = detection.className + ' ' + std::to_string(detection.confidence).substr(0, 4); cv::Size textSize = cv::getTextSize(classString, cv::FONT_HERSHEY_DUPLEX, 1, 2, 0); cv::Rect textBox(box.x, box.y - 40, textSize.width + 10, textSize.height + 20); cv::rectangle(frame, textBox, color, cv::FILLED); cv::putText(frame, classString, cv::Point(box.x + 5, box.y - 10), cv::FONT_HERSHEY_DUPLEX, 1, cv::Scalar(0, 0, 0), 2, 0); } // 推断结束... // 仅用于预览 float scale = 0.8; cv::resize(frame, frame, cv::Size(frame.cols*scale, frame.rows*scale)); cv::imshow("Inference", frame); if (cv::waitKey(1) == 27) { break; } } cap.release(); cv::destroyAllWindows(); }

多线程（onnx推理线程和界面主线程）

在这里插入图片描述
摄像头与onnx互不干扰，说明主界面线程与onnx推理是分开线程进行的，ok！

######################### 2024 05 09 更新 ##############################################

发表于 更新于 分类于 ， Valine：

1.环境准备

在这之前，需要先准备主机的环境，环境如下：

Ubuntu18.04
cuda11.3
pytorch:1.11.0
torchvision:0.12.0
在服务器上执行以下命令，

创建yolov8虚拟环境

1
conda create -n yolov8 python=3.8

进入虚拟环境

1
conda activate yolov8

安装pytorch v1.11.0

pytorch v1.11.0（torch1.11.0+cu1113 ，torchvision0.12.0+cu113）

1
# CUDA 11.3 pip install torch==1.11.0+cu113 torchvision==0.12.0+cu113 torchaudio==0.11.0 --extra-index-url https://download.pytorch.org/whl/cu113

下载yolov8的代码

先创建yolov8文件夹，存放等会要下载的yolov8代码mkdir yolov8
进入yolov8文件夹，cd yolov8
下载yolov8代码git clone https://github.com/ultralytics/ultralytics.git

其他配置

1
pip install ultralytics

2.VisDrone数据集准备

数据集下载

github链接上下载：官方链接
下载Task1：Object Detectino in Images下面的四个VisDrone-DET dataset数据集

下载好zip文件后，使用winscp将zip文件传输到远程服务器上。
在服务器上进入到zip文件所在的文件夹中使用unzip命令解压zip文件。
如： unzip VisDrone2019-DET-val.zip

数据集处理

和yolov5所需要的格式一致。参考yolov5数据处理方法。
主要是labels的生成，可以在yolov8下面新建一个visdrone2yolov.py文件。

1
from utils.general import download, os, Path def visdrone2yolo(dir): from PIL import Image from tqdm import tqdm def convert_box(size, box): # Convert VisDrone box to YOLO xywh box dw = 1. / size[0] dh = 1. / size[1] return (box[0] + box[2] / 2) * dw, (box[1] + box[3] / 2) * dh, box[2] * dw, box[3] * dh (dir / 'labels').mkdir(parents=True, exist_ok=True) # make labels directory pbar = tqdm((dir / 'annotations').glob('*.txt'), desc=f'Converting {dir}') for f in pbar: img_size = Image.open((dir / 'images' / f.name).with_suffix('.jpg')).size lines = [] with open(f, 'r') as file: # read annotation.txt for row in [x.split(',') for x in file.read().strip().splitlines()]: if row[4] == '0': # VisDrone 'ignored regions' class 0 continue cls = int(row[5]) - 1 # 类别号-1 box = convert_box(img_size, tuple(map(int, row[:4]))) lines.append(f"{cls} {' '.join(f'{x:.6f}' for x in box)}\n") with open(str(f).replace(os.sep + 'annotations' + os.sep, os.sep + 'labels' + os.sep), 'w') as fl: fl.writelines(lines) # write label.txt dir = Path('/home/yolov5/datasets/VisDrone2019') # datasets文件夹下Visdrone2019文件夹目录 # Convert for d in 'VisDrone2019-DET-train', 'VisDrone2019-DET-val', 'VisDrone2019-DET-test-dev': visdrone2yolo(dir / d) # convert VisDrone annotations to YOLO labels

正确执行代码后，会在’VisDrone2019-DET-train’, ‘VisDrone2019-DET-val’, ‘VisDrone2019-DET-test-dev三个文件夹内新生成labels文件夹，用以存放将VisDrone数据集处理成YoloV8格式后的数据标

修改数据配置文件

记事本或notepad++打开ultralytics-main\ultralytics\datasets\文件夹下的VisDrone.yaml文件，将其中path参数修改为VisDrone2019文件夹所在的路径。
在这里插入图片描述

3.训练/验证/导出

训练

打开终端（或者pycharm等IDE），进入虚拟环境，随后进入yolov8文件夹，在终端中输入下面命令，即可开始训练。

1
yolo task=detect mode=train model=yolov8s.pt data=datasets/VisDrone.yaml batch=16 epochs=100 imgsz=640 workers=0 device=0

验证

  1. val数据集上验证
    激活yolov8虚拟环境conda activate yolov8
    进入yolov8文件夹cd pyCode/yolov8/ultralytics/ultralytics/
    使用如下命令，即可完成对验证数据的评估。
    开始验证
1
yolo task=detect mode=val model=runs/detect/train4/weights/best.pt data=datasets/VisDrone.yaml device=0

验证结果如下。
在这里插入图片描述

  1. 在test数据集上验证
    将datasets/VisDrone.yaml文件中的val路径修改为：VisDrone2019-DET-test-dev/images
1
# Train/val/test sets as 1) dir: path/to/imgs, 2) file: path/to/imgs.txt, or 3) list: [path/to/imgs1, path/to/imgs2, ..] # path: ../datasets/VisDrone # dataset root dir path: /home/xxx/yolov5/datasets/VisDrone # dataset root dir train: VisDrone2019-DET-train/images # train images (relative to 'path') 6471 images val: VisDrone2019-DET-test-dev/images # val images (relative to 'path') 548 images VisDrone2019-DET-val/images test: VisDrone2019-DET-test-dev/images # test images (optional) 1610 images

在这里插入图片描述

使用如下命令，即可完成在VisDrone2019-DET-test-dev数据集上的评估。
开始验证

1
yolo task=detect mode=val model=runs/detect/train4/weights/best.pt data=datasets/VisDrone.yaml device=0

结果如下
在这里插入图片描述

导出

使用如下命令即可导出

1
yolo task=detect mode=export model=runs/detect/train4/weights/best.pt