各种插入函数收集整理

各种插入函数收集整理

插入排序

void InsertSort(int arr[], int length)    //无哨兵的插入排序 
{
	for(int i=1; i<length; i++)
	{
		if(arr[i] < arr[i-1])
		{
			int temp = arr[i];
			for(int j=i-1; j>=0 && arr[j]>temp; j--)
			{
				arr[j+1] = arr[j];
			}
			arr[j+1] = temp;
		}
	}
}


void InsertSort(int arr[], int length)   //有哨兵的插入排序 
{
	for(int i=1; i<=length; i++)
	{
		if(arr[i] < arr[i-1])
		{
			arr[0] = arr[i];
			for(int j=i-1; arj[j]>arr[0]; j--)
			{
				arr[j+1] = arr[j];
			}
			arr[j+1] = arr[0];
		}
	}
}

希尔排序

void shell_sort(int arr[], int length)
{
	int d = length / 2;
	while(d > 0)
	{
		for(int i=d; i<length; i++)
		{
			int temp = arr[i];
			int j = i - d;
			while(j >=0 && arr[j] > temp)
			{
				arr[j+d] = arr[j];
				j -= d;
			}
			arr[j+d] = temp;
		}
		d /= 2;
	}
}

选择排序

void SelectSort(int arr[], int length)    //简单选择排序 
{
	for(int i=0; i<length-1; i++)
	{
		k = i;
		for(int j=i+1; j<length; j++)   //从后面选择一个最小的记录 
		{
			if(arr[j] < arr[k])
				k = j;
		}
		if(k != i)    //与第i个记录交换 
			swap(arr[i], arr[k]);
	}
}

冒泡排序

void Bubble_Sort1(int arr[], int length)     //将小元素冒泡到最前面,首先操作小元素
{
	for(int i=0; i<length-1; i++)
	{
		for(int j=i+1; j<length; j++)
		{
			if(arr[j] < arr[i])
				swap(arr[i], arr[j]);
		}
	}
} 

void Bubble_Sort2(int arr[], int length)
{
	for(int i=0; i<length; i++)
	{
		for(int j=0; j<legnth-1-i; j++)
		{
			if(arr[j] > arr[j+1])
				swap(arr[j], arr[j+1]);
		}
	}
}


void Bubble_Sort3(int arr[], int length)
{
	int left = 0;
	int right = length - 1;
	while(left < right)
	{
		for(int i=left; i<right; i++)
			if(arr[i] > arr[i+1])
				swap(arr[i], arr[i+1]);
		
		--right;
		for(int j=right; j>left; j--)
			if(arr[j] < arr[j-1])
				swap(arr[j], arr[j-1]);
		++left;
	}
}

快速排序

int partition(int* arr, int low, int high)
{
	int pivo = arr[low];
	while(low < high)
	{
		while(low < high && arr[high] >= pivo)
			high--;
		arr[low] = arr[high];
		while(low < high && arr[low] <= pivo)
			low++;
		arr[high] = arr[low];
	}
	arr[low] = pivo;
	return low;
}
 
void qsort(int* arr, int low, int high)    //快排(递归) 
{
	if(low < high)
	{
		int index = partition(arr, low, high);
		qsort(arr, low, index-1);
		qsort(arr, index+1, high);
	}
}

void qsort_no_recursive(int* arr, int low, int high)   //快排 (非递归) 
{
	int pivo = partition(arr, low, high);
	stack<int> s;
	if(pivo - 1 > low)
	{
		s.push(low);
		s.push(pivo-1);
	}
	if(pivo + 1 < high)
	{
		s.push(pivo+1);
		s.push(high);
	}
	while(!s.empty())
	{
		high = s.top();
		s.pop();
		low = s.top();
		s.pop();
		int index = partition(arr, low, high);
		if(index - 1 > low)
		{
			s.push(low);
			s.push(index - 1);
		}
		if(index + 1 < high)
		{
			s.push(index + 1);
			s.push(high);
		}
	}
}

归并排序

void Merge(int arr[], int low,int mid, int high)
{
	int i = low, j = mid+1; 
	int k = 0;
	int* temp = (int*)malloc((high - low + 1) * sizeof(int));
	while(i <= mid && j <= high)
	{
		if(arr[i] < arr[j])    //进行排序存入动态分配的数组中 
			temp[k++] = arr[i++];
		else
			temp[k++] = arr[j++];
	}
	while(i <= mid)      //如果前一半还有未处理完的数据,按顺序移入动态分配的数组中 
		temp[k++] = arr[i++];
	while(j <= high)     //如果后一半还有未处理完的数据,按顺序移入动态分配的数组中 
		temp[k++] = arr[j++];
	for(i=low, j=0; i<=high; i++)
		arr[i] = temp[j++];
	free(temp);
}
 
void Msort(int arr[], int low, int high)
{
	if(low < high)
	{
		int mid = (low + high) >> 1;
		Msort(arr, low, mid);
		Msort(arr, mid+1, high);
		Merge(arr, low, mid, high);
	}
}

堆排序

void HeapAdjust(int arr[], int s, int m)
{
	int temp = arr[s];
	for(int i=2*s; i<=m ; i*=2)
	{
		if(i < m && arr[i] < arr[i+1])
			i++;
		if(temp >= arr[i])
			break;
		arr[s] = arr[i];
		s = i;
	}
	arr[s] = temp;
} 
 
void HeapSort(int arr[], int length)
{
	for(int i=length/2; i>=0; i--)
		HeapAdjust(arr, i, length-1);
	for(int i=length-1; i>0; i--)
	{
		swap(arr[i], arr[0]);
		HeapAdjust(arr, 0, i-1);
	}
}

作者:鼠标CS
来源:CSDN
原文:https://blog.csdn.net/hubeidaxuesanqi3012/article/details/65934951
版权声明:本文为博主原创文章,转载请附上博文链接!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114903.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • php小皮怎么用_搭建php环境

    php小皮怎么用_搭建php环境本文主要和大家分享php环境搭建wampserver、Apache、Mysql和phpphp环境搭建csdnphp环境搭建详解,希望能帮助到大家。wampserver2.5-Apache-2.4.9-Mysql-5.6.17-php5.5.12-32b搭建php环境。在win下,下载wampserver2.5-Apache-2.4.9-Mysql-5.6.17-php5.5.12-32b.e…

  • SPSS聚类分析——一个案例演示聚类分析全过程

    SPSS聚类分析——一个案例演示聚类分析全过程SPSS聚类分析——一个案例演示聚类分析全过程摘要:案例数据源:有20种12盎司啤酒成分和价格的数据,变量包括啤酒名称、热量、钠含量、酒精含量、价格。数据来自《SPSSforWindows统计分析》案例数据源:有20种12盎司啤酒成分和价格的数据,变量包括啤酒名称、热量、钠含量、酒精含量、

    2022年10月18日
  • supervisor命令出现 unix:///tmp/supervisor.sock no such file[通俗易懂]

    supervisor命令出现 unix:///tmp/supervisor.sock no such file[通俗易懂]supervisor命令出现 unix:///tmp/supervisor.sock no such file

  • MD5加密算法「建议收藏」

    MD5加密算法「建议收藏」MD5的全称是Message-DigestAlgorithm5(信息-摘要算法),在90年代初由MITLaboratoryforComputerScience和RSADataSecurityInc的RonaldL.Rivest开发出来,经MD2、MD3和MD4发展而来。MD5加密算法:http://blog.csdn.net/huangxiaoguo1/artic

  • 最短路径算法——Dijkstra算法——python3实现

    最短路径算法——Dijkstra算法——python3实现本文参考来自数据结构与算法分析java语言描述。问题描述问题分析实现过程如何使用数据变化表问题描述现有一个有向赋权图。如下图所示:问题:根据每条边的权值,求出从起点s到其他每个顶点的最短路径和最短路径的长度。说明:不考虑权值为负的情况,否则会出现负值圈问题。s:起点v:算法当前分析处理的顶点w:与v邻接的顶点dvdvd_v:从s到v的距离…

  • UPX脱壳逐一跟踪分析

    UPX脱壳逐一跟踪分析UPX脱壳逐一跟踪分析写在前面OD跟踪命令先结合PE知识分析分析“新年快乐.exe”写在前面之前看到的UPX脱壳文章都只是教了方法,对UPX的原理少有提及。看了《逆核》的UPX脱壳一章后,俺尝试把UPX脱壳与PE文件结构的知识结合起来整理了一些(也可联系压缩器Paker的知识)。分析样本来自BUUCTF:Reverse题目“新年快乐”(本文将寻找样本的OEP)OD跟踪命令可能会用到的几个跟踪命令:命令快捷键作用AnimateIntoCtrl+F7反复执行StepIn

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号