数据结构中的排序技术

2025年3月17日 | 阅读20分钟

引言

排序是计算机科学中的一项基本操作，它包括将一组对象按特定顺序排列。它广泛应用于数据库管理、数据分析和搜索等许多不同领域。在数据结构中，采用不同的排序技术来高效地组织和操作大量数据。

排序技术

有各种排序技术，列在下表中

算法	描述	时间复杂度	空间复杂度
冒泡排序	比较相邻的元素，交换任何不按顺序排列的元素，并重复此过程，直到数组排序完成。	O(n^2)	O(1)
选择排序	将输入数组分为两部分：已排序部分和未排序部分。它通过反复选择未排序区域中的最小元素并将其移至已排序区域来实现。	O(n^2)	O(1)
插入排序	通过将每个未排序的元素连续插入已排序子数组中的适当位置，一次一个元素地构建最终排序的数组。	O(n^2)	O(1)
合并排序	归并排序将输入数组分成两半，分别对每一半进行迭代排序，然后合并两个已排序的半部分，以创建最终的排序数组。	O(n log n)	O(n)
快速排序	选择一个枢轴元素并将数组分区，使得所有小于枢轴的元素都放在它前面，所有大于枢轴的元素都放在它后面。然后递归地对枢轴之前和之后的子数组进行排序。	O(n log n)	O(log n)
堆排序	从输入数组创建最大堆，然后定期从堆中删除最大元素，将其与最后一个元素交换，并修改堆，直到数组排序完成。	O(n log n)	O(1)
计数排序	创建一个计数数组来跟踪输入数组中不同元素的数量。然后通过计算计数的累积和来确定每个元素的位置。	O(n + k)	O(n + k)
桶排序	将输入数组划分为一组存储桶，其中每个存储桶代表一个值范围。它根据元素的值将它们分配到相应的存储桶中。然后，每个存储桶分别排序，通常使用不同的排序方法。	O(n^2) 或 O(n + k)	O(n)
基数排序	通过处理元素的最不重要数字（LSD）到最重要数字（MSD）的各个数字或字符来对元素进行排序。作为子程序，它可以采用可靠的排序算法。	O(d * (n + k))	O(n + k)

冒泡排序

称为“冒泡排序”的简单排序方法会分析相邻的元素，迭代地遍历列表，并交换任何不按顺序排列的元素。要对整个列表进行排序，请重复此步骤。

示例

让我们考虑一个整数数组：{5, 2, 8, 12, 3}。

在第一次遍历中，算法比较 5 和 2，交换它们，然后比较 5 和 8（不交换）。接下来，它比较 8 和 12（不交换），最后比较 12 和 3，导致交换。数组变为：{2, 5, 8, 3, 12}。
在第二次遍历中，算法比较 2 和 5（不交换），5 和 8（不交换），以及 8 和 3，导致交换。数组变为：{2, 5, 3, 8, 12}。
在第三次遍历中，算法比较 2 和 5（不交换），5 和 3，导致交换。数组变为：{2, 3, 5, 8, 12}。
在第四次遍历中，所有元素已经排序，因此不发生交换。

程序

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; ++i) {
        for (int j = 0; j < size - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                // Swap the elements
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {5, 2, 8, 12, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, size);

    cout << "Sorted array: ";
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

说明

bubbleSort 函数接受一个数组（arr）及其大小（size）作为输入。它使用嵌套循环遍历数组并比较相邻元素。

如果当前元素大于下一个元素，则执行交换。此过程重复进行，直到最大元素“冒泡”到数组末尾。

在 main 函数中初始化一个名为 arr 的数组，并使用 sizeof 运算符确定数组的大小。

然后调用 bubbleSort 函数，传入数组及其大小。

程序输出

选择排序

选择排序是一种使用原地比较的排序算法。它将输入数组分为两部分：已排序部分和未排序部分。在每次迭代中，算法从该部分的未排序部分选择最小（或最大）元素，并将其插入到该部分的已排序部分的开头。

示例

考虑相同的整数数组：{5, 2, 8, 12, 3}。

在第一次迭代中，算法找到最小元素 2，并将其与第一个元素交换。数组变为：{2, 5, 8, 12, 3}。
在第二次迭代中，算法在未排序部分（从第二个元素开始）找到最小元素 3，并将其与第二个元素交换。数组变为：{2,5, 8, 12, 3}。
在第三次迭代中，算法确定第三个元素是未排序段中最小的元素，从该元素开始，并将其与该元素交换。数组变为：{2, 3, 8, 12, 5}。
在第四次迭代中，算法在未排序部分（从第四个元素开始）找到最小元素 5，并将其与第四个元素交换。数组变为：{2, 3, 5, 12, 8}。
在第五次迭代中，未排序部分只剩下一个元素，因此不发生交换。

程序

#include <iostream>
using namespace std;

void selectionSort(int arr[], int size) {
    for (int i = 0; i < size - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < size; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the minimum element with the current element
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {5, 2, 8, 12, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, size);

    cout << "Sorted array: ";
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

说明

selectionSort 函数接受一个数组（arr）及其大小（size）作为输入。它使用嵌套循环遍历数组。内层循环在数组的剩余未排序部分中搜索最小元素，而外层循环选择当前成员。

当内层循环完成时，外层循环的当前元素与最小元素交换。这样做可确保最小元素被移至排序中的正确位置。

在 main 函数中初始化一个名为 arr 的数组后，使用 sizeof 运算符确定数组的大小。然后调用 selectionSort 函数，传入数组及其大小。

程序输出

插入排序

插入排序是一种简单的排序算法，它一次构建一个完成的排序数组。一次一个元素，迭代地考虑输入数组，将其插入数组的已排序部分中的正确位置。

示例

让我们使用相同的整数数组：{5, 2, 8, 12, 3}。

在第一次迭代中，算法将 5 视为第一个元素，该元素已排序，因此不发生更改。
在第二次迭代中，算法考虑 2 并将其插入 5 之前，结果为 {2, 5, 8, 12, 3}。
在第三次迭代中，算法考虑 8，它已位于正确的位置。
在第四次迭代中，算法考虑 12，它已位于正确的位置。
在第五次迭代中，算法考虑 3 并将其插入 2 和 5 之间，结果为 {2, 3, 5, 8, 12}。

程序

#include <iostream>
using namespace std;


void insertionSort(int arr[], int size) {
    for (int i = 1; i < size; ++i) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {5, 2, 8, 12, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, size);

    cout << "Sorted array: ";
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

说明

insertionSort 函数接受数组 arr 及其大小 size 作为输入。它开始将数组已排序部分的元素与第二个元素（i = 1）进行比较。然后它向后（j = i - 1）遍历已排序部分，如果元素大于键值，则将它们向右移动。

内部 while 循环继续，直到 j 变为负数或索引 j 处的元素不大于键。此循环将元素向右移动，为键值在其正确的排序位置腾出空间。

while 循环之后，键值将被插入到排序位置（arr[j + 1] = key）。数组的元素一次处理一个，直到所有元素都已处理。

在 main 函数中初始化名为 arr 的数组后，使用 sizeof 运算符确定数组的大小。然后调用 insertionSort 函数，传入数组及其大小。

程序输出

合并排序

归并排序是一种分治算法，它将输入数组分成更小的子数组，对它们进行排序，然后将它们合并以产生已排序的输出。它使用“合并”操作将较小的已排序子数组合并成一个较大的已排序数组。

示例

考虑整数数组：{5, 2, 8, 12, 3}。

算法将数组分成两半：{5, 2} 和 {8, 12, 3}。
它进一步将前半部分分为 {5} 和 {2}。
单个元素已排序，因此算法合并 {5} 和 {2} 得到 {2, 5}。
类似地，后半部分 {8, 12, 3} 被分成 {8} 和 {12, 3}，然后进一步分为 {12} 和 {3}。
子数组 {8} 和 {12} 被合并得到 {8, 12}。
最后，子数组 {2, 5} 和 {8, 12, 3} 被合并得到排序后的数组 {2, 3, 5, 8, 12}。

程序

#include<iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];

    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {5, 2, 8, 12, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, size - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

说明

mergeSort 函数递归地将数组分成更小的子数组，直到每个子数组只包含一个元素。数组被 mergeSort 函数反复分成更小的子数组，直到每个子数组只包含一个元素。

然后通过按排序顺序比较和组合它们的组件来合并子数组。

merge 函数使用两个已排序的子数组将它们合并成一个已排序的数组。它比较两个子数组的组件，并将它们按原始数组的正确顺序排列。

在 main 方法中初始化一个数组，然后使用 mergeSort 函数对其进行排序。最后打印排序后的数组。

程序输出

快速排序

另一种分治技术，它根据枢轴元素对数组进行分区。它选择一个枢轴并重新排列数组的组件，使得靠近枢轴的组件放在前面，远离枢轴的组件放在后面。这些子数组一遍又一遍地重复此过程，直到整个数组排序完成。

示例

使用整数数组：{5, 2, 8, 12, 3}。

算法选择一个枢轴元素，该元素可以通过多种方式选择（例如，数组中的最后一个元素）。

在第一次迭代中，枢轴选择为 3。
算法重新排列元素，使得所有小于 3 的元素都放在它前面，所有大于 3 的元素都放在它后面。数组变为：{2, 3, 8, 12, 5}。
枢轴之前的子数组（2 和 3）已排序。
枢轴之后的子数组（8、12 和 5）使用相同的过程递归排序。
在第二次迭代中，枢轴选择为 5。
重新排列后，数组变为：{2, 3, 5, 12, 8}。
算法递归地对子数组进行排序，直到整个数组排序完成。

程序

#include <iostream>
using namespace std;


int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);

        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

int main() {
    int arr[] = {5, 2, 8, 12, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, size - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

说明

partition 函数选择数组中的最后一个元素作为枢轴，并重新排列数组的组件，使得所有小于枢轴的元素都移到左边，所有大于枢轴的元素都移到右边。它返回枢轴元素的索引。

quickSort 函数通过选择枢轴、对数组进行分区以及递归排序子数组来递归应用快速排序算法。当子数组大小为 1 或更小时停止。

在 main 函数中初始化一个数组，然后使用 quickSort 函数对其进行排序。最后打印排序后的数组。

程序输出

堆排序

堆排序是一种基于比较的排序算法，它使用堆数据结构来高效地以升序或降序对元素进行排序。它通过将数组转换为二叉堆并反复从堆中提取最大（升序）或最小（降序）元素，直到数组完全排序。

下面使用一个好的例子来解释堆排序算法

考虑一个数字数组：[9, 7, 5, 2, 1, 8, 6, 3, 4]。

1. 构建最大堆：我们首先需要从给定的数组创建一个二叉堆。从最后一个非叶节点 (n/2-1) 开始，我们堆化数组，使最大元素始终位于根。在这种情况下，最后一个非叶节点位于索引 4。

[9, 7, 5, 2, 1, 8, 6, 3, 4]（原始数组）

[9, 7, 6, 4, 1, 8, 5, 3, 2]（堆化后）

2. 交换根与最后一个元素：将根（即第一个元素）与堆的最后一个元素交换。在这种情况下，交换索引 0 和索引 8。

[2, 7, 6, 4, 1, 8, 5, 3, 9]（交换后）

3. 减小堆的大小：将堆大小减 1，并对根元素（现在位于索引 0）进行堆化。这将把下一个最大元素移到根。

[8, 7, 6, 4, 1, 2, 5, 3, 9]（堆化后）

4. 重复步骤 2 和 3：直到堆大小为 1，根据需要重复步骤 2 和 3。每次迭代后，最大元素将移到数组的末尾。

[7, 4, 6, 3, 1, 2, 5, 8, 9]

[6, 4, 5, 3, 1, 2, 7, 8, 9]

[5, 4, 2, 3, 1, 6, 7, 8, 9]

[4, 3, 2, 1, 5, 6, 7, 8, 9]

[3, 1, 2, 4, 5, 6, 7, 8, 9]

[2, 1, 3, 4, 5, 6, 7, 8, 9]

[1, 2, 3, 4, 5, 6, 7, 8, 9]

数组现在按升序排序。

程序

#include <iostream>
using namespace std;


void heapify(int arr[], int n, int i) {
    int largest = i;     // Initialize largest as root
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

说明

heapify 函数比较节点与其左子节点和右子节点，并在必要时将其与较大的子节点交换，确保最大堆属性。

heapSort 函数从数组构建最大堆，然后通过将其与最后一个元素交换、减小堆大小并调用 heapify 来维护最大堆属性来反复提取最大元素。

在 main 函数中初始化一个数组，并使用 heapSort 对数组进行排序。然后打印排序后的数组。

程序输出

计数排序

计数排序是一种线性排序方法，它根据计数或频率来排列元素。对于具有已知最大值的非负整数范围，它效果很好。计数排序不包含任何比较操作，它比许多其他排序算法更快。

示例

让我们考虑一个整数数组作为我们的输入：[4, 2, 5, 1, 3, 4, 2, 4]。我们假设输入值的范围是 1 到 5。

找到输入数组中的最高值。在这种情况下，最大数字是 5。
创建一个维度为最大值加 1 的计数数组。最初将计数数组的每个元素设置为 0。
遍历输入数组时，通过增加计数数组中相应索引的值来计算每个值出现的次数。例如，在输入数组 [4, 2, 5, 1, 3, 4, 2, 4] 中，我们将如下更新计数数组：countingArray[1] = 1, countingArray[2] = 2, countingArray[3] = 1, countingArray[4] = 3, countingArray[5] = 1。
通过对先前计数进行求和来修改计数数组。此过程有助于确定元素在排序数组中的正确位置。例如，修改计数数组后，它将是：countingArray[1] = 1, countingArray[2] = 3, countingArray[3] = 4, countingArray[4] = 7, countingArray[5] = 8。
创建一个与输入数组大小相同的临时数组。
应从左到右遍历输入数组。对于每个元素，通过访问计数数组找到其在临时数组中的位置。减少计数数组中该元素的计数。将元素放置在临时数组中的计算位置。
将临时数组的内容复制回第一个输入数组。输入数组现在已排序。

程序

#include <bits/stdc++.h>
#include <vector>

void countingSort(std::vector<int>& arr) {
    int max = *max_element(arr.begin(), arr.end());  // Step 1


    std::vector<int> countingArray(max + 1, 0);  // Step 2

    for (int i = 0; i < arr.size(); i++) {
        countingArray[arr[i]]++;  // Step 3
    }

    for (int i = 1; i < countingArray.size(); i++) {
        countingArray[i] += countingArray[i - 1];  // Step 4
    }

    std::vector<int> temp(arr.size());

    for (int i = arr.size() - 1; i >= 0; i--) {  // Step 6
        temp[countingArray[arr[i]] - 1] = arr[i];
        countingArray[arr[i]]--;
    }

    for (int i = 0; i < arr.size(); i++) {  // Step 7
        arr[i] = temp[i];
    }
}

int main() {
    std::vector<int> arr = {4, 2, 5, 1, 3, 4, 2, 4};

    countingSort(arr);

    std::cout << "Sorted array: ";
    for (int i = 0; i < arr.size(); i++) {
std::cout << arr[i] << " ";
}
return 0;
}

说明

我们找到数组中的最大元素以确定元素的范围。然后创建一个计数数组，将其所有项初始化为 0，并给它一个大小（max + 1）。计数数组应遍历输入数组，增加每个条目的计数。

然后，应更新计数数组以存储条目总数。该元素表示小于或等于元素索引的元素数量。

应创建与输入数组大小相同的临时数组。

反向遍历输入数组。使用计数数组，将每个元素放置在临时数组中其应有的位置。

要创建已排序的数组，请将临时数组中的条目复制回输入数组。

程序输出

基数排序

基数排序是一种非比较排序算法，它根据数字或位来排列对象。它通过将元素按每个有效数字或位分组，然后反复将它们分发到不同的存储桶中来工作。如果整数、字符串或其他数据类型可以表示为数字或位的序列，则可以应用基数排序。

示例

让我们考虑一个整数数组作为输入：[170, 45, 75, 90, 802, 24, 2, 66]。我们将使用十进制基数排序，它根据数字从最低有效位到最高有效位对元素进行排序。

在输入数组中，确定最高值。在这种情况下，最大值为 802。
对每个数字执行计数排序，从最低有效位到最高有效位。最低有效位应首先出现，然后是最高有效位。
首先，使用最低有效位（即个位）对组件进行排序。此步骤创建十个存储桶（0-9），并将元素根据其最低有效位的数值分发到这些存储桶中。例如，根据个位排序后，数组变为 [170, 90, 802, 2, 24, 45, 75, 66]。
接下来，根据十位数字对元素进行排序。同样，根据其十位数字的值将元素分发到十个存储桶中。根据十位排序后，数组变为 [802, 2, 24, 45, 66, 170, 75, 90]。
对于每个后续数字，直到达到最高有效数字，重复上一个过程。使用基于最高有效数字的排序对数组进行完全排序。

程序

#include <iostream>
using namespace std;

// Function to get the maximum value in the array

int getMax(int arr[], int n) {

    int max = arr[0];

    for (int i = 1; i < n; i++) {

        if (arr[i] > max)

            max = arr[i];

    }

    return max;

}
// Function to perform counting sort based on the digit represented by exp

void countingSort(int arr[], int n, int exp) {

    const int RANGE = 10; // Possible digits are 0 to 9

    int output[n];

    int count[RANGE] = {0};

    // Count the occurrences of each digit

    for (int i = 0; i < n; i++)

        count[(arr[i] / exp) % 10]++;

    // Calculate cumulative count to determine the positions

    for (int i = 1; i < RANGE; i++)

        count[i] += count[i - 1];

    // Build the output array

    for (int i = n - 1; i >= 0; i--) {

        output[count[(arr[i] / exp) % 10] - 1] = arr[i];

        count[(arr[i] / exp) % 10]--;

    }

    // Copy the output array to the original array

    for (int i = 0; i < n; i++)

        arr[i] = output[i];

}

// Radix sort implementation

void radixSort(int arr[], int n) {

    int max = getMax(arr, n);

    // Perform counting sort for each digit position

    for (int exp = 1; max / exp > 0; exp *= 10)

        countingSort(arr, n, exp);

}

// Function to print an array

void printArray(int arr[], int n) {

    for (int i =0; i < n; i++)

cout << arr[i] << " ";
cout << endl;

}
// Main function to test the radix sort
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};

int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";

printArray(arr, n);

radixSort(arr, n);

cout << "Sorted array: ";
printArray(arr, n);

return 0;
}

说明

getMax 函数查找数组中的最大元素以确定最大位数。

countingSort 函数使用计数数组，根据特定数字（由 exp 确定）执行计数排序。它计算每个数字的计数，然后确定输出数组中数字的位置。

从最低有效数字到最高有效数字，radixSort 函数为每个数字位置执行计数排序。

printArray 函数打印数组的项。

在 main 函数中，初始化一个数组，并打印其原始内容。

通过调用 radixSort 函数使用基数排序对数组进行排序。

最后打印排序后的数组。

程序输出

桶排序

桶排序是一种排序算法，它根据输入元素的取值范围将它们分成不同的“桶”，然后分别对每个桶中的元素进行排序。当输入数字均匀分布在一个范围内时，它效果最好。

桶排序可以分两步完成：分发和收集。分发步骤将元素放入相应的桶中，收集步骤将来自桶的元素合并以获得排序后的数组。

示例

让我们考虑一个浮点数数组作为我们的输入：[0.42, 0.32, 0.21, 0.91, 0.15, 0.84, 0.67]。我们假设输入值的范围是从 0 到 1。
创建一个空桶数组，其中桶的数量对应于输入值的范围。
在遍历数组时，将输入数组的每个组件放入适当的桶中。可以通过将元素乘以桶的数量并取整数部分来完成分发。
使用任何合适的排序算法（例如，插入排序、快速排序）对每个桶中的元素进行单独排序。
按顺序从桶中收集元素。可以通过遍历桶将元素添加回原始数组。
数组现在已排序。

程序

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

void bucketSort(std::vector<float>& arr) {
    int n = arr.size();

    // Step 1: Create an array of empty buckets
    std::vector<std::vector<float>> buckets(n);

    // Step 2: Distribute elements into buckets
    for (int i = 0; i < n; i++) {
        int bucketIndex = n * arr[i];
        buckets[bucketIndex].push_back(arr[i]);
    }

    // Step 3: Sort elements within each bucket
    for (int i = 0; i < n; i++) {
        std::sort(buckets[i].begin(), buckets[i].end());
    }

    // Step 4: Collect elements from buckets
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < buckets[i].size(); j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

int main() {
    std::vector<float> arr = {0.42, 0.32, 0.21, 0.91, 0.15, 0.84, 0.67};

    bucketSort(arr);

    std::cout << "Sorted array: ";
    for (int i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }

    return 0;
}

说明

创建一个空桶数组，其中每个桶代表一个值范围。

根据其值将输入数组中的每个元素放入适当的桶中。桶索引通过将元素乘以桶的数量来确定。

对每个桶中的元素进行排序。在此代码中，使用 std::sort 函数对元素进行排序。

从桶中按正确的顺序收集元素。在迭代遍历每个桶之后，将已排序的元素添加到输出数组中。

main 函数初始化一个浮点数输入数组。

最后，打印排序后的数组。

程序输出

下一个主题在二叉搜索树中查找顺时针数组

← 上一个下一个 →

数据结构中的排序技术

引言

排序技术

冒泡排序

程序

选择排序

程序

插入排序

程序

合并排序

程序

快速排序

程序

堆排序

程序

计数排序

程序

基数排序

程序

桶排序

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

数据结构中的排序技术

引言

排序技术

冒泡排序

程序

选择排序

程序

插入排序

程序

合并排序

程序

快速排序

程序

堆排序

程序

计数排序

程序

基数排序

程序

桶排序

程序

相关帖子

证明顶点覆盖是 NP 完全的

将中缀表达式转换为前缀表达式

二叉搜索树中的 floor 和 ceiling

从字符流中查找第一个非重复字符

逆序数

N 元树的所有元素之和

数据结构中的 K-D 树

树中的非路径三元组计数

使用 RMQ 在二叉树中查找 LCA

反向排序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器