排序算法及源代码
堆排序:
在学习堆之后我们知道了大堆和小堆,对于大堆而言第一个节点就是对大值,对于小堆而言,第一个值就是最小的值。如果我们把第一个值与最后一个值交换再对最后一个值前面的数据重新建堆,如此下去就可以实现建堆排序。
建堆的两种方法:
向上调整建堆:
向上调整建堆的思路是从第一个开始先后添加数据,在每次到一个数据是如果比父节点大(小)就与父节点交换位置并继续向上调整。
算法复杂度:O(N*logN)
向下调整建堆:
因为对于大(小)堆来说它的左右子树也都应该是大(小)堆,以此类推我们最小的数也应该是大(小)堆,于是我们就从最小的树开始建堆。
算法复杂度:O(N)
插入排序:
直接插入排序是认为要插入数之前的所有数据已经排序好,用一个tmp临时变量存储要插入的值,如果要插入值的前一个数据比他大,那么就向后覆盖,接着继续往前比,直到遇到比要插入值小的数据,将要插入值插入在该数据的后一位。
希儿排序:
事实上就是插入排序的升级版,对插入排序进行调整使数组趋于有序,最后一次进行一次插入排序。
选择排序:
选择排序是从数据的首端去进行选择,遍历一遍数组取选出最大值和最小值,选出后交换放在两端排序,继续去选择。注意的是如果最大值是第一个数据,后面交换时会出现数据被替代的情况,这种情
况下我们需要在交换后将最大值下标指向最小值下标。
快速排序:
递归:
非递归 :
归并排序:
递归:
非递归:
计数排序 :
其思想就是利用一个数组,数组名表示需要排序的数组里的数据,其大小就是出现次数,最后从大到小存在一个数组里。
#include "SORT.h"void swap(int* a, int* b)
{//printf("%d %d --", *a, *b);int tmp = *a;*a = *b;*b = tmp;//printf("%d %d\n", *a, *b);
}/*******************************************************************************/
/*---------------------------------堆排序------------------------------------- */
/*******************************************************************************/
void heapSort_F(int* arr,int n)//向下调整建堆
{//升序建大堆int last_father = (n - 1) / 2; //找到第一个父while (last_father != -1){int father = last_father;int child = father * 2 + 1;while (child <= n){if (child + 1 <= n && arr[child + 1] > arr[child]) //找到最大的孩子{++child;}if (arr[father] < arr[child]) //孩子比父亲大就交换{int tmp = arr[father];arr[father] = arr[child];arr[child] = tmp;}father = child; //继续向下(大的往上走作为父)child = father * 2 + 1;} //大堆好了--last_father;}while (n){//交换首尾巴size--int tmp = arr[0];arr[0] = arr[n];arr[n] = tmp;--n;int father = 0;int child = father * 2 + 1;while (child <= n) //向下找大的作为父{if (child + 1 <= n){if (arr[child + 1] > arr[child])++child;}if (arr[father] < arr[child]){int tmp = arr[father];arr[father] = arr[child];arr[child] = tmp;}father = child;child = father * 2 + 1;}}
}void heapSort_S(int* arr, int n)//向上调整建堆
{//降序建小堆for (int i = 1; i <= n; i++) //从前往后插入,每插入一个判断上面的父是否需要向上改变{int child = n;while (child){int father = (child - 1) / 2;if (arr[father] > arr[child]){int tmp = arr[child];arr[child] = arr[father];arr[father] = tmp;}child = father;}}while (n){int tmp = arr[0];arr[0] = arr[n];arr[n] = tmp;--n;int father = 0;int child = father * 2 + 1;while (child <= n){if (child + 1 <= n){if (arr[child + 1] < arr[child])++child;}if (arr[father] > arr[child]){int tmp = arr[father];arr[father] = arr[child];arr[child] = tmp;}father = child;child = father * 2 + 1;}}
}
/*=======================================================================================*/
/*=======================================================================================*//*******************************************************************************/
/*--------------------------------插入排序------------------------------------ */
/*******************************************************************************/
void InsertSort(int* arr, int n)
{int end = 0;while (end != n - 1){++end;int val = arr[end];int change = end;while (change != 0){if (arr[change - 1] > val){arr[change] = arr[change - 1];--change;}else break;}arr[change] = val;}
}
//void InsertSort(int* a, int n)
//{
// // [0, n-1]
// for (int i = 0; i < n - 1; i++)
// {
// // [0, n-2]是最后一组
// // [0,end]有序 end+1位置的值插入[0,end],保持有序
// 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* arr, int n)
{int gap = n;while(gap>1){gap = gap / 3 + 1;//for (size_t j=0; j < gap; j++)//{// for (size_t i = j; i < n-gap; i+=gap) //一组一组for (size_t i = 0; i < n - gap; ++i) //多组并着走{int end = i;int tmp = arr[end + gap];while (end >= 0){if (tmp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}//}}
}
/*=======================================================================================*/
/*=======================================================================================*//*******************************************************************************/
/*------------------------------ 选择排序 ---------------------------------- */
/*******************************************************************************/
void SelectSort(int* arr, int n)
{int start = 0; int end = n - 1;while (start < end){int mini = start;int maxi = end;for (int i = start; i <= end; i++){if (arr[i] < arr[mini])mini = i;if (arr[i] > arr[maxi])maxi = i;}swap(&arr[start], &arr[mini]);if (start == maxi){maxi = mini;}swap(&arr[end], &arr[maxi]);++start;--end;}
}
/*=======================================================================================*/
/*=======================================================================================*//*******************************************************************************/
/*--------------------------------快速排序------------------------------------ */
/*******************************************************************************/
int get_midi(int* arr, int left, int right) //优化--三值取中
{int midi = (left + right) / 2;if (arr[midi] < arr[left]){if (arr[midi] > arr[right])return midi;else{if (arr[left] > arr[right])return left;else return right;}}else{if (arr[midi] < arr[right])return midi;else{if (arr[left] > arr[right])return left;else return right;}}
}
// 霍尔版
int partSort1(int* arr, int left, int right)
{if (right - left < 10)//小区间优化{InsertSort(&arr[left], right - left + 1);}int midi = get_midi(arr, left, right);int keyi = left;swap(&arr[midi], &arr[keyi]);int key = arr[left];int begin = left, end = right;while (begin < end){//向右找小while (arr[end] >= key && begin < end){--end;}//向左找大while (arr[begin] <= key && begin < end){++begin;}swap(&arr[begin], &arr[end]);}swap(&arr[keyi], &arr[end]);return begin;
}
// 双指针
int partSort2(int* arr, int left, int right)
{int keyi = left;int key = arr[left];int prev = left;int cur = prev + 1;while (cur<=right){if (arr[cur] < key && ++prev != cur)swap(&arr[cur], &arr[prev]);++cur;}swap(&arr[prev], &arr[keyi]);return prev;
}void QuickSort(int* arr, int left, int right)
{if (left >= right)return;else{int begin = partSort2(arr, left, right); //双指针//int begin = partSort1(arr, left, right); //霍尔版QuickSort(arr, left, begin - 1);QuickSort(arr, begin + 1, right);}}
/*=======================================================================================*/
/*=======================================================================================*//*******************************************************************************/
/*---------------------------快速排序(非递归)------------------------------- */
/*******************************************************************************/
void quickSortNonR(int* arr, int left, int right)
{ST st;STinit(&st);STpush(&st, left);STpush(&st, right);while (!STEmpty(&st)){int end = STtop(&st);STpop(&st);int begin = STtop(&st);STpop(&st);int mid = partSort1(arr, begin, end);if (mid - 1 > begin){STpush(&st, begin);STpush(&st, mid - 1);}if (mid + 1 < end){STpush(&st, mid + 1);STpush(&st, end);}}
}
/*=======================================================================================*/
/*=======================================================================================*//*******************************************************************************/
/*--------------------------------归并排序------------------------------------ */
/*******************************************************************************/
void _mergeSort(int* arr, int* tmp, int begin, int end)
{if (begin >= end)return;int mid = (begin + end) / 2;_mergeSort(arr, tmp, begin, mid);_mergeSort(arr, tmp, mid + 1, end);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[i++] = arr[begin1++];}else{tmp[i++] = arr[begin2++];}}while (begin1 <= end1)tmp[i++] = arr[begin1++];while (begin2 <= end2)tmp[i++] = arr[begin2++];memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void mergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_mergeSort(arr, tmp, 0, n-1);free(tmp);
}
/*=======================================================================================*/
/*=======================================================================================*//*******************************************************************************/
/*---------------------------归并排序(非递归)------------------------------- */
/*******************************************************************************/
void mergeSortNonR(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);int gap = 1;while (gap < n){for (int i = 0; i < n; i += gap * 2){int j = i;int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;if (begin2 >= n)break;if (end2 >= n)end2 = n - 1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[j++] = arr[begin1++];}else{tmp[j++] = arr[begin2++];}}while (begin1 <= end1)tmp[j++] = arr[begin1++];while (begin2 <= end2)tmp[j++] = arr[begin2++];memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tmp);
}
/*=======================================================================================*/
/*=======================================================================================*//*******************************************************************************/
/*--------------------------------计数排序------------------------------------ */
/*******************************************************************************/void count_Sort(int* arr, int sz)
{int max = arr[0];int min = arr[0];for (int i = 0; i < sz; i++){if (arr[i] > max)max = arr[i];if (arr[i] < min)min = arr[i];}int* tmp = (int*)calloc(max - min + 1, sizeof(int));for (int i = 0; i < sz; i++){tmp[arr[i] - min]++;}int i = 0;for (int j = 0; j < max - min + 1; j++){while (tmp[j]--){arr[i++] = j + min;}}
}/*=======================================================================================*/
/*=======================================================================================*/
相关文章:

排序算法及源代码
堆排序: 在学习堆之后我们知道了大堆和小堆,对于大堆而言第一个节点就是对大值,对于小堆而言,第一个值就是最小的值。如果我们把第一个值与最后一个值交换再对最后一个值前面的数据重新建堆,如此下去就可以实现建堆排…...
力扣第206题“反转链表”
在本篇文章中,我们将详细解读力扣第206题“反转链表”。通过学习本篇文章,读者将掌握如何使用迭代和递归的方法来解决这一问题,并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释,以便于理解。 问题描述 力扣第…...

多模态大模型解读
目录 1. CLIP 2. ALBEF 3. BLIP 4. BLIP2 参考文献 (2023年)视觉语言的多模态大模型的目前主流方法是:借助预训练好的LLM和图像编码器,用一个图文特征对齐模块来连接,从而让语言模型理解图像特征并进行深层次的问…...
React是什么?
theme: condensed-night-purple highlight: atelier-cave-light React是什么? 官方的解释是:A JavaScript library for building user interfaces用于构建用户界面的 JavaScript 库 那为什么要选择用React呢? 原生的HTML、CSS、JavaScrip的…...

创新入门 | 病毒循环Viral Loop是什么?为何能实现指数增长
今天,很多高速增长的成功创业公司都在采用”病毒循环“的策略去快速传播、并扩大用户基础。究竟什么是“病毒循环”?初创公司的创始人为何需要重视这个策略?这篇文章中将会一一解答与病毒循环有关的各种问题。 一、什么是病毒循环(…...

鸿蒙HarmonyOS实战:渲染控制、路由案例
条件渲染 简单来说,就是动态控制组件的显示与隐藏,类似于vue中的v-if 但是这里写法就是用if、else、else if看起来更像是原生的感觉 效果 循环渲染 我们实际开发中,数据一般是后端返回来的对象格式,对此我们需要进行遍历&#…...

【Linux】进程控制2——进程等待(waitwaitpid)
1. 进程等待必要性 我们知道,子进程退出,父进程如果不管不顾,就可能造成"僵尸进程”的问题,进而造成内存泄漏。另外,进程一旦变成僵尸状态,那就刀枪不入,“杀人不眨眼”的kill -9 也无能为…...
SpringBoot 统计接口调用耗时的多种方式
在实际开发中,了解项目中接口的响应时间是必不可少的事情。SpringBoot 项目支持监听接口的功能也不止一个,接下来我们分别以 AOP、ApplicationListener、Tomcat 三个方面去实现三种不同的监听接口响应时间的操作。 AOP 首先我们在项目中创建一个类 &am…...

Linux系统安装Ruby语言
Ruby是一种面向对象的脚本语言,由日本的计算机科学家松本行弘设计并开发,Ruby的设计哲学强调程序员的幸福感,致力于简化编程的复杂性,并提供一种既强大又易于使用的工具。其语法简洁优雅,易于阅读和书写,使…...
网络安全练气篇——OWASP TOP 10
1、什么是OWASP? OWASP(开放式Web应用程序安全项目)是一个开放的社区,由非营利组织 OWASP基金会支持的项目。对所有致力于改进应用程序安全的人士开放,旨在提高对应用程序安全性的认识。 其最具权威的就是“10项最严重…...
python实现进度条的方法和实现代码
在Python中,有多种方式可以实现进度条。这里,我将介绍七种常见的方法:使用tqdm(这是一个外部库,非常流行且易于使用)、rich、click、progressbar2等库以及纯Python的print函数与time库来模拟进度条。 目录…...

被拷打已老实!面试官问我 #{} 和 ${} 的区别是什么?
引言:在使用 MyBatis 进行数据库操作时,#{} 和 ${} 的区别是面试中常见的问题,对理解如何在 MyBatis 中安全有效地处理 SQL 语句至关重要。正确使用这两种占位符不仅影响应用的安全性,还涉及到性能优化。 题目 被拷打已老实&…...
C# —— while循环语句
作用 让顺序执行的代码 可以停下来 循环执行某一代码块 // 条件分支语句: 让代码产生分支 进行执行 // 循环语句 : 让代码可以重复执行 语法 while循环 while (bool值) { 循环体(条件满足时执行的代码块) …...
力扣第205题“同构字符串”
在本篇文章中,我们将详细解读力扣第205题“同构字符串”。通过学习本篇文章,读者将掌握如何使用哈希表来解决这一问题,并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释,以便于理解。 问题描述 力扣第205题“…...
探索RESTful API开发,构建可扩展的Web服务
介绍 当我们浏览网页、使用手机应用或与各种互联网服务交互时,我们经常听到一个术语:“RESTful API”。它听起来很高深,但实际上,它是构建现代网络应用程序所不可或缺的基础。 什么是RESTful API? 让我们将RESTful …...
苹果安卓网页的H5封装成App的应用和原生开发的应用有什么不一样?
H5封装类成App的应用和原生应用有什么不一样?——一对比谈优缺点 1. 开发速度和复用性 H5封装的App优势:一次编写,多平台运行。你只需要使用一种语言编写代码,就可以发布到不同的平台,降低开发成本。 原生应用优势&…...

IO流2.
字符流-->字符流的底层其实就是字节流 public class Stream {public static void main(String[] args) throws IOException {//1.创建对象并关联本地文件FileReader frnew FileReader("abc\\a.txt");//2.读取资源read()int ch;while((chfr.read())!-1){System.out…...

详解MySQL中的PERCENT_RANK函数
目录 1. 引入1. 基本使用2:分组使用3:处理重复值4. 使用优势4.1 手动计算百分等级4.2 使用 PERCENT_RANK 的优势4.3 使用 PERCENT_RANK 5. 总结 在 MySQL 中,PERCENT_RANK 函数用于计算一个值在其分组中的百分等级。 它的返回值范围是从 0 …...
宏任务与微任务
一、宏任务 1、概念 指消息队列中等地被主线程执行的事件 2、种类 script主代码块、setTimeout 、setInterval 、nodejs的setImmediate 、MessageChannel(react的fiber用到)、postMessage、网络I/O、文件I/O、用户交互的回调等事件、UI渲染事件&#x…...

昇思大模型学习·第一天
mindspore快速入门回顾 导入mindspore包 处理数据集 下载mnist数据集进行数据集预处理 MnistDataset()方法train_dataset.get_col_names() 打印列名信息使用create_tuple_iterator 或create_dict_iterator对数据集进行迭代访问 网络构建 mindspore.nn: 构建所有网络的基类用…...

Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...

k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...