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

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

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

Java桶排序算法

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

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

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

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

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

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

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

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

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

在這里插入圖片描述

實現(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個桶
	int bucketsize[5];  //每個桶中元素個數(shù)的計數(shù)器

	//初始化桶和桶計數(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++)  //對每個桶中的數(shù)據(jù)進行排序
		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];  //將每個桶中的元素填充到數(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;
}