c语言5个常用的排序算法实例代码

2023-09-16 21:50:06 69
1.插入排序

基本思想：插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。
voidinsertSort(vector&nums)
{
intk=0;
for(inti=0;i0&&temp
2.希尔排序
基本思想：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
voidshellSort(vector&nums)
{
for(intgap=nums.size()/2;gap>0;gap/=2)
{
for(inti=gap;i=gap&&temp
3.堆排序
用一句概括，堆排序就是一种改进的选择排序，改进的地方在于，每次做选择的时候，不单单把最大的数字选择出来，而且把排序过程中的一些操作进行了记录，这样在后续排序中可以利用，并且有分组的思想在里面，从而提高了排序效率，其效率为O(n*logn).
#include
intc=0;
/*heapadjust()函数的功能是实现从a[m]到a[n]的数据进行调整，使其满足大顶堆的特性*/
/*a[]是待处理的数组，m是起始坐标，n是终止坐标*/
voidheapadjust(inta[],intm,intn)
{
	inti,temp;
	temp=a[m];
	for(i=2*m;i<=n;i*=2)//从m的左孩子开始
	{
		if(i+1<=n&&a[i]0;i--)//n/2为最后一个双亲节点，依次向前建立大顶堆
	{
		heapadjust(a,i,n);
	}
}
/*swap()函数的作用是将a[i]和a[j]互换*/
voidswap(inta[],inti,intj)
{
	inttemp;
	temp=a[i];
	a[i]=a[j];
	a[j]=temp;
	c++;
}
voidheapsort(inta[],intn)
{
	inti;
	crtheap(a,n);
	for(i=n;i>1;i--)
	{
		swap(a,1,i);
		//将第一个数，也就是从a[1]到a[i]中的最大的数，放到a[i]的位置
		heapadjust(a,1,i-1);
		//对剩下的a[1]到a[i]，再次进行堆排序，选出最大的值，放到a[1]的位置
	}
}
intmain(void)
{
	inti;
	inta[10]={-1,5,2,6,0,3,9,1,7,4};
	printf("排序前：");
	for(i=1;i<10;i++)
	{
		printf("%d",a[i]);
	}
	heapsort(a,9);
	printf("\n\n共交换数据%d次\n\n",c);
	printf("排序后：");
	for(i=1;i<10;i++)
	{
		printf("%d",a[i]);
	}
	printf("\n\n\n");
	return0;
}
4.归并排序
基本思想：归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤，分别为：


1）划分子表

2）合并半子表


刚好最近刷leetcode有道题用的归并排序：sortlist
classSolution{
public:
//归并排序
ListNode*getMiddleOfList(ListNode*head)
{
ListNode*mid=head;
ListNode*last=head;
while(last->next!=NULL&&last->next->next!=NULL)
{
mid=mid->next;
last=last->next->next;
}
returnmid;
}
ListNode*sortList(ListNode*head){
if(head==NULL||head->next==NULL)returnhead;
ListNode*mid=getMiddleOfList(head);
ListNode*midnext=mid->next;
mid->next=NULL;
returnmergeList(sortList(head),sortList(midnext));
}
ListNode*mergeList(ListNode*a,ListNode*b)
{
ListNode*res=newListNode(-1);
ListNode*cur=res;
while(a!=NULL&&b!=NULL)
{
if(a->valval)
{
cur->next=a;
a=a->next;
}
else
{
cur->next=b;
b=b->next;
}
cur=cur->next;
}
cur->next=a!=NULL?a:b;
returnres->next;
}
};
5.快速排序
基本思想：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
classsort{
public:
intmedian3(vector&nums,intleft,intright)
{
intmid=(left+right)/2;
if(nums[left]>nums[mid])swap(nums[left],nums[mid]);
if(nums[mid]>nums[right])swap(nums[mid],nums[right]);
if(nums[left]>nums[mid])swap(nums[left],nums[mid]);

swap(nums[mid],nums[left]);
returnnums[left];
}
voidquickSort(vector&nums,inti,intj)
{
if(i>j)return;
intpartition=median3(nums,i,j);
intlow=i+1,high=j;
while(lowpartition)high--;
if(low&nums)
{
quickSort(nums,0,nums.size()-1);
}
};
总结
以上就是本文关于c语言5个常用的排序算法实例代码的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
c语言5个常用的排序算法实例代码

1.插入排序

2.希尔排序

3.堆排序

4.归并排序

5.快速排序

总结

热门推荐

随机推荐
