排序算法合集

F B I W a r n i n g : \color{red}FBI \qquad Warning: FBIWarning:

本人没有完整的计算机科班的教育经历,但是一直在兢兢业业,努力学习。

这些排序函数都是自己零零散散写的,也没有经过深思熟虑和优化,纯粹是为了自娱自乐。

  1. 冒泡排序:

代码里有两种实现方式,感觉第二种比较正宗,第一种跟插入排序相似度很高。

int bubbleSortInc(int data[], int size) {if (size <= 0){return -1;}for (int i = 0; i <= size - 1; i++) {for (int j = 0; j < i; j++){if (data[j] > data[j + 1]){int tmp = data[j];data[j] = data[j + 1];data[j + 1] = tmp;}}}return 0;
}
int bubbleSortDec(int data[], int size) {if (size <= 0){return -1;}for (int i = size - 1; i >= 0; i--) {for (int j = 0; j < i; j++){if (data[j] > data[j + 1]){int tmp = data[j];data[j] = data[j + 1];data[j + 1] = tmp;}}}return 0;
}
  1. 插入排序:

此处可以看出,插入排序和冒泡排序还是有很大的不同。

int insertSort(int data[], int size) {int cnt = 0;if (size <= 1){return 0;}for (int i = 0; i < size - 1; i++){if (data[i] > data[i + 1]){int tmp = data[i + 1];data[i + 1] = data[i];data[i] = tmp;for (int j = i; j > 0; j--){if (data[j] < data[j - 1]){int tmp2 = data[j];data[j] = data[j - 1];data[j - 1] = tmp2;}}}}return cnt;
}
  1. 选择排序

按照次序,每次挑选一个最小的,放到相应的次序位置。

int selectLeast(int data[], int datalen, int idx) {for (int i = idx + 1; i < datalen; i++){if (data[idx] > data[i]){idx = i;}}return idx;
}int selectionSort(int data[], int datalen) {for (int i = 0; i < datalen; i++){int least = selectLeast(data, datalen, i);if (least != i) {int tmp = data[i];data[i] = data[least];data[least] = tmp;}}return 0;
}
  1. shell排序
void shellInsert(int arr[],int arrsize, int dk) {for (int i = dk ;i <= arrsize - 1;i ++){if (arr[i] < arr[i-dk]){int tmp = arr[i]; int j = i - dk;for (;j >= 0 && tmp < arr[j];j -= dk){arr[j + dk] = arr[j];}arr[j + dk] = tmp;}}
}void shellSort(int arr[], int size, int delta[], int deltasize) {for (int i = 0;i < deltasize; i ++){shellInsert(arr, size, delta[i]);}
}
  1. 二分插入排序
void binaryInsertSort(int* data,int size) {for (int i = 1;i < size;i ++){int tmp = data[i];int low = 0;int high = i - 1;while (low <= high) {int m = (low + high ) / 2;if (data[i] < data[m]){high = m - 1;}else {low = m + 1;}}for ( int j = i - 1;j >= high + 1; j --){data[j + 1] = data[j];}data[high + 1] = tmp;}
}
  1. 快速排序

快速排序一种是本人自己写的,一种是算法书上的源码。

int partition(int data[], int low, int high) {int  pivot = data[low];while (low < high){while (low < high && data[high] >= pivot) // 从右向左找第一个小于x的数high--;if (low < high)data[low++] = data[high];while (low < high && data[low] < pivot) // 从左向右找第一个大于等于x的数low++;if (low < high)data[high--] = data[low];}data[low] = pivot;return low;
}void quickSort(int s[], int low, int high)
{if (low < high){int pivot = partition(s, low, high);quickSort(s, low, pivot - 1);quickSort(s, pivot + 1, high);}
}
int fastSort(int data[], int left, int right) {if (right - left <= 1){return 0;}int pos = left;int tmp = data[pos];int empty = pos;int low = left;int high = right;while (low < high){while (low < high){if (data[high] > tmp){high--;if (high <= low){break;}}else {data[empty] = data[high];empty = high;high--;break;}}while (low < high){if (low == pos){low++;if (high <= low){break;}}if (data[low] < tmp){low++;if (high <= low){break;}}else {data[empty] = data[low];empty = low;low++;break;}}}data[empty] = tmp;fastSort(data, left, low - 1);fastSort(data, low + 1, right);return 0;
}
  1. 堆排序
    堆排序是我最喜欢的一种排序。有3种实现方式(后面两种是我根据算法的思路自己写的)。
void swap(int* a, int* b) {int temp = *b;*b = *a;*a = temp;
}void max_heapify(int arr[], int start, int end) {// 建立父節點指標和子節點指標int dad = start;int son = dad * 2 + 1;while (son <= end) { // 若子節點指標在範圍內才做比較if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小,選擇最大的son++;if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢,直接跳出函數return;else { // 否則交換父子內容再繼續子節點和孫節點比較swap(&arr[dad], &arr[son]);dad = son;son = dad * 2 + 1;}}
}void heap_sort(int arr[], int len) {int i;// 初始化,i從最後一個父節點開始調整for (i = len / 2 - 1; i >= 0; i--)max_heapify(arr, i, len - 1);// 先將第一個元素和已排好元素前一位做交換,再重新調整,直到排序完畢for (i = len - 1; i > 0; i--) {swap(&arr[0], &arr[i]);max_heapify(arr, 0, i - 1);}
}
void swap(int& i, int& k) {int tmp = k;k = i;i = tmp;
}void heapAdjust(int arr[], int num, int arrsize) {int pos = num;for (int j = 2 * num + 1; j < arrsize; j = j * 2 + 1){if (j < arrsize - 1 && arr[j] < arr[j + 1]){j++;}if (arr[pos] < arr[j]){break;}else {arr[num] = arr[j];num = j;}}arr[num] = arr[pos];
}void heapSort2(int arr[], int arrsize) {for (int i = arrsize / 2 - 1; i >= 0; i--)		// n/2-1 is previous root dot{heapAdjust(arr, i, arrsize);}for (int i = arrsize - 1; i >= 0; i--){swap(arr[0], arr[i]);heapAdjust(arr, 0, i);}
}
void heapify(int arr[], int arrsize, int num) {int lowest = num;int lchild = 2 * num + 1;	//lchildint rchild = 2 * num + 2;	//rchildif (lchild < arrsize && arr[lchild] > arr[lowest]){lowest = lchild;}if (rchild < arrsize && arr[rchild]> arr[lowest]){lowest = rchild;}if (lowest != num){swap(arr[num], arr[lowest]);heapify(arr, arrsize, lowest);}
}
//				0
//		1				2
//	3		4		5		6
//7	 8    9  10   11 12   13 14void heapSort(int arr[], int arrsize) {for (int i = arrsize / 2 - 1; i >= 0; i--)		// n/2-1 is previous root dot{heapify(arr, arrsize, i);}for (int i = arrsize - 1; i >= 0; i--){swap(arr[0], arr[i]);heapify(arr, i, 0);}
}
  1. 归并排序
void Merge(int* data, int i, int m, int n) {int j = 0;int k = 0;for (int j = m + 1, k = i; i < m && j <= n; ++k){if (data[i] <= data[j]){data[k] = data[i++];}else {data[k] = data[j++];}}if (i <= m){int size = m - i;for (int c = size; c < size; c++){data[k++] = data[i++];}}if (j <= n){int size = n - j;for (int c = size; c < size; c++){data[k++] = data[j++];}}
}void MSort(int* data, int s, int t) {if (s == t){}
}

测试3轮65536个随机整数数据,上述8中排序算法的时间对比:

在这里插入图片描述

快速排序是冒泡排序的1000倍。

工程项目地址:https://github.com/satadriver/dataStruct

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

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

相关文章

shell脚本免交互

一.Here Document免交互 1.免交互概述 使用I/O重定向的方式将命令列表提供给交互式程序 是一种标准输入&#xff0c;只能接收正确的指令或命令 2.格式&#xff1a; 命令 <<标记 ....... 内容 #标记之间是传入内容 ....... 标记 注意事项 标记可以使用任意的合法…

2023年菏泽市中职学校技能大赛“网络安全”赛项规程

2023年菏泽市中职学校技能大赛 “网络安全”赛项规程 一、赛项名称 赛项名称&#xff1a;网络安全 赛项所属专业大类&#xff1a;信息技术类 二、竞赛目的 通过竞赛&#xff0c;检验参赛选手对网络、服务器系统等网络空间中各个信息系统的安全防护能力&#xff0c;以及分析…

系统架构:数据库

文章目录 数据库设计关系代数规范化理论求候选键特殊函数依赖Armstrong公理 数据库设计 步骤产出说明1.根据数据要求和处理要求进行需求分析数据流图、数据字典、需求说明书等分析数据流向、数据详细含义等&#xff0c;分析具体需求2.对现实世界进行抽象&#xff0c;进行概念结…

基于 Alpine 环境源码构建 alibaba-tengine(阿里巴巴)的 Docker 镜像

About Alpine&#xff08;简介&#xff09; Alpine Linux 是一款极其轻量级的 Linux 发行版&#xff0c;基于 busybox&#xff0c;多被当做 Docker 镜像的底包&#xff08;基础镜像&#xff09;&#xff0c;在使用容器时或多或少都会接触到此系统&#xff0c;本篇文章我们以该镜…

Jmeter生成可视化的HTML测试报告

Jmeter也是可以生成测试报告的。 性能测试工具Jmeter由于其体积小、使用方便、学习成本低等原因&#xff0c;在现在的性能测试过程中&#xff0c;使用率越来越高&#xff0c;但其本身也有一定的缺点&#xff0c;比如提供的测试结果可视化做的很一般。 不过从3.0版本开始&…

Mysql group by使用示例

文章目录 1. groupby时不能查询*2. 查询出的列必须在group by的条件列中3. group by多个字段&#xff0c;这些字段都有索引也会索引失效&#xff0c;只有group by单个字段索引才能起作用4. having条件必须跟group by相关联5. 用group by做去重6. 使用聚合函数做数量统计7. havi…

基于FPGA的FIR低通滤波器实现(附工程源码),matlab+vivado19.2+simulation

基于FPGA的FIR低通滤波器实现(附工程源码) 文章目录 基于FPGA的FIR低通滤波器实现(附工程源码)前言一、matlab设计FIR滤波器&#xff0c;生成正弦波1.设计FIR滤波器1.生成正弦波.coe 二、vivado1.fir滤波器IP核2.正弦波生成IP核3.时钟IP核设置4.顶层文件/测试文件代码 三.simul…

记忆正则表达式的基本元件

正则常见的三种功能&#xff0c;它们分别是&#xff1a;校验数据的有效性、查找符合要求的文本以及对文本进行切割和替换等操作。 正则表达式&#xff0c;简单地说就是描述字符串的规则。在正则中&#xff0c;普通字符表示的还是原来的意思&#xff0c;比如字符 a&#xff0c;…

小程序中的页面配置和网络数据请求

页面配置文件和常用的配置项 1.在msg.json中配置window中的颜色和背景色 "navigationBarBackgroundColor": "#efefef","navigationBarTextStyle": "black" 2.可以看到home中的没有发生变化但是msg的发生变化了&#xff0c;这个和前面的…

Mimikatz免杀实战:绕过360核晶和defender

文章目录 前言绕过360核晶实现思路完整代码运行测试 绕过WD实现思路MiniDumpWriteDump回调函数加密dump文件 完整代码运行测试 参考文章 前言 通常来说&#xff0c;即使我们成功实现了mimikatz的静态免杀&#xff0c;其抓取hash的行为仍可能会被防病毒软件检测到虽然你可以通过…

算法通关村第九关——透彻理解二分查找

1.前言 常见的查找算法有顺序查找、二分查找、插值查找、斐波那契查找、树表查找、分块查找、哈希查找等。如果进行归类&#xff0c;那么二分查找、插值查找&#xff08;一种查找算法&#xff09;以及斐波那契查找都可以归为插值查找&#xff08;大类&#xff09;。而插值查找…

ES搭建集群

一、创建 elasticsearch-cluster 文件夹 创建 elasticsearch-7.8.0-cluster 文件夹&#xff0c;在内部复制三个 elasticsearch 服务。 然后每个文件目录中每个节点的 config/elasticsearch.yml 配置文件 node-1001 节点 #节点 1 的配置信息&#xff1a; #集群名称&#xff0…

Android相机-架构

引言&#xff1a; 主要是针对CameraAPI v2 HAL3的架构对Android相机系统进行梳理。 相机架构 App和FrameWork packages/apps/Camer2 frameworks/ex/camera2 Camera API v2&#xff1b;Camera2 CameraDevice&#xff1a; CameraCaptureSession&#xff1a; CameraService AIDL…

设计模式(8)外观模式

一、 1、使用背景&#xff1a;降低访问复杂系统的内部子系统时的复杂度&#xff0c;简化客户端之间的接口。 2、定义&#xff1a; 为子系统中的一组接口定义一个一致的界面&#xff0c;此模式定义了一个高层接口&#xff0c;这个接口使得这一子系统更加容易使用。完美地体现…

什么是安全测试报告,怎么获得软件安全检测报告?

安全测试报告 软件安全测试报告&#xff1a;是指测试人员对软件产品的安全缺陷和非法入侵防范能力进行检查和验证的过程&#xff0c;并对软件安全质量进行整体评估&#xff0c;发现软件的缺陷与 bug&#xff0c;为开发人员修复漏洞、提高软件质量奠定坚实的基础。 怎么获得靠谱…

NLP预训练模型超大规模探索

总共从四方面来进行比较。 第一个方面&#xff0c;高层次方法&#xff08;自监督的预训练方法&#xff09;对比&#xff0c;总共三种方式。 语言模型式&#xff0c;就是 GPT-2 那种方式&#xff0c;从左到右预测&#xff1b;BERT-style 式&#xff0c;就是像 BERT 一样将一部…

多传感器分布式融合算法——加权最小二乘WLS融合/简单凸组合SCC融合

加权最小二乘WLS融合/简单凸组合SCC融合——多传感器分布式融合算法 原创不易&#xff0c;路过的各位大佬请点个赞 主要讲解算法&#xff1a; 加权最小二乘融合WLS 简单凸组合融合SCC 应用于: 多传感器网络协同目标跟踪/定位/导航 联系WX: ZB823618313 目…

框架分析(2)-React

框架分析&#xff08;2&#xff09;-React 专栏介绍React核心思想关键特性和功能组件化开发单向数据流JSX语法强大的生态系统 优缺点分析优点缺点 专栏介绍 link 主要对目前市面上常见的框架进行分析和总结&#xff0c;希望有兴趣的小伙伴们可以看一下&#xff0c;会持续更新的…

【数据结构入门指南】二叉树

【数据结构入门指南】二叉树 一、二叉树的概念二、现实中的二叉树三、特殊的二叉树四、二叉树的性质五、二叉树的存储结构5.1 顺序结构5.2 链式结构 一、二叉树的概念 二叉树是一棵特殊的树。一棵二叉树是结点的一个有限集合&#xff0c;该节点&#xff1a; ①&#xff1a;或者…

【Java转Go】快速上手学习笔记(四)之基础篇三

目录 泛型内置泛型的使用切片泛型和泛型函数map泛型泛型约束泛型完整代码 接口反射协程特点WaitGroupgoroutine的调度模型&#xff1a;MPG模型 channel介绍语法&#xff1a;举例&#xff1a;channel遍历基本使用和协程一起使用案例一案例二 select...casemain.go 完整代码 文件…