数据结构与算法系列文章:数据结构与算法目录
桶排序是计数排序的升级版,它将要排的数据分到多个有序的桶里,每个桶里的数据再单独排序,再把每个桶的数据依次取出,即可完成排序。
图解桶排序:
拿一组计数排序啃不掉的数据 [ 500,6123,1700,10,9999 ] 来举例。
第一步,我们创建 10 个桶,分别来装 0-1000 、1000-2000 、 2000-3000 、 3000-4000 、 4000-5000 、5000-6000、 6000-7000 、7000-8000 、8000-9000 区间的数据。
桶排序1.png
第二步,遍历原数组,对号入桶。
桶排序2.png
第三步,对桶中的数据进行单独排序,只有第一个桶中的数量大于 1 ,显然只需要排第一个桶。
桶排序3.png
最后,依次将桶中的数据取出,排序完成。
桶排序4.png
桶排序需要考虑2个问题:
1、怎么确定桶的数量?
2、桶内排序用什么方法排?
实现:
/// <summary>
/// 桶排序
/// </summary>
/// <param name="arr"></param>
public void BucketSort(int[] arr)
{
if (arr == null || arr.Length <= 0)
{
return;
}
// 找到数组内的最大值和最小值
int minValue = arr[0];
int maxValue = arr[0];
int arrLength = arr.Length;
int arrValue;
for (int i = 0; i < arrLength; i++)
{
arrValue = arr[i];
if (arrValue < minValue)
{
minValue = arrValue;
}
else if (arrValue > maxValue)
{
maxValue = arrValue;
}
}
// 最大和最小间差值
int offsetValue = maxValue - minValue;
// 初始化桶列表,桶的数量设置为原数组的长度
List<List<int>> buckets = new List<List<int>>();
for (int i = 0; i < arrLength; i++)
{
buckets.Add(new List<int>());
}
// 每个桶的存数区间
float section = (float)offsetValue / (arrLength - 1);
// 数据入桶
for (int i = 0; i < arrLength; i++)
{
arrValue = arr[i];
// 当前数除以区间得出桶的位置,减一后得出桶的下标
int bucketIndex = Mathf.FloorToInt(arrValue / section) - 1;
if (bucketIndex < 0)
{
bucketIndex = 0;
}
buckets[bucketIndex].Add(arrValue);
}
List<int> newList = new List<int>();
// 对每个桶进行排序,这里使用插入排序
for (int i = 0; i < buckets.Count; i++)
{
InsertSort(buckets[i]);
}
// 写入原数组
int index = 0;
for (int i = 0; i < buckets.Count; i++)
{
for (int j = 0; j < buckets[i].Count; j++)
{
arr[index] = buckets[i][j];
index++;
}
}
}
/// <summary>
/// 插入排序
/// </summary>
/// <param name="list"></param>
public void InsertSort(List<int> list)
{
if (list == null || list.Count <= 0)
{
return;
}
int len = list.Count;
for (int i = 1; i < len; i++)
{
int temp = list[i];
// 在已经排序好的元素中,从后往前比较
for (int j = i - 1; j >= 0; j--)
{
if (list[j] > temp)
{
// 交换元素
list[j + 1] = list[j];
list[j] = temp;
}
else
{
// 有序元素未比较的元素中,没有比此元素大的了
break;
}
}
}
}
网友评论