排序算法合集

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;	//lchild
	int rchild = 2 * num + 2;	//rchild
	if (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 14

void 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

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

node使用高版本的oracledb导致连接oracle的Error: NJS-138异常

node使用高版本的oracledb导致连接oracle的Error: NJS-138异常

异常信息如下 Error: NJS-138: connections to this database server version are not supported by node-oracledb in Thin mode 我的oracle版本是11g&#xff0c;之前的使用正常&#xff0c;今天却报错了&#xff0c;显示不支持thin模式&#xff0c;后面回退版本就可以了。
阅读更多...
AWS复制EC2文件到S3，g4dn.2xlarge没有NVIDIA GPU 驱动问题

AWS复制EC2文件到S3，g4dn.2xlarge没有NVIDIA GPU 驱动问题

1、给instances权限 action > Security > modify IAM role 把提前创建好的role给这个instance即可 2、复制到bucket aws s3 cp gogo.tar.gz s3://ee547finalbucket不需要手动安装GPU驱动 如果要自己安装&#xff0c;参考https://docs.aws.amazon.com/AWSEC2/latest/U…
阅读更多...
6-模板初步使用

6-模板初步使用

官网: 中文版: 介绍-Jinja2中文文档 英文版: Template Designer Documentation — Jinja Documentation (2.11.x) 模板语法 1. 模板渲染 (1) app.py 准备数据 import jsonfrom flask import Flask,render_templateimport settingsapp Flask(__name__) app.config.from_obj…
阅读更多...
C#详解-Contains、StartsWith、EndsWith、Indexof、lastdexof

C#详解-Contains、StartsWith、EndsWith、Indexof、lastdexof

目录 简介: 过程: 举例1.1 举例1.2 ​ 总结: 简介: 在C#中Contains、StarsWith和EndWith、IndexOf都是字符串函数。 1.Contains函数用于判断一个字符串是否包含指定的子字符串&#xff0c;返回一个布尔值&#xff08;True或False&#xff09;。 2.StartsWith函数用于判断一…
阅读更多...
wifi高通驱动之WCNSS_qcom_cfg.ini以及MCS、空间流数的学习和记录

wifi高通驱动之WCNSS_qcom_cfg.ini以及MCS、空间流数的学习和记录

一、WCNSS_qcom_cfg.ini 这个文件说是可以调优wifi的带宽&#xff0c;还有MIMO技术 Android Wi-Fi MIMO/SISO设置方法&#xff08;基于高通平台&#xff09;_广凯的博客-CSDN博客 不是太了解&#xff0c;先记录一下&#xff0c;个人感觉MCS和MIMO技术最全的应该是下面的网址…
阅读更多...
DataLoader PyTorch 主要参数的含义

DataLoader PyTorch 主要参数的含义

定义&#xff1a; DataLoader类是一个用于从数据集&#xff08;dataset&#xff09;中加载数据&#xff0c;并以迭代器&#xff08;iterator&#xff09;的形式返回数据样本&#xff08;data samples&#xff09;的工具。您给出的两个字典&#xff08;dictionary&#xff09;分…
阅读更多...
%f占位符

%f占位符

介绍&#xff1a; %f &#xff0c;用来输出实数&#xff08;包括单双精度&#xff09;&#xff0c;以小数形式输出。 通常情况下&#xff0c;当输入的数值或者打印的数值是float类型数据时&#xff0c;使用%f &#xff0c;当然在精度更高的double数据类型下&#xff0c;也可以…
阅读更多...
记忆正则表达式的基本元件

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

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

Linux下的Shell编程——正则表达式入门（四）

前言&#xff1a; 正则表达式使用单个字符串来描述、匹配一系列符合某个语法规则的字符串。在很多文本编辑器里&#xff0c;正则表达式通常被用来检索、替换那些符合某个模式的文本。 在Linux 中&#xff0c;grep&#xff0c;sed&#xff0c;awk 等文本处理工具都支持…
阅读更多...
Spring Clould 服务间通信 - Feign

Spring Clould 服务间通信 - Feign

视频地址&#xff1a;微服务&#xff08;SpringCloudRabbitMQDockerRedis搜索分布式&#xff09; Feign-基于Feign远程调用&#xff08;P30&#xff09; 先来看我们以前利用RestTemplate发起远程调用的代码&#xff1a; 存在下面的问题&#xff1a; 代码可读性差&#xff0c…
阅读更多...
在外SSH远程连接macOS服务器

在外SSH远程连接macOS服务器

文章目录 前言1. macOS打开远程登录2. 局域网内测试ssh远程3. 公网ssh远程连接macOS3.1 macOS安装配置cpolar3.2 获取ssh隧道公网地址3.3 测试公网ssh远程连接macOS 4. 配置公网固定TCP地址4.1 保留一个固定TCP端口地址4.2 配置固定TCP端口地址 5. 使用固定TCP端口地址ssh远程 …
阅读更多...
PSP - 基于开源框架 OpenFold Multimer 蛋白质复合物的结构预测与BugFix

PSP - 基于开源框架 OpenFold Multimer 蛋白质复合物的结构预测与BugFix

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/132410296 AlphaFold2-Multimer 是一个基于 AlphaFold2 的神经网络模型&#xff0c;可以预测多链蛋白复合物的结构。该模型在训练和推理时都可以处…
阅读更多...
Java将PDF文件转为Word文档

Java将PDF文件转为Word文档

Java将PDF文件转为Word文档 一、创建Springboot Maven项目 二、导入依赖信息 <repositories><repository><id>com.e-iceblue</id><url>https://repo.e-iceblue.cn/repository/maven-public/</url></repository></repositories&g…
阅读更多...
POSTGRESQL 如何用系统函数来诊断权限问题

POSTGRESQL 如何用系统函数来诊断权限问题

开头还是介绍一下群&#xff0c;如果感兴趣polardb ,mongodb ,mysql ,postgresql ,redis 等有问题&#xff0c;有需求都可以加群群内有各大数据库行业大咖&#xff0c;CTO&#xff0c;可以解决你的问题。加群请联系 liuaustin3 &#xff0c;在新加的朋友会分到2群&#xff08;共…
阅读更多...
更改计算机睡眠时间

更改计算机睡眠时间

控制面板–>系统和安全–>电源选项下的更改计算机睡眠时间 如果关闭显示器时间小于使计算机进入睡眠状态时间&#xff0c;时间先到达关闭显示器时间&#xff0c;显示器关闭&#xff0c;这时电脑还在正常工作状态。如果此时敲击键盘显示器出现画面&#xff0c;无需输入密…
阅读更多...
opencv 进阶15-检测DoG特征并提取SIFT描述符cv2.SIFT_create()

opencv 进阶15-检测DoG特征并提取SIFT描述符cv2.SIFT_create()

前面我们已经了解了Harris函数来进行角点检测&#xff0c;因为角点的特性&#xff0c;这些角点在图像旋转的时候也可以被检测到。但是&#xff0c;如果我们放大或缩小图像时&#xff0c;就可能会丢失图像的某些部分&#xff0c;甚至有可能增加角点的质量。这种损失的现象需要一…
阅读更多...
存储系统性能优化中IOMMU的作用是什么？

存储系统性能优化中IOMMU的作用是什么？

一、IOMMU原理 IOMMU（Input/Output Memory Management Unit）是一种用于管理计算机内存的技术，它允许将物理内存映射到虚拟地址空间。IOMMU通过使用专用的硬件来管理和优化内存访问，从而提高系统性能和稳定性。本文将详细介绍IOMMU的原理，并介绍一些应用案例和典型的问题解…
阅读更多...
Spring6.0官方文档示例：（28）多种方式添加BeanPostProcessor

Spring6.0官方文档示例：（28）多种方式添加BeanPostProcessor

一、定义三个BeanPostProcessor package cn.edu.pku;import org.springframework.beans.BeansException; import org.springframework.beans.factory.config.BeanPostProcessor; import org.springframework.stereotype.Component;Component public class MyScannedBeanPostPr…
阅读更多...
【HarmonyOS北向开发】-05 ArkTS开发语言-ArkTS开发实践

【HarmonyOS北向开发】-05 ArkTS开发语言-ArkTS开发实践

阅读更多...
微信小程序列表加载更多

微信小程序列表加载更多

概述 基于小程序开发的列表加载更多例子。 详细 一、前言 基于小程序开发的列表加载更多例子。 二、运行效果 运行效果&#xff08;演示的小视频&#xff0c;点击播放即可&#xff09; 三、实现过程 总体思路如何&#xff1a; 1、通过scroll-view组件提供的bindscroll方法…
阅读更多...
最新文章

Copyright @ 2022~2023