桶排序（简化版）与冒泡排序

code-child

发布于 2023-05-30 14:14:38

1460

发布于 2023-05-30 14:14:38

文章被收录于专栏：codechild

1.桶排序（简化版）

所谓桶排序就是桶的序列是排好的，只需要把数字放在对应桶的序列就可以，记下这个桶里面数字出现过几次就可以。我们来排个数吧！3 4 6 8 5 2 9 7 1 我们需要的桶数由最大数+1构成，所以占内存比较大，但时间复杂度小。用数组来储存，arr[10],数组的下标是从0开始的。先把桶都先初始化为0，表示没有一个数出现过. 先讲一下一维数组的初始化 这是一种初始化

cppint arr[10] = { 0 };

这样虽然初始化第一个元素，都是下面的各个元素都被默认为0 还可以这样初始化，下面的这种开始声明的并没有初始化，后续是进行的赋值

cppint arr[10];
	int n = 0;
	for (n = 0; n < 10; n++)
	{
		arr[n] = 0;
	}

在平时的初始化中我喜欢第一种。下面我们循环输入刚才的数 3 4 6 8 5 2 9 7 1 并且把数存到相应的桶中，并记录出现几次

cppfor (n = 0; n < 9; n++)
	{
		scanf("%d", &s);
		arr[s]++;
	}

接着我们把它输出就可以了（从小到大）

cppfor (n = 0; n < 10; n++)
	{
		if (arr[n] != 0)
			printf("%d ", n);
	}

完整代码

cpp#include <stdio.h>
#define MAX 10
int main()
{
	int arr[MAX]={0};
	int n = 0,s=0;
	for (n = 0; n < MAX-1; n++)
	{
		scanf("%d", &s);
		arr[s]++;
	}
	for (n = 0; n < MAX; n++)
	{
		if (arr[n] != 0)
			printf("%d ", n);
	}
	return 0;
}

2.冒泡排序

基本思路前一个数与第二个数进行比较

“冒泡”就像上面的图片一样，从下面到上面，我们这里讲的_冒泡排序 _就和这个类似还是这样一个无序的数列** 3 4 6 8 5 2 9 7 1，我们想让它变成 1 2 3 4 5 6 7 8 9 假设有一个箭头J指向一个数 1）首先是J指向最下面的3，它与J+1指向的数（也就是下一个数）进行比较，如果比它大，他俩就进行交换，否则不交换。然后J **往后走一步（j++)，依此循环该步骤。直至到最后一个数的比较。这次找到的是最大的数。

cppfor (j = 0; j < 9 - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}

2）3 4 6 5 2 8 7 1 9 ，这是上一步排成的，可以观察到最后一个数已经排好了（可以理解为最大的气泡已经出水面了），下面的排序就是把已经排好的数字（每次排好的最后一个数）去掉，按照（1）进行排下列的数字.直至完成排序。注意： 1.总排序此时为排序数字个数减1 2.每一次排序都减1 完整代码

cppint main()
{
	int arr[9] = { 3 ,4, 6, 8, 5, 2, 9 ,7, 1 };
	int i, j;
	for (i = 0; i < 9 - 1; i++)
	{
		for (j = 0; j < 9 - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-05-26，如有侵权请联系 cloudcommunity@tencent.com 删除

int