一起学习交流~

排序-07-非比较排序:计数排序&桶排序&基数排序

算法 laomuji 12个月前 (10-10) 584次浏览 已收录 0个评论

一、三种排序简介

计数排序 桶排序 基数排序 属于非比较排序,是内部排序中最快的排序

理论下限速度非常快 可以突破nlogn,也就是说比快排,归并等排序都要快

但是适用场合有限,不适用于所有场景.

排序算法 时间复杂度 空间复杂度 是否为稳定排序
计数排序O(N + K) O(N + K)
桶排序 O(N + K) O(N + K)
基数排序 O(N + K) O(N + K)
//先贴两个简单获取数组中最大最小值,下面代码会用到
int getMax(int nums[], int length)
{
	int max = nums[0];
	for (int i = 1; i < length; i++)
		if (nums[i] > max)max = nums[i];
	return max;
}
int getMin(int nums[], int length)
{
	int min = nums[0];
	for (int i = 1; i < length; i++)
		if (nums[i] < min)min = nums[i];
	return min;
}

二、计数排序

计数排序
假设数字最小值为0
假设有数组{4,3,6,3,3,2,3,7,5,4}
最大数字和前面的每个数字建立一个桶
每个桶存放这个数字出现的次数
0,1,2,3,4,5,6,7 桶
0,0,1,4,2,1,1,1 出现次数
把这个数字出现的次数放入原始数组里
0次0 0次1 1次2 4次3 2次4 1次5 1次6 1次7
2,3,3,3,3,4,4,5,6,7
就实现了计数排序

void countSort(int source[],int length)
{
	int* sort = new int[length];
	//首先找出最大的数字
	int max = getMax(source, length) + 1;//比如最大数字是3,就应该是0,1,2,3四个桶,所以要+1
	//建立桶
	int* tong = new int[max];
	memset(tong, 0, sizeof(int) * max);//初始化为0
	//记录桶中数字个数
	for (int i = 0; i < length; i++)
	{
		//记录当前数字
		int val = source[i];
		//将当前数字所在的桶的个数+1
		tong[val]++;
	}
	//记录排序后的数组的下标
	int pos = 0;
	//将桶中的数据加入到排序后的数组
	//i是每个数字
	for (int i = 0; i < max; i++)
	{
		//j是数字出现的次数,依次把该数字放入进去
		for (int j = 0; j < tong[i]; j++) 
		{
			sort[pos++] = i;
		}
	}

	for (int i = 0; i < length; i++)
	{
		source[i] = sort[i];
	}

	delete[] tong;
	delete[] sort;
}

三、桶排序

桶排序 个人感觉是优化的计数排序

每个桶存储某个范围的数
比如是这些数字
17,13,4321,25,100,72,15,2234
max=4321 min=13
8个数字,假设建立3个桶
数字范围:4321 – 13 = 4308
桶的间隔:4308 / 3 = 1436
桶1<1436
1436<=桶2<2872
2872<=桶3<4308

//循环+递归的方法
void quickSort(int nums[], int low, int high)
{
	//low 和 high 用户限定数组的开始和结束部分,nums[low]-nums[high]为一个整体
	if (low >= high)return;
	int left = low;//左边下标
	int right = high;//右边下标
	int key = nums[low];//基准值,假设为最左边的
	//在left和right的范围内进行寻找
	//先从左边或右边开始找
	while (left <= right)
	{
		while (left <high && nums[left] < key)left++;
	
		while (right > low && nums[right] > key)right--;
		if (left > right) break;

		swap(nums[left++], nums[right--]);
	}

	quickSort(nums, low, left - 1);//左边部分再次排序
	quickSort(nums, left, high);//右边部分再次排序
}
//给桶排序内部排序进行使用
void quickSort(std::vector<int> nums, int low, int high)
{
	//low 和 high 用户限定数组的开始和结束部分,nums[low]-nums[high]为一个整体
	if (low >= high)return;
	int left = low;//左边下标
	int right = high;//右边下标
	int key = nums[left];//基准值,假设为最左边的
	int temp;
	//在left和right的范围内进行寻找
	//先从左边或右边开始找 取决于基准值的为止,若基准值是左边,则必须先从右边开始找
	while (left < right)
	{
		//若当前值大于等于基准值,则往前,当找到第一个小于基准值的数字后,终止循环
		//因为右边必须全部大于基准值,若不大于基准值,则把他放到左边
		while (left < right && nums[right] > key) { right--; }

		//若当前值小于等于基准值,则往后,当找到第一个大于基准值的数字后,终止循环
		//因为左边必须全部小于基准值,若不小于基准值,则把他放到右边
		while (left < right && nums[left] < key) { left++; }

		//判断这两个值的位置是否正确
		if (left >= right)break;
		//将两个需要交换的值进行交换
		std::swap(nums[left++], nums[right--]);
	}

	quickSort(nums, low, left - 1);//左边部分再次排序
	quickSort(nums, left + 1, high);//右边部分再次排序
}


//桶排序
void bucketSort(int nums[],int length)
{
	//获得最大数和最小数
	int max = getMax(nums, length);
	int min = getMin(nums, length);
	//设定桶的个数,根据自己的需求设定
	//这里我根据个数还有最大值和最小值来设定桶的个数,基本上可以保证每个桶里的个数差距不大
	int bucketCount = length / (max - min) + 1;//+1避免结果为0 出现溢出
	//获得每个桶的间隔
	int gap = (max - min) / bucketCount;
	if (gap == 0)return;
	//生成对应的桶,使用方式为buckets[bucketCountId][index]
	//int** buckets = (int**)(new int[bucketCount * length]);
	//这种方法比较浪费内存,最好使用列表
	std::vector<std::vector<int>>buckets;//相当于二维数组
	for (int i = 0; i < bucketCount; i++)
		buckets.push_back(std::vector<int>());//创建对应的桶

	//将数字放入到桶中
	for (int i = 0; i < length; i++)
		buckets[(nums[i] - (min + 1)) / gap].push_back(nums[i]);
	

	//对桶中的数字进行排序,可以使用快排,归并之类的比较快速的排序
	int pos = 0;//用于放入原始数组
	for (int i = 0; i < bucketCount; i++)
	{
		quickSort(buckets[i], 0, buckets[i].size() - 1);//排序桶里的数据
		for (int j = 0; j < buckets[i].size(); j++)
			nums[pos++] = buckets[i][j];//出桶
	} 
}

四、基数排序

基数排序
从最低位开始,往最高位,每次进行计数排序的变体(比较某一位而不是确切的数字)
比如有以下数字17,13,4321,25,100,72,15,2234
建立0-9的桶,因为每一位上的数字都在0-9的范围
0 1 2 3 4 5 6 7 8 9
对数字的个位进行计数
0:100
1:4321
2:72
3:13
4:2234
5:25,15
6:
7:17
8:
9:
合并
100,4321,72,13,2234,25,15,17
对数字的十位进行计数
0:100
1:13,15,17
2:4321,25
3:2234

7:72

合并
100,13,15,17,4321,25,2234,72
对数字的百位进行计数
0:13,15,17,25,72
1:100
2:2234
3:4321
4:

合并
13,15,17,25,72,100,2234,4321
对数字的千位进行计数
0:13,15,17,25,72,100
1:
2:2234
3:
4:4321
5:

合并
13,15,17,25,72,100,4321

//获取数字的某一位的数字,1就是个位,10是十位
int getDigtiNum(int num,int digit)
{
	return (num / digit) % 10;
}

//计数排序的变种,对某个位进行排序
void radixSortCount(int nums[], int length, int digit, int temp[])
{
	memset(temp, 0, sizeof(int) * length);
	//建立桶,每位上的数字比较特殊,只能是0-9
	int tong[10] = { 0 };
	//对每个数字的某位出现次数进行记录
	for (int i = 0; i < length; i++)
	{
		int digtiNum = getDigtiNum(nums[i], digit);//某位的数字
		tong[digtiNum]++;
	}
	//把等于某位出现的次数变为小于等于某位的出现的次数
	for (int i = 1; i < 10; i++)
	{
		tong[i] += tong[i - 1];
	}
	//从右往左,根据某位上的数字放入对应的临时数组
	for (int i = length - 1; i >= 0; i--)
	{
		//digtiNum就是某位的数字
		int digtiNum = getDigtiNum(nums[i], digit);
		//桶记录的是小于等于该数字的个数
		//个数-1 就是该数字的下标
		int pos = tong[digtiNum] - 1;
		temp[pos] = nums[i];
		//因为相同的数字可以出现多次,所以该位置的下标应该往前移动一个
		tong[digtiNum]--;
	}
	//将临时数组拷贝到原始数组
	for (int i = 0; i < length; i++)
	{
		nums[i] = temp[i];
	}

}

//基数排序
void radixSort(int nums[],int length)
{
	//创建一个临时数组,用于存放排序后的数据
	int* temp = new int[length];
	//首先获取最大的数字,然后循环该长度的次数,每次/10,就是最大位数
	int max = getMax(nums, length);
	//digit为比较的位数,1是个位,10是十位,100是百位
	for (int digit = 1; digit <= max; digit *= 10)
	{
		radixSortCount(nums, length, digit,temp);
	}
	delete[] temp;
}

大概是这样

喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论