排序(一)插入排序,希尔排序,选择排序,堆排序,冒泡排序

目录

一.排序

1.插入排序

2.希尔排序

3.选择排序

4.堆排序

5.冒泡排序

二.整体代码

1.Sort.h

2.Sort.c

3.test.c

一.排序

1.插入排序

插入排序基本思想:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为 止，得到一个新的有序序列

实现过程单趟排序:将插入值与前一个数进行比较,如果大就直接插入到后面,如果小,将前一个数后移,继续与之前的比较,小的话插入空的位置,否则继续向前比较

        我们可以将每一个排序分为单趟和整体排序,了解单趟排序,对于整体排序,我们可以将它看作将数据一个一个的向里面插入

void InsertSort(int* a, int n)
{assert(a);for (int i = 0; i < n - 1; ++i){//单趟排序,[0,end]有序,将end + 1向其中插入int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}//插入的值比数组内所有值都小a[end + 1] = tmp;}
}

插入排序特性总结:

1.时间复杂度:O(N^2),顺序时最好,逆序时最坏

2.空间复杂度:O(1)

3.稳定性:稳定

4.当排序的数组越接近有序,算法的时间效率越高

2.希尔排序

我们将希尔排序分为预排序(使数组接近有序),然后直接插入排序

预排序:把间距为gap的值分为一组,进行插入排序

以gap为3为例的图

        当gap的值越大时,前面大的值可以更快的到后面,后面小的值可以更快的到前面,但是gap越大,数组内数据越不接近有序,而当gap为1的,就相当于插入排序

// 希尔排序
void ShellSort(int* a, int n)
{//gap>1相当于预排序,让数组接近有序int gap = n;while (gap > 1){gap = gap / 3 + 1;//+1保证了gap最后一次一定为1//gap==1相当于直接插入排序for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

希尔排序特性总结:

1.希尔排序是对插入排序的优化

2.当gap>1时为预排序,是为了让数组更接近有序,gap==1时数组已经基本有序,插入时就会较快.对于整个过程可以起到优化

3.稳定性:不稳定

4.gap的时间复杂度不好计算,因为gap的值不同

        在下图中我们可以看到对于一组数据插入排序和希尔排序的处理时间

我们可以看到希尔排序的处理速度相比于插入排序提升很大

3.选择排序

        选择排序:我们在begin和end的区间内寻找到最小值和最大值的下标,将最小值和最大值找到分别置于首和尾后,++begin,--end,缩小区间,继续寻找,直到搜索完整个区间

选择排序特性总结:

1.直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

2.时间复杂度：O(N^2)

3.空间复杂度：O(1)

4.稳定性：不稳定

我们可以看到选择排序的处理效率与直接插入排序差不多

4.堆排序

        堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆

堆排序在前面已经讲解过,在此不多解释

//向下调整
//小堆向下调整前提:左右子树都为小堆
//大堆向下调整前提:左右子树都为大堆
void AdjustDown(int* a, int n, int root)
{int parent = root;//将根节点位置给父节点int child = 2 * parent + 1;//子节点下标为2*parent+1while (child < n)//保证下标不越界{//找出左右孩子小的那个if (child + 1 < n && a[child + 1] > a[child]){++child;}//若孩子的值大于父亲则交换,并将孩子下标给父亲,重新计算孩子下标if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}//如果孩子大,则说明为小堆,不需要向下调整else{break;}}
}//堆排序
//1.升序建大堆
//2.降序建小堆
void HeapSort(int* a, int n)
{//建堆//假设树有N个节点,树高度:logN.时间复杂度:O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);//向下调整}int end = n - 1;//最后一个叶的下标while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

堆排序特性总结:

1. 堆排序使用堆来选数，效率就高了很多

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

5.冒泡排序

        冒泡排序:将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动,前后比较,大的就交换

// 冒泡排序
void BubbleSort(int* a, int n)
{assert(a);int end = n;while (end > 0){int exchange = 0;for (int i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}//如果一趟冒泡中没有发生交换,则说明已经有序,不需要冒泡if (exchange == 0){break;}}
}

冒泡排序特性总结:

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：稳定

二.整体代码

1.Sort.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>void PrintArray(int* a, int n);
void Swap(int* p1, int* p2);
void AdjustDown(int* a, int n, int root);
// 插入排序
void InsertSort(int* a, int n);// 希尔排序
void ShellSort(int* a, int n);// 选择排序
void SelectSort(int* a, int n);// 堆排序
void AdjustDown(int* a, int n, int root);
void HeapSort(int* a, int n);// 冒泡排序
void BubbleSort(int* a, int n);

2.Sort.c

#include "Sort.h"void PrintArray(int* a, int n)
{for (int i = 0; i < n; ++i){printf("%d ", a[i]);}printf("\n");
}// 插入排序
// 时间复杂度O(N^2),顺序有序时最好,逆序时最坏
//空间复杂度O(1)
void InsertSort(int* a, int n)
{assert(a);for (int i = 0; i < n - 1; ++i){//单趟排序,[0,end]有序,将end + 1向其中插入int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}//插入的值比数组内所有值都小a[end + 1] = tmp;}
}// 希尔排序
void ShellSort(int* a, int n)
{//gap>1相当于预排序,让数组接近有序int gap = n;while (gap > 1){gap = gap / 3 + 1;//+1保证了gap最后一次一定为1//gap==1相当于直接插入排序for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}// 选择排序
void SelectSort(int* a, int n)
{assert(a);int begin = 0, end = n - 1;while (begin < end){//在[bagin,end]之间找出最小数和最大数的下标int mini, maxi;mini = maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[begin], &a[mini]);//如果maxi和begin位置重叠,maxi需要修正if (begin == maxi){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}//向下调整
//小堆向下调整前提:左右子树都为小堆
//大堆向下调整前提:左右子树都为大堆
void AdjustDown(int* a, int n, int root)
{int parent = root;//将根节点位置给父节点int child = 2 * parent + 1;//子节点下标为2*parent+1while (child < n)//保证下标不越界{//找出左右孩子小的那个if (child + 1 < n && a[child + 1] > a[child]){++child;}//若孩子的值大于父亲则交换,并将孩子下标给父亲,重新计算孩子下标if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}//如果孩子大,则说明为小堆,不需要向下调整else{break;}}
}//堆排序
//1.升序建大堆
//2.降序建小堆
void HeapSort(int* a, int n)
{//建堆//假设树有N个节点,树高度:logN.时间复杂度:O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);//向下调整}int end = n - 1;//最后一个叶的下标while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}// 冒泡排序
void BubbleSort(int* a, int n)
{assert(a);int end = n;while (end > 0){int exchange = 0;for (int i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}//如果一趟冒泡中没有发生交换,则说明已经有序,不需要冒泡if (exchange == 0){break;}}
}

3.test.c

#include "Sort.h"// 测试排序的性能对比
void TestOP()
{srand(time(0));const int N = 10000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();BubbleSort(a5,  N);int end5 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("BubbleSort:%d\n", end5 - begin5);free(a1);free(a2);free(a3);free(a4);free(a5);
}void TestInsertSort()
{int a[] = { 3,2,4,6,7,9,11,1,0 };PrintArray(a, sizeof(a) / sizeof(int));InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestShellSort()
{int a[] = { 9,8,7,6,5,4,3,2,1};PrintArray(a, sizeof(a) / sizeof(int));ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestSelectSort()
{int a[] = {5,4,7,6,4,2,9,7,8 };PrintArray(a, sizeof(a) / sizeof(int));SelectSort (a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestHeapSort()
{int a[] = { 1,8,4,7,6,3,9,12,6 };PrintArray(a, sizeof(a) / sizeof(int));HeapSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestBubbleSort()
{int a[] = { 7,8,1,14,6,10,2,12,9 };PrintArray(a, sizeof(a) / sizeof(int));BubbleSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestInsertSort();TestShellSort();TestSelectSort();TestHeapSort();TestBubbleSort();TestOP();
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/456859.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

计算机网络原理总结C-网络层

计算机网络原理总结C-网络层

网络层 网络层提供的两种服务网际协议IP 虚拟互连网络IP地址子网掩码&#xff08;无分类编址CIDR&#xff09;IP地址和MAC地址IP数据报格式&#xff08;路由&#xff09;转发分组的流程 因特网的路由选择协议&#xff08;动态路由协议&#xff09; 网际控制报文协议ICMPIP多播…
阅读更多...
纯血鸿蒙的最难时刻才开始

纯血鸿蒙的最难时刻才开始

关注卢松松&#xff0c;会经常给你分享一些我的经验和观点。 纯血鸿蒙(HarmonyOS NEXT)也正式发布了&#xff0c;绝对是一个历史性时刻&#xff0c;但最难的鸿蒙第二个阶段&#xff0c;也就是生态圈的建设&#xff0c;才刚刚开始。 目前&#xff0c;我劝你现在不要升级到鸿蒙…
阅读更多...
最新版本jdbcutils集成log4j做详细sql日志、自动释放连接...等

最新版本jdbcutils集成log4j做详细sql日志、自动释放连接...等

maven坐标 <!-- MySQL 8 --><dependency><groupId>com.mysql</groupId><artifactId>mysql-connector-j</artifactId><version>8.0.33</version></dependency><!-- Druid连接池 --><dependency><groupId&…
阅读更多...
软考中级嵌入式系统设计师笔记分享（二）

软考中级嵌入式系统设计师笔记分享（二）

1.TTL 电路是电流控制器件&#xff0c;而CMOS 电路是电压控制器件。 2.TTL 电路的速度快&#xff0c;传输延迟时间短(5-10ns)&#xff0c;但是功耗大。 常见的串行总线有 SPI、II2C、USB、RS232/RS422/RS485、CAN等;高速串行总线主要有 SATA、PCIE、IEEE 1394、Rapidl0、USB 3…
阅读更多...
C# Unity 同步/异步编程和多线程什么关系？async/await和coroutine又是什么？

C# Unity 同步/异步编程和多线程什么关系？async/await和coroutine又是什么？

目录 不用模板生成的目录怎么这么丑啊 1.同步&#xff1f;异步&#xff1f;多线程&#xff1f; 2.async/await和coroutine&#xff1f; 证明 单线程中的同步/异步 同 异 多线程中的同步异步 同 异 1.同步&#xff1f;异步&#xff1f;多线程&#xff1f; 首先&#…
阅读更多...
模型选择拟合

模型选择拟合

1.通过多项式拟合交互探索概念 import math import numpy as np import torch from torch import nn from d2l import torch as d2l 2.使用三阶多项式来生成训练和测试数据的标签 max_degree 20 # 多项式的最大阶数 n_train, n_test 100, 100 # 训练和测试数据集大小 true…
阅读更多...
手动改造UPX壳，增加IAT保护

手动改造UPX壳，增加IAT保护

随便拿Delphi7&#xff0c;新建一个VCL窗体程序&#xff0c;画一个按钮&#xff0c;写两行代码。这一步骤讲究的是什么呢&#xff1f;率性而为&#xff0c;反正没什么卵用。比如&#xff0c;俺写的是这玩意。 <span style"color:#666666"><span style"…
阅读更多...
FFMPEG+Qt 实时显示本机USB摄像头1080p画面以及同步录制mp4视频

FFMPEG+Qt 实时显示本机USB摄像头1080p画面以及同步录制mp4视频

FFMPEGQt 实时显示本机USB摄像头1080p画面以及同步录制mp4视频 文章目录 FFMPEGQt 实时显示本机USB摄像头1080p画面以及同步录制mp4视频1、前言1.1 目标1.2 一些说明 2、效果3、代码3.1 思路3.2 工程目录3.3 核心代码 4、全部代码获取 1、前言 本文通过FFMPEG(7.0.2)与Qt(5.13.…
阅读更多...
YOLO系列入门：1、YOLO V11环境搭建

YOLO系列入门：1、YOLO V11环境搭建

YOLO了解 yolo检测原理 yolo是目标检测模型&#xff0c;目标检测包含物体分类、位置预测两个内容。目前yolo的开发公司官网为&#xff1a;https://docs.ultralytics.com/zh截止到目前2024年10月&#xff0c;最新的是yolo11。关于YOLO的介绍可以参考这篇文章&#xff1a;https…
阅读更多...
Python+Django+VUE 搭建深度学习训练界面 （持续ing）

Python+Django+VUE 搭建深度学习训练界面 （持续ing）

PythonDjangoVUE 搭建深度学习训练界面 &#xff08;持续ing&#xff09; 环境说明 Pycharm 专业版2024.1.4&#xff0c;社区版不支持网页开发 下载链接&#xff1a;https://www.jetbrains.com/pycharm/download/other.html 参考链接&#xff1a;https://www.quanxiaoha.co…
阅读更多...
es实现桶聚合

es实现桶聚合

目录 聚合 聚合的分类 DSL实现桶聚合 dsl语句 结果 聚合结果排序 限定聚合范围 总结 聚合必须的三要素&#xff1a; 聚合可配置的属性 DSL实现metric聚合 例如&#xff1a;我们需要获取每个品牌的用户评分的min,max,avg等值 只求socre的max 利用RestHighLevelClien…
阅读更多...
BIO，NIO，直接内存，零拷贝

BIO，NIO，直接内存，零拷贝

前置知识 什么是Socket&#xff1f; Socket是应用层与TCP/IP协议族通信的中间软件抽象层&#xff0c;它是一组接口&#xff0c;一般由操作系统提供。在设计模式中&#xff0c;Socket其实就是一个门面模式&#xff0c;它把复杂的TCP/IP协议处理和通信缓存管理等等都隐藏在Sock…
阅读更多...
vue3使用i18n做国际化多语言，实现常量跟随语言切换翻译

vue3使用i18n做国际化多语言，实现常量跟随语言切换翻译

因为我有一个常量的配置文件在项目中&#xff0c;而且有中文内容&#xff0c;我想在切换语言的时候&#xff0c;跟着这个翻译也实时切换&#xff0c;就可以使用computed计算属性实现。 把name改成下面的样子&#xff1a; name: computed(() > t(pad.regularMode)), 就可以…
阅读更多...
分享一款录屏、直播软件

分享一款录屏、直播软件

光音录屏 光音录屏 是新一代的录屏工具&#xff0c;跟传统录屏工具相比&#xff0c;它不仅可以录制屏幕&#xff0c;还可以同时录制「人像 屏幕」&#xff0c;此外它还提供了美颜、虚拟背景、绿幕抠像、图片、文本编辑、字幕、白板等更多高级功能。你可以将录制好的视频&…
阅读更多...
ue5实现数字滚动增长

ue5实现数字滚动增长

方法1 https://www.bilibili.com/video/BV1h14y197D1/?spm_id_from333.999.0.0 b站教程 重写loop节点 方法二 写在eventtick里
阅读更多...
ffmpeg视频滤镜: 色温- colortemperature

ffmpeg视频滤镜: 色温- colortemperature

滤镜简述 colortemperature 官网链接 》 FFmpeg Filters Documentation 这个滤镜可以调节图片的色温&#xff0c;色温值越大显得越冷&#xff0c;可以参考一下下图&#xff1a; 咱们装修的时候可能会用到&#xff0c;比如选择灯还有地板的颜色的时候&#xff0c;选暖色调还是…
阅读更多...
多厂商的实现不同vlan间通信

多厂商的实现不同vlan间通信

Cisco单臂路由 Cisco路由器配置 -交换机配置 -pc配置 华三的单臂路由 -路由器配置 -华三的接口默认是打开的 -pc配置及ping的结果 -注意不要忘记配置默认网关 Cisco-SVI -交换机的配置 -创建vlan -> 设置物理接口对应的Acess或Trunk -> 进入vlan接口&#xff0c;打开接…
阅读更多...
【纯血鸿蒙】HarmonyOS和OpenHarmony 的区别

【纯血鸿蒙】HarmonyOS和OpenHarmony 的区别

一、开源鸿蒙&#xff08;Open Harmony&#xff09; 鸿蒙系统愿来的设计初衷&#xff0c;就是让所有设备都可以运行一个系统&#xff0c;但是每个设备的运算能力和功能都不同&#xff0c;所以内核的设计上&#xff0c;采用了微内核的设计&#xff0c;除了最基础的功能放在内核…
阅读更多...
mfc之tab标签控件的使用--附TabSheet源码

mfc之tab标签控件的使用--附TabSheet源码

TabSheet源码 TabSheet.h #if !defined(AFX_TABSHEET_H__42EE262D_D15F_46D5_8F26_28FD049E99F4__INCLUDED_) #define AFX_TABSHEET_H__42EE262D_D15F_46D5_8F26_28FD049E99F4__INCLUDED_#if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 // TabSheet.h : …
阅读更多...
C++面向对象编程学习

C++面向对象编程学习

C面向对象编程学习 前言一、C面向对象编程二、知识点学习1. 定义一个类1.1 使用struct定义1.2 使用class定义1.3 struct和class的区别 2. 类的定义方式2.1 单文件定义&#xff08;Inline Definition&#xff09;2.2 分离定义&#xff08;Separate Definition&#xff09;2.3 头…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023