Spandsorteringsalgoritme (Java, Python, C/C++ Code Eksempler)
⚡ Smart opsummering
Bucket Sort spreder inputelementer i flere buckets, sorterer hver bucket uafhængigt og samler dem for at producere et endeligt sorteret array.

Hvad er Bucket Sort?
Bucket Sort, ofte kaldet bin sortering, er en sammenligningsbaseret fordelingssorteringsmetode, der accepterer et usorteret array som input og producerer et sorteret array som output. Denne teknik fordeler elementer i flere buckets og sorterer hver bucket individuelt ved hjælp af en anden sorteringsalgoritme, såsom indsættelsessortering. Derefter flettes alle buckets sammen for at danne det endelige sorterede array.
Bucket Sort bruges almindeligvis, når elementerne er:
- Flydende komma værdier
- Ensartet fordelt over et kendt interval
Tidskompleksiteten af Bucket Sort afhænger af antallet af anvendte buckets og ensartetheden af inputfordelingen. Mens andre sorteringsalgoritmer som f.eks. skal sortere, flette sortering, heapsortering og hurtigsortering For at opnå en best-case tidskompleksitet på O(n*logn), kan Bucket Sort-algoritmen opnå lineær tidskompleksitet O(n) under gunstige forhold.
Bucket Sort følger scatter-gather-metoden. Elementer spredes i tilsvarende buckets, sorteres inde i hver bucket og samles for at danne et sorteret array som det sidste trin. Denne scatter-gather-metode diskuteres i det følgende afsnit.
Scatter-Samle-tilgangen
Store, komplekse problemer kan til tider være udfordrende at løse direkte. Scatter-gather-tilgangen adresserer sådanne problemer ved at opdele hele datasættet i klynger. Hver klynge behandles separat, og resultaterne samles igen for at producere det endelige svar.
Sådan implementerer Bucket Sort-algoritmen scatter-gather-metoden:
Sådan fungerer spandsortering
Det grundlæggende arbejdsprincip for Bucket Sort er som følger:
- Der oprettes et sæt tomme buckets. Antallet af buckets kan variere afhængigt af den valgte politik.
- Fra input-arrayet placeres hvert element i dets tilsvarende bucket.
- Hver bucket sorteres individuelt ved hjælp af en sekundær sorteringsalgoritme.
- De sorterede buckets sammenkædes for at producere et enkelt outputmatrix.
Kaldenavn Code
Start Create N empty buckets For each array element: Calculate bucket index Put that element into the corresponding bucket For each bucket: Sort elements within each bucket Merge all the elements from each bucket Output the sorted array End
Metode 1: Bucket Sort Algoritme for Floating-Point Numbers
Bucket Sort-algoritmen for flydende tal inden for området [0.0, 1.0]:
Trin 1) Opret ti (10) tomme spande. Den første spand indeholder tal inden for intervallet [0.0, 0.1]. Den anden spand indeholder [0.1, 0.2] og så videre.
Trin 2) For hvert array-element:
- a. Beregn spandindekset ved hjælp af formlen:
bucket_index = no_of_buckets * array_element - b. Indsæt elementet i bucket[bucket_index]
Trin 3) Sorter hver spand individuelt ved hjælp af indføringssortering.
Trin 4) Saml alle buckets i et enkelt sorteret array.
Lad os gennemgå et eksempel på en bucketsortering. I dette eksempel sorterer vi følgende array:
Trin 1) Først opretter vi 10 tomme spande. Den første spand indeholder tal i [0.0, 0.1]. Den anden spand indeholder [0.1, 0.2] og så videre.
Trin 2) For hvert array-element skal du beregne bucket-indekset og placere elementet i den pågældende bucket.
Bucket-indekset beregnes ved hjælp af formlen:
bucket_index = no_of_buckets * array_element
Beregning af spandindeks:
a) 0.78
bucket_index = no_of_buckets * array_element
= 10 * 0.78
= 7.8
Derfor gemmes elementet 0.78 i bucket[floor(7.8)] eller bucket[7].
b) 0.17
bucket_index = no_of_buckets * array_element
= 10 * 0.17
= 1.7
Array-elementet 0.17 er gemt i bucket[floor(1.7)] eller bucket[1].
c) 0.39
bucket_index = no_of_buckets * array_element
= 10 * 0.39
= 3.9
0.39 er gemt i bucket[floor(3.9)] eller bucket[3].
Efter iterering over alle array-elementer ser buckets ud som følger:
Trin 3) Hver bucket sorteres derefter ved hjælp af indsættelsessortering. Efter sorteringsoperationen er outputtet:
Trin 4) I det sidste trin sammenkædes buckets til et enkelt array. Dette array er det sorterede resultat af inputtet.
Hver bucket er sammenkædet med outputmatrixen. For eksempel sammenkædelsen af de andre bucket-elementer:
Sammenkædningen af de sidste bucket-elementer er vist nedenfor:
Efter sammenkædning er det resulterende array det ønskede sorterede array.
Skovlsorteringsprogram i C/C++
Input:
//Bucket Sort Program in C/C++ //For values without integer parts #include <bits/stdc++.h> #define BUCKET_SIZE 10 using namespace std; void bucketSort(float input[], int array_size) { vector <float>bucket[BUCKET_SIZE]; for (int i = 0; i < array_size; i++) { int index = BUCKET_SIZE*input[i]; bucket[index].push_back(input[i]); } for (int i = 0; i < BUCKET_SIZE; i++) sort(bucket[i].begin(), bucket[i].end()); int out_index = 0; for (int i = 0; i < BUCKET_SIZE; i++) for (int j = 0; j < bucket[i].size(); j++) input[out_index++] = bucket[i][j]; } int main() { float input[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.69}; int array_size = sizeof(input)/sizeof(input[0]); bucketSort(input, array_size); cout <<"Sorted Output: "; for (int i = 0; i< array_size; i++) cout<<input[i]<<" "; return 0; }
Output:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Spandsorteringsprogram ind Python
Input:
# Bucket Sort Program in Python # For values without integer parts def bucketSort(input): output = [] bucket_size = 10 for bucket in range(bucket_size): output.append([]) for element in input: index = int(bucket_size * element) output[index].append(element) for bucket in range(bucket_size): output[bucket] = sorted(output[bucket]) out_index = 0 for bucket in range(bucket_size): for element in range(len(output[bucket])): input[out_index] = output[bucket][element] out_index += 1 return input input = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.69] print("Sorted Output:") print(bucketSort(input))
Output:
Sorted Output: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]
Spand Sorter i Java
Input:
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class BucketSort { private static final int BUCKET_SIZE = 10; public static void bucketSort(float[] input, int arraySize) { List<Float>[] bucket = new ArrayList[BUCKET_SIZE]; for (int i = 0; i < arraySize; i++) { int index = (int)(BUCKET_SIZE * input[i]); if (bucket[index] == null) { bucket[index] = new ArrayList<>(); } bucket[index].add(input[i]); } for (int i = 0; i < BUCKET_SIZE; i++) { if (bucket[i] != null) { Collections.sort(bucket[i]); } } int outIndex = 0; for (int i = 0; i < BUCKET_SIZE; i++) { if (bucket[i] != null) { for (float value: bucket[i]) { input[outIndex++] = value; } } } } public static void main(String[] args) { float[] input = {0.78f,0.17f,0.39f,0.26f,0.72f,0.94f,0.21f,0.12f,0.23f,0.69f}; int arraySize = input.length; bucketSort(input, arraySize); System.out.println("Sorted Output:"); for (int i = 0; i < arraySize; i++) { System.out.print(input[i]+" "); } } }
Output:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Metode 2: Bucket Sort Algoritme for heltalselementer
Sorteringsalgoritmen for bucket-data, der indeholder tal uden for området [0.0, 1.0], er en smule anderledes end den foregående. algoritmeDe nødvendige trin i denne sag er som følger:
Trin 1) Find det største og mindste antal elementer i arrayet.
Trin 2) Vælg antallet af buckets, n, og initialiser dem som tomme.
Trin 3) Beregn rækkevidden eller spændvidden for hver spand ved hjælp af formlen:
span = (maximum - minimum) / n
Trin 4) For hvert array-element:
- 1. Beregn spandindekset:
bucket_index = (element - minimum) / span - 2. Indsæt elementet i bucket[bucket_index]
Trin 5) Sorter hver spand ved hjælp af indføringssortering.
Trin 6) Sammensæt alle spandene i et enkelt array.
Lad os gennemgå et eksempel på denne Bucket Sort-algoritme. I dette eksempel sorterer vi følgende array:
Trin 1) I det første trin finder vi det maksimale og minimale antal elementer i det givne array. I dette eksempel er maksimum 24 og minimum 1.
Trin 2) Dernæst vælger vi antallet af tomme buckets, n. I dette eksempel bruger vi 5 buckets og initialiserer dem som tomme.
Trin 3) Spændet for hver spand beregnes ved hjælp af formlen:
span = (maximum - minimum) / n = (24 - 1) / 5 = 4
Derfor indeholder den første spand tal inden for [0, 5]. Den anden spand indeholder [5, 10], og så videre.
Trin 4) For hvert array-element beregnes bucket-indekset, og elementet placeres i den pågældende bucket. Bucket-indekset beregnes ved hjælp af formlen:
bucket_index = (element - minimum) / span
Beregning af spandindeks:
a) 11
bucket_index = (element – minimum) / span
= (11 – 1) / 4
= 2
Således er element 11 gemt i bucket[2].
b) 9
bucket_index = (element – minimum) / span
= (9 – 1) / 4
= 2
Bemærk: Da 9 er et grænseelement for bucket[1], tilføjes det til bucket[1] i stedet for at blive placeret i den samme bucket som det foregående element.
Efter at have udført operationerne for hvert element, ser buckets ud som følger:
Trin 5) Nu sorteres hver spand ved hjælp af indsættelsessortering. Spandene efter sortering:
Trin 6) I det sidste trin sammenkædes buckets til et enkelt array. matrix er det sorterede resultat af inputtet.
Skovlsorteringsprogram i C/C++
Input:
#include<bits/stdc++.h> using namespace std; void bucketSort(vector < double > & input, int No_Of_Buckets) { double max_value = * max_element(input.begin(), input.end()); double min_value = * min_element(input.begin(), input.end()); double span = (max_value - min_value) / No_Of_Buckets; vector<vector <double>> output; for (int i = 0; i < No_Of_Buckets; i++) output.push_back(vector <double>()); for (int i = 0; i < input.size(); i++) { double difference = (input[i] - min_value) / span - int((input[i] - min_value) / span); if (difference == 0 && input[i] != min_value) output[int((input[i] - min_value) / span) - 1].push_back(input[i]); else output[int((input[i] - min_value) / span)].push_back(input[i]); } for (int i = 0; i < output.size(); i++) { if (!output[i].empty()) sort(output[i].begin(), output[i].end()); } int index = 0; for (vector <double> & bucket: output) { if (!bucket.empty()) { for (double i: bucket) { input[index] = i; index++; } } } } int main() { vector <double> input ={11,9,21,8,17,19,13,1,24,12}; int No_Of_Buckets = 5; bucketSort(input, No_Of_Buckets); cout<<"Sorted Output:"; for (int i=0; i < input.size(); i++) cout <<input[i]<<" "; return 0; }
Output:
Sorted Output:1 8 9 11 12 13 17 19 21 24
Spandsorteringsprogram ind Python
Input:
def bucketSort(input, No_Of_Buckets): max_element = max(input) min_element = min(input) span = (max_element - min_element) / No_Of_Buckets output = [] for bucket in range(No_Of_Buckets): output.append([]) for element in range(len(input)): diff = (input[element] - min_element) / span - int( (input[element] - min_element) / span ) if diff == 0 and input[element] != min_element: output[int((input[element] - min_element) / span) - 1].append( input[element] ) else: output[int((input[element] - min_element) / span)].append(input[element]) for bucket in range(len(output)): if len(output[bucket]) != 0: output[bucket].sort() index = 0 for bucket in output: if bucket: for element in bucket: input[index] = element index = index + 1 input = [11, 9, 21, 8, 17, 19, 13, 1, 24, 12] No_Of_Buckets = 5 bucketSort(input, No_Of_Buckets) print("Sorted Output: ", input)
Output:
Sorted Output: [1, 8, 9, 11, 12, 13, 17, 19, 21, 24]
Spand Sorter i Java
Input:
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class BucketSort { public static void bucketSort(List < Double > input, int No_Of_Buckets) { double max_value = Collections.max(input); double min_value = Collections.min(input); double span =(max_value - min_value) / No_Of_Buckets; List<List<Double>> output = new ArrayList<>(); for (int i = 0; i < No_Of_Buckets; i++) { output.add(new ArrayList<>()); } for (Double value: input) { double difference = (value - min_value) / span - ((value - min_value) / span); if (difference == 0 && value != min_value) { output.get((int)((value - min_value) / span) - 1).add(value); } else { output.get((int)((value - min_value) / span)).add(value); } } for (List <Double> bucket: output) { if (!bucket.isEmpty()) { Collections.sort(bucket); } } int index = 0; for (List <Double> bucket: output) { if (!bucket.isEmpty()) { for (Double value: bucket) { input.set(index,value); index++; } } } } public static void main(String[] args) { List <Double> input = new ArrayList<>(); input.add(11.0); input.add(9.0); input.add(21.0); input.add(8.0); input.add(17.0); input.add(19.0); input.add(13.0); input.add(1.0); input.add(24.0); input.add(12.0); int No_Of_Buckets = 5; bucketSort(input, No_Of_Buckets); System.out.println("Sorted Output:"); for (Double value: input) { System.out.print(value + " "); } } }
Output:
Sorted Output: 1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0
Fordele og ulemper ved spandsortering
| FORDELE | ULEMPER |
|---|---|
| Udfører hurtigere beregninger på ensartet fordelte data | Bruger mere plads sammenlignet med algoritmer til sortering på stedet |
| Kan bruges som en ekstern sorteringsmetode til store datasæt | Yder dårligt, når dataene ikke er ensartet fordelt |
| Spande kan behandles uafhængigt og parallelt | Kræver kendskab til dataområdet og -fordelingen på forhånd |
Bucket Sort kompleksitetsanalyse
Sorteringstid for bucket-kompleksitet
- Bedste sags kompleksitet: Hvis alle array-elementerne er ensartet fordelt og præsorteret inden for hver bucket, kræver det O(n) tid at sprede elementerne i de tilsvarende buckets. Derefter sorteres hver bucket ved hjælp af indsætnings sortering koster O(k). Således er den samlede kompleksitet O(n+k).
- Gennemsnitlig sagskompleksitet: For gennemsnitlige tilfælde antager vi, at inputtene er ensartet fordelt. Således opnår Bucket Sort-algoritmen en lineær tidskompleksitet på O(n+k). Her kræves O(n) tid til at sprede elementerne og O(k) tid til at sortere dem ved hjælp af indsættelsessortering.
- Worst Case-kompleksitet: I værste fald er elementerne ikke ensartet fordelt og koncentreres i en eller to spande. I så fald forringes Bucket Sort til en adfærd, der ligner en boblesorteringsalgoritmeDerfor er tidskompleksiteten af Bucket Sort i værste fald O(n²).
Pladskompleksitet af spandsortering
Rumkompleksiteten af Bucket Sort er O(n*k). Her er n antallet af elementer, og k er antallet af buckets, der kræves for at indeholde dem under sortering.


















