当前位置: 首页 > news >正文

排序(七种排序)

1.插入排序

2.希尔排序

3.选择排序
4.堆排序
5.冒泡排序
6.快速排序
7.归并排序

 

 1.插入排序

        1.1思路

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

 

        1.2实现 

//插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; ++i){// [0, end] 有序,插入tmp依旧有序int end = i;int tmp = a[i + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}

2. 希尔排序

        2.1思路

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。

        2.2实现 

void ShellSort(int* a, int n)
{// 1、gap > 1 预排序// 2、gap == 1 直接插入排序int gap = n;while (gap > 1){gap = gap / 3 + 1;  // +1可以保证最后一次一定是1// gap = gap / 2;for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

3. 选择排序

        3.1思路

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完

  

        3.2实现 

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){//找出最大和最小值放在开头和结尾,然后begin++,end--int maxi = begin, mini = begin;for (int i = begin; 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和begin重叠,可能会重复交换if (begin == maxi){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

 4.堆排序

        4.1思路

堆排序 是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。
不知道堆的可以参考: 数据结构:堆的实现_元清加油的博客-CSDN博客

        4.2实现 

//向下调整法
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (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 = parent * 2 + 1;}else{break;}}
}// 排升序
void HeapSort(int* a, int 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;}
}

5.冒泡排序 

         5.1思路

冒泡排序非常的简单,相邻二个数比较大小,然后交换即可

        5.2实现 

void BubbleSort(int* a, int n)
{for (int j = 0; j < n; ++j){bool exchange = false;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){int tmp = a[i];a[i] = a[i - 1];a[i - 1] = tmp;exchange = true;}}if (exchange == false){break;}}
}

6.快速排序 

6.1霍尔快排法

        6.1.1思路

取第一个数为key,从左右出发,右边找小于key的数,左边找大于key的数,找到交换。直到左边大于右边,就交换key和左边的数

 

6.1.2 实现

void Swap(int* str1, int* str2)
{int temp = *str1;*str1 = *str2;*str2 = temp;
}
int PartSort1(int* a, int left, int right)
{int keyi = left;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort2(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}
int main()
{int arr[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(arr, 0, 9);for (int i = 0; i < 9; i++){printf("%d ", arr[i]);}return 0;
}

6.2挖坑法 

6.2.1思路

取第一个数为key,从左右出发,右边找小于key的数,把他设立为一个坑位,左边找大于key的数,把他设立为一个新的坑位。直到左边大于右边,就交换key和坑的数

 

6.2.2实现 

// 挖坑法
// [left, right]
int PartSort2(int* a, int left, int right)
{int key = a[left];int hole = left;while (left < right){// 右边找小while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;// 左边找大while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort2(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}
int main()
{int arr[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(arr, 0, 9);for (int i = 0; i < 9; i++){printf("%d ", arr[i]);}return 0;
}

 

6.3前后指针法 

6.3.1思路

取第一个数为key,初始时,prev指针指向序列开头,cur指针指向prev后一个位置。cur找小与key的数与(prev++)交换

 

6.3.2实现

// 前后指针法
// [left, right]
int PartSort3(int* a, int left, int right)
{int prev = left;int cur = left + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort2(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}
int main()
{int arr[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(arr, 0, 9);for (int i = 0; i < 9; i++){printf("%d ", arr[i]);}return 0;
}

 

 7.归并排序

7.1思路

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用 分治法(Divide andConquer) 的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

 

7.2实现 

//归并排序
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin == end)return;int mid = (begin + end) / 2;// [begin, mid] [mid+1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);// 归并两个区间// ...int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

 

 

 

 

 

 

 

相关文章:

排序(七种排序)

1.插入排序 2.希尔排序 3.选择排序 4.堆排序 5.冒泡排序 6.快速排序 7.归并排序 1.插入排序 1.1思路 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中&#xff0c;直到所有的记录插入完为 止&#xff0c;得到一个新的有序序列 1.2实现 //插入排…...

【工程优化问题】基于鲸鱼、萤火虫、灰狼优化算法的张力、压缩弹簧设计问题研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

sap ui5刷新页面的方式

1.第一种 window.location.reload();2.第二种 如果你想在UI5应用程序中使用MVC模式来处理页面刷新,可以通过重新加载当前路由来实现刷新。首先,确保你有一个Router对象实例: var oRouter = sap.ui.core.UIComponent.getRouterFor(this);然后&...

Java课题笔记~ Fastjson 概述

3.3 JSON串和Java对象的相互转换 学习完 json 后&#xff0c;接下来聊聊 json 的作用。 以后我们会以 json 格式的数据进行前后端交互。前端发送请求时&#xff0c;如果是复杂的数据就会以 json 提交给后端&#xff1b;而后端如果需要响应一些复杂的数据时&#xff0c;也需要…...

Arduino 入门学习笔记11 读写内置EEPROM

Arduino 入门学习笔记11 使用I2C读写EEPROM 一、Arduino 内置EEPROM介绍二、EEPROM 操作1. 包含EEPROM库&#xff1a;2. 写入数据到EEPROM&#xff1a;3. 从EEPROM读取数据4. 完整示例&#xff1a; 一、Arduino 内置EEPROM介绍 Arduino的内置EEPROM&#xff08;Electrically E…...

【Nginx】安装make后遇到/bin/sh: 第 0 行:cd: ../pcre-8.38: 没有那个文件或目录

遇到/bin/sh: 第 0 行:cd: ../pcre-8.38: 没有那个文件或目录 需安装pcre 下载 http://downloads.sourceforge.net/project/pcre/pcre/8.35/pcre-8.35.tar.gz 上传到/usr/local下 pcre解压编译 tar -zxvf pcre-8.35.tar.gz mv pcre-8.35 /usr/local/src/cd /usr/local/src/p…...

在Windows Server 2008上启用自动文件夹备份

要在Windows Server 2008上启用自动文件夹备份&#xff0c;您可以使用内置的Windows备份功能。下面是如何设置它的方法&#xff1a; 1. 点击“开始”按钮并选择“服务器管理器”&#xff0c;打开“服务器管理器”。 2. 在“服务器管理器”窗口中&#xff0c;单击左侧窗格中的“…...

数据结构—线性表的查找

7.查找 7.1查找的基本概念 问题&#xff1a;在哪里找&#xff1f;——查找表 查找表是由同一类型的数据元素&#xff08;或记录&#xff09;构成的集合。由于“集合”中的数据元素之间存在着松散的关系&#xff0c;因此查找表是一种应用灵便的结构。 问题&#xff1a;什么查找&…...

EndNote(一)【界面+功能介绍】

EndNote界面&#xff1a; 顶上小图标的介绍&#xff1a; ①&#xff1a;同步 ②&#xff1a;分享 ③&#xff1a;检索全文 对于第三个&#xff08;检索全文的功能&#xff09;&#xff1a; &#xff08;不做任何操作的情况下的界面&#xff0c;检索全文的按钮是灰的&…...

JWT令牌验证

目录 一、JWT介绍 二、安装依赖 三、登陆接口 1、令牌工具类 2、接口代码 四、说明 一、JWT介绍 JWT全称&#xff1a;JSON Web Token &#xff08;官网&#xff1a;JSON Web Tokens - jwt.io&#xff09; 定义了一种简洁的、自包含的格式&#xff0c;用于在通信双方以json…...

【微信小程序】下拉刷新功能实现

微信小程序开发系列 文章目录 前言一、onPullDownRefresh函数二、实现1.开启下拉刷新2.监听下拉事件 前言 在开发微信小程序中经常会需要下拉页面进行更新要页面数据的功能&#xff0c;微信小程序提供了onPullDownRefresh函数。该函数作用是监听用户下拉动作。 一、onPullDown…...

三角函数与圆,角度和弧度 (草稿,建设中)

目录 1 三角函数与圆&#xff0c;角度和弧度 1.1 三角形 1.2 圆形 2 角度 3 弧度 rad 4 角度&#xff0c;弧度的换算 2 三角函数 1 三角函数与圆&#xff0c;角度和弧度 1.1 三角形 角度弧长sin()cos()tan() 1.2 圆形 半径&#xff0c;周长&#xff0c;弧长半径面积 …...

AIGC 施展“物理魔法”,3D视觉突破“精度极限”

点击关注 文&#xff5c;姚悦&#xff0c;编&#xff5c;王一粟 “没有艺术&#xff0c;全是物理&#xff01;物理让你快乐&#xff0c;不是吗&#xff1f;” 近日&#xff0c;在世界计算机图形会议 SIGGRAPH 2023 上&#xff0c;英伟达创始人、CEO 黄仁勋宣布&#xff0c;将…...

redis 哨兵模式

目录 一、什么是哨兵模式 二、配置哨兵 三、启动哨兵 四、验证哨兵 五、复制延时 六、选举策略 一、什么是哨兵模式 哨兵也叫 sentinel&#xff0c;它的作用是能够在后台监控主机是否故障&#xff0c;如果故障了根据投票数自动将从库转换为主库。 二、配置哨兵 首先停止…...

java八股文面试[java基础]——String StringBuilder StringBuffer

String类型定义&#xff1a; final String 不可以继承 final char [] 不可以修改 String不可变的好处&#xff1a; hash值只需要算一次&#xff0c;当String作为map的key时&#xff0c; 不需要考虑hash改变 天然的线程安全 知识来源&#xff1a; 【基础】String、StringB…...

[oneAPI] 基于BERT预训练模型的命名体识别任务

[oneAPI] 基于BERT预训练模型的命名体识别任务 Intel DevCloud for oneAPI 和 Intel Optimization for PyTorch基于BERT预训练模型的命名体识别任务语料介绍数据集构建使用示例 命名体识别模型前向传播模型训练 结果 参考资料 比赛&#xff1a;https://marketing.csdn.net/p/f3…...

SSL证书如何使用?SSL保障通信安全

由于SSL技术已建立到所有主要的浏览器和WEB服务器程序中&#xff0c;因此&#xff0c;仅需安装数字证书或服务器证书就可以激活功能了。SSL证书主要是服务于HTTPS&#xff0c;部署证书后&#xff0c;网站链接就由HTTP开头变为HTTPS。 SSL安全证书主要用于发送安全电子邮件、访…...

postgresql 的递归查询

postgresql 的递归查询功能很强大&#xff0c;可以实现传统 sql 无法实现的事情。那递归查询的执行逻辑是什么呢&#xff1f;在递归查询中&#xff0c;我们一般会用到 union 或者 union all&#xff0c;他们两者之间的区别是什么呢&#xff1f; 递归查询的执行逻辑 递归查询的…...

Go语言进阶:函数、指针、错误处理

一、函数 函数是基本的代码块&#xff0c;用于执行一个任务。 Go 语言最少有个 main() 函数。 你可以通过函数来划分不同功能&#xff0c;逻辑上每个函数执行的是指定的任务。 函数声明包括函数名﹑形式参数列表﹑返回值列表&#xff08;可省略&#xff09;以及函数体。 fun…...

最强自动化测试框架Playwright(30)-JS句柄

在 Playwright 中&#xff0c;JSHandle 是一个表示浏览器中 JavaScript 对象的类。它提供了与网页中的 JavaScript 对象进行交互和操作的方法。 可以通过调用 Playwright中的 evaluateHandle 或 evaluate 方法来获取 JSHandle from playwright.sync_api import sync_playwrig…...

Ctfshow web入门 命令执行RCE篇 web29-web77 与 web118-web124 详细题解 全

Ctfshow 命令执行 web29 pregmatch是正则匹配函数&#xff0c;匹配是否包含flag&#xff0c;if(!preg_match("/flag/i", $c))&#xff0c;/i忽略大小写 可以利用system来间接执行系统命令 flag采用f*绕过&#xff0c;或者mv fl?g.php 1.txt修改文件名&#xff0c…...

【C++ STL之map,set,pair详解】

目录 一.map映射1.简介2.包含头文件及其初始化3.基本操作4.用迭代器正反遍历5.添加元素的四种方式6.元素的访问7.对比unordered_map&#xff0c;multimap 二.set集合1.简介2.包含头文件及其初始化3.基本操作4.元素的访问5.set&#xff0c;multiset&#xff0c;unordered_set&am…...

Python LEGB规则解析与应用

引言 推荐阅读 AI文本 OCR识别最佳实践 AI Gamma一键生成PPT工具直达链接 玩转cloud Studio 在线编码神器 玩转 GPU AI绘画、AI讲话、翻译,GPU点亮AI想象空间 资源分享 「java、python面试题」来自UC网盘app分享&#xff0c;打开手机app&#xff0c;额外获得1T空间 http…...

气象监测站:用科技感知气象变化

气象监测站是利用科学技术感知当地小气候变化情况的气象观测仪器&#xff0c;可用于农业、林业、养殖业、畜牧业、环境保护、工业等多个领域&#xff0c;提高对环境数据的利用率&#xff0c;促进产业效能不断提升。 气象监测站主要由气象传感器、数据传输系统、电源系统、支架…...

Linux debian12解压和压缩.rar文件教程

一、Debian12安装rar命令 sudo apt install rar二、使用rar软件 1.解压文件 命令格式&#xff1a; rar x 文件名.rar实例测试&#xff1a; [rootdoudou tmp]# rar x test.rar2.压缩文件 test是一个文件夹 命令格式&#xff1a; rar a 文件名.rar 文件夹名实例测试&#x…...

探析国际大文件传输的花费与降低开销的小妙招

随着全球化的不断发展&#xff0c;跨国企业日益增多&#xff0c;因此国外大文件传输也日益普遍。在这种背景下&#xff0c;国外大文件传输方式的需求也相应增加。本文旨在深入分析国外大文件传输的成本&#xff0c;并提出有效降低这些成本的方法。 一、国外大文件传输成本分析 …...

Linux中shell脚本——for、while循环及脚本练习

目录 一.for循环 1.1.基本格式 1.2.类C语言格式 二.while循环 2.1.基本格式 2.2.死循环语句 三.跳出循环 3.1.continue跳出循环 3.2.break跳出循环 四.常用循环 4.1.循环打印九九乘法表 4.2.循环ping测试某个网段网络连通性 4.3.while死循环实现猜数字游戏 4.4.数…...

【数字实验室】时钟切换

大部分开发者使用 BUFGCTRL 或 BUFGMUX进行时钟切换&#xff0c;它们在时钟切换上可以提供无毛刺输出。然而&#xff0c;了解所涉及的原理是有好处的。 当然&#xff0c;无论我们在同步逻辑中使用哪种技术&#xff0c;重要的是要确保在进行时钟切换时输出上没有毛刺。任何故障都…...

线性代数的学习和整理7:各种特殊效果矩阵特例(草稿-----未完成)

目录 1 矩阵 1.1 1维的矩阵 1.2 2维的矩阵 1.3 没有3维的矩阵---3维的是3阶张量 2 方阵 3 单位矩阵 3.1 单位矩阵的定义 3.2 单位矩阵的特性 3.3 为什么单位矩阵I是 [1,0;0,1] 而不是[0,1;1,0] 或[1,1;1,1] 3.4 零矩阵 3.4 看下这个矩阵 [0,1;1,0] 3.5 看下这个矩阵…...

springBoot 配置文件 spring.mvc.throw-exception-if-no-handler-found 参数的作用

在Spring Boot应用中&#xff0c;可以通过配置文件来控制当找不到请求处理器&#xff08;handler&#xff09;时是否抛出异常。具体的配置参数是spring.mvc.throw-exception-if-no-handler-found。 默认情况下&#xff0c;该参数的值为false&#xff0c;即当找不到请求处理器时…...