排序算法（2）-- 快速排序，冒泡排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了排序算法（2）-- 快速排序，冒泡排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2642字，纯文字阅读大概需要4分钟。

内容图文

冒泡排序使我们开始最先接触到的一种排序算法，这里对其进行简单的说明以及现对于冒泡排序的一种改进算法快速排序，是在冒泡排序的基础上进行改进。

• 冒泡排序
• 快速排序

这里先对冒泡排序进行说明
1.冒泡排序：从待排组中第一个数字A[j]，其中j=0开始，依次与它后面A[j+1]的数字进行比较，如果小于第一个元素，则交换位置，将大的数字放在后面（石头向下沉），循环将第一个最大的数字放在数组最后面，比较趟数减一，即通过与后面元素的比较将最大的数字依次放在后面，最小的放在前面即可。
冒泡优化处理：当该待排序组原本就是有序时，不需要进行交换， 为了减少时间复杂度，可以设置一个标记flg，初始化为false，当前两个元素不相等时，将其置为true，每一趟排序完成后，判断 !flg 是否成立，成立则不返回 什么。

2.快速排序：快速排序是对冒泡排序的一种优化,初四是将第一个元素作为基准，一趟排序结果是将待排数组分为两个部分，处于基准左边的是小于它的数字，处于右边的是大于基准的数字。目标是将其移到坐标为K的位置。递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。

对于快排的基准的选择有不同的方法，时间复杂度，效率上有所不同，上述为基本的定位基准的方法，其他方法还需要进行理解。

//冒泡排序
#include<stdio.h>

void BubbleSort(int *arr,int len)//时间复杂度O(n^2)
{
	int tmp;
	int i;
	for(i=0;i<len-1;i++)//趟数
	{
		for(int j=0;j<len-1-i;j++)//-i!!!每沉入一个，比较的数字个数减一
		{
			if(arr[j]>arr[j+1])
			{
				tmp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=tmp;
			}
		}
	}
}


void BubbleSort1(int *arr,int len)//冒泡优化//有序 1 2 3 4 5 6 时间复杂度O(n)
{
	int tmp;
	bool flg=false;
	int i;
	for(i=0;i<len-1;i++)//有序 1 2 3 4 5 6 避免交换
	{
		bool flg=false;
		for(int j=0;j<len-1-i;j++)
		{
			if(arr[j]>arr[j+1])
			{
				tmp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=tmp;
				flg=true;
			}
		}
		if(!flg)
		{
			return;
		}
	}
}

void Show(int *arr,int len)
{
	for(int i=0;i<len;i++)
	{
		printf("%3d",arr[i]);
	}
	printf("\n");
}

int main()
{
	int arr[]={20,33,21,54,17,16,30,18,19,22,7,10,46,12,15};
	
	BubbleSort(arr,sizeof(arr)/sizeof(arr[0]));
	
	Show(arr,sizeof(arr)/sizeof(arr[0]));

	return 0;
}

//快速排序
#include<stdio.h>
//快排一次划分
int Partition(int *arr,int low,int high)//O(n),O(1) 
{
	int tmp = arr[low];//基准
	while(low < high)
	{
		while(low<high && arr[high]>tmp)
		{
			high--; 
		}
		arr[low] = arr[high];
		while(low<high && arr[low]<tmp)
		{
			low++;
		}
		arr[high] = arr[low];
	}

	arr[low] = tmp;//low==high
	return low;
}

static void Quick(int*arr,int low,int high)
{
	int par = Partition(arr,low,high);
	if(low+1 < par)//左边至少两个数据
	{
		Quick(arr,low,par-1);
	}
	if(par+1 < high)//右边至少两个数据
	{
		Quick(arr,par+1,high);
	}
}

void QuickSort(int *arr,int len)//O(nlogn),O(logn)***,不稳定
{
	Quick(arr,0,len-1);
}

void Show(int *arr,int len)
{
	for(int i=0;i<len;i++)
	{
		printf("%d ",arr[i]);
	}
	printf("\n");
}


int main()
{
	int arr[] = {4,9,0,12,34,67,8,91,32,54,66,88,2};
	QuickSort(arr,sizeof(arr)/sizeof(arr[0]));
	Show(arr,sizeof(arr)/sizeof(arr[0]));

	return 0;
}

内容总结

以上是互联网集市为您收集整理的排序算法（2）-- 快速排序，冒泡排序全部内容，希望文章能够帮你解决排序算法（2）-- 快速排序，冒泡排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

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

内容手机端

---