快捷導(dǎo)航

Java排序算法之桶排序算法解析

更新時(shí)間：2023年10月30日 09:43:44 作者：大彤小憶

這篇文章主要介紹了Java排序算法之桶排序算法解析,桶排序 (Bucket sort)或所謂的箱排序,是一個(gè)排序算法,工作原理是將數(shù)組分到有限數(shù)量的桶子里,每個(gè)桶子再個(gè)別排序,有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序,需要的朋友可以參考下

Java桶排序算法

桶排序 (Bucket sort)或所謂的箱排序，是一個(gè)排序算法。

工作原理是將數(shù)組分到有限數(shù)量的桶子里，每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時(shí)候，桶排序使用線性時(shí)間 O ( n ) O(n) O(n)。

桶排序是計(jì)數(shù)排序的升級(jí)版。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。為了使桶排序更加高效，我們需要做到以下兩點(diǎn)：

1. 在額外空間充足的情況下，盡量增大桶的數(shù)量；

2. 使用的映射函數(shù)能夠?qū)⑤斎氲?N 個(gè)數(shù)據(jù)均勻的分配到 K 個(gè)桶中。同時(shí)，對(duì)于桶中元素的排序，選擇何種比較排序算法對(duì)于性能的影響至關(guān)重要。

什么時(shí)候最快：當(dāng)輸入的數(shù)據(jù)可以均勻的分配到每一個(gè)桶中。

什么時(shí)候最慢：當(dāng)輸入的數(shù)據(jù)被分配到了同一個(gè)桶中。

桶排序的基本思想：假設(shè)數(shù)據(jù)在[min,max]之間均勻分布，其中min、max分別指數(shù)據(jù)中的最小值和最大值。那么將區(qū)間[min,max]等分成n份，這n個(gè)區(qū)間便稱為n個(gè)桶。將數(shù)據(jù)加入對(duì)應(yīng)的桶中，然后每個(gè)桶內(nèi)單獨(dú)排序。由于桶之間有大小關(guān)系，因此可以從大到小(或從小到大)將桶中元素放入到數(shù)組中。

例如：使用桶排序算法將數(shù)組{ 21,3,30,44,15,36,6,10,9,19,25,48,5,23,47 }進(jìn)行升序排序。

在這里插入圖片描述

實(shí)現(xiàn)代碼如下所示。

#include<iostream>
using namespace std;
#include<algorithm>

void BubbleSort(int arr[], int len)
{
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = 0; j < len - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				std::swap(arr[j], arr[j + 1]);
			}
		}
	}
}

void BucketSort(int* arr, int len) 
{

	int bucket[5][5];  //分配5個(gè)桶
	int bucketsize[5];  //每個(gè)桶中元素個(gè)數(shù)的計(jì)數(shù)器

	//初始化桶和桶計(jì)數(shù)器
	memset(bucket, 0, sizeof(bucket));
	memset(bucketsize, 0, sizeof(bucketsize));

	for (int i = 0; i < len; i++)  //把數(shù)組中的數(shù)據(jù)放入桶中
	{
		bucket[arr[i] / 10][bucketsize[arr[i] / 10]++] = arr[i];
	}

	for (int i = 0; i < len; i++)  //對(duì)每個(gè)桶中的數(shù)據(jù)進(jìn)行排序
		BubbleSort(bucket[i],bucketsize[i]);

	int k = 0;
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < bucketsize[i]; j++)
		{
			arr[k++] = bucket[i][j];  //將每個(gè)桶中的元素填充到數(shù)組中去
		}
	}
}

int main() 
{
	int a[] = { 21,3,30,44,15,36,6,10,9,19,25,48,5,23,47 };
	int len = sizeof(a) / sizeof(a[0]);

	cout << "排序前：" << endl;
	for (int i = 0; i < len; i++)
	{
		cout << a[i] << "  ";
	}
	cout << endl;

	BucketSort(a, len);

	cout << "排序后：" << endl;
	for (int i = 0; i < len; i++)
	{
		cout << a[i] << "  ";
	}
	cout << endl;

	system("pause");
	return 0;
}