How to use bucket sort algorithm in C++

How to use the bucket sort algorithm in C

Bucket Sort is a sorting algorithm with linear time complexity, which is based on the concept of buckets A sorting algorithm for sorting. The basic idea of ​​bucket sorting is to divide the data to be sorted into several ordered buckets, and then sort each bucket separately.

In C, we can use vector containers and iterators to implement the bucket sort algorithm. The following is a specific sample code:

#include <iostream>
#include <vector>
#include <algorithm>

void BucketSort(std::vector<int>& arr, int numBuckets) {
    // 创建桶
    std::vector<std::vector<int>> buckets(numBuckets);
    
    // 将元素放入桶中
    for (int i = 0; i < arr.size(); i++) {
        int bucketIdx = arr[i] / numBuckets;
        buckets[bucketIdx].push_back(arr[i]);
    }
    
    // 对每个桶进行排序
    for (int i = 0; i < buckets.size(); i++) {
        std::sort(buckets[i].begin(), buckets[i].end());
    }
    
    // 将排序好的元素放回原数组
    int index = 0;
    for (int i = 0; i < buckets.size(); i++) {
        for (int j = 0; j < buckets[i].size(); j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

int main() {
    std::vector<int> arr = {5, 2, 8, 3, 1, 9, 4, 6, 7};
    
    std::cout << "Before sorting: ";
    for (int i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    
    // 指定桶的数量为3
    BucketSort(arr, 3);
    
    std::cout << "After sorting: ";
    for (int i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

In the above code, we define a BucketSort function to implement the bucket sorting algorithm. This function receives an integer array arr and the specified number of buckets numBuckets as parameters. First, we create a two-dimensional vector buckets to represent buckets, each bucket stores a portion of elements. We then put the elements into corresponding buckets based on their values. Next, the elements in each bucket are sorted. Finally, we put the sorted elements back into the original array.

In the main function, we create an integer array arr and initialize some elements. Then, call the BucketSort function to sort. Finally, we output the array contents before and after sorting.

Run the above code, the output result is as follows:

Before sorting: 5 2 8 3 1 9 4 6 7
After sorting: 1 2 3 4 5 6 7 8 9

You can see that after sorting by the bucket sort algorithm, the contents of the array have been arranged in ascending order.

The time complexity of bucket sorting is O(n k), where n is the number of elements to be sorted and k is the number of buckets. Since the number of buckets is fixed, the time complexity of bucket sorting can be considered linear. However, bucket sorting has a high space complexity and requires additional space to store buckets.

In summary, using the bucket sorting algorithm in C can quickly sort data, just provide a suitable number of buckets. When using the bucket sorting algorithm, you need to consider the distribution of elements to select the appropriate number of buckets to avoid wasting bucket space or uneven distribution of elements.

The above is the detailed content of How to use bucket sort algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!