桶排序算法

提示

分组排序方法：桶排序通过将元素划分到多个桶中，然后对每个桶分别排序，最后合并桶以形成最终的排序数组。
桶的创建和填充：创建固定数量的桶，并根据元素的范围将它们分配到不同的桶中。
桶内排序和合并：每个桶使用适当的排序算法（如快速排序）进行排序，然后按顺序将所有桶中的元素合并回一个数组中。

桶排序是一种排序算法，它将未排序的数组元素划分为几组，称为桶。然后，每个桶使用任何适合的排序算法进行排序，或递归应用相同的桶排序算法。

最后，将排序好的桶组合成最终的排序数组。

分散-聚合方法

桶排序的过程可以理解为分散-聚合方法。首先，元素被分散到桶中，然后每个桶中的元素被排序。最后，元素按顺序聚集起来。

桶排序工作原理

桶排序的工作原理

假设输入数组为：

创建一个大小为 10 的数组。该数组的每个槽用作存储元素的桶。
将数组中的元素插入到桶中。元素根据桶的范围进行插入。

在我们的示例代码中，我们有从 0 到 1、1 到 2、2 到 3、...... (n-1) 到 n 的桶。假设，取一个输入元素 .23，它乘以 size = 10（即 .23*10=2.3）。然后，它被转换为一个整数（即 2.3≈2）。最后，.23 被插入到桶-2。

同样，.25 也被插入到同一个桶中。每次都取浮点数的下限值。

如果我们将整数作为输入，我们必须除以间隔（这里是 10）来获得下限值。

类似地，其他元素被插入到各自的桶中。桶排序步骤

使用任何稳定的排序算法对每个桶中的元素进行排序。这里，我们使用了快速排序（内置函数）。
从每个桶中收集元素。

通过遍历桶并在每个周期将单个元素插入原始数组来完成。一旦元素从桶中复制到原始数组，就会被删除。

桶排序算法

bucketSort()
  创建 N 个桶，每个桶可以存储一定范围的值
  对于所有的桶
    初始化每个桶的值为 0
  对于所有的桶
    将元素放入匹配范围的桶中
  对于所有的桶
    对每个桶中的元素进行排序
  从每个桶中收集元素
end bucketSort

Python、Java 和 C/C++ 中的桶排序代码

Python Java C C++

# Python 中的桶排序


def bucketSort(array):
    bucket = []

    # 创建空桶
    for i in range(len(array)):
        bucket.append([])

    # 将元素插入到各自的桶中
    for j in array:
        index_b = int(10 * j)
        bucket[index_b].append(j)

    # 对每个桶中的元素进行排序
    for i in range(len(array)):
        bucket[i] = sorted(bucket[i

])

    # 获取排序后的元素
    k = 0
    for i in range(len(array)):
        for j in range(len(bucket[i])):
            array[k] = bucket[i][j]
            k += 1
    return array


array = [.42, .32, .33, .52, .37, .47, .51]
print("降序排列的数组是")
print(bucketSort(array))

// Java 中的桶排序

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {
  public void bucketSort(float[] arr, int n) {
    if (n <= 0)
      return;
    @SuppressWarnings("unchecked")
    ArrayList<Float>[] bucket = new ArrayList[n];

    // 创建空桶
    for (int i = 0; i < n; i++)
      bucket[i] = new ArrayList<Float>();

    // 将元素添加到桶中
    for (int i = 0; i < n; i++) {
      int bucketIndex = (int) arr[i] * n;
      bucket[bucketIndex].add(arr[i]);
    }

    // 对每个桶中的元素进行排序
    for (int i = 0; i < n; i++) {
      Collections.sort((bucket[i]));
    }

    // 获取排序后的数组
    int index = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0, size = bucket[i].size(); j < size; j++) {
        arr[index++] = bucket[i].get(j);
      }
    }
  }

  // 驱动代码
  public static void main(String[] args) {
    BucketSort b = new BucketSort();
    float[] arr = { (float) 0.42, (float) 0.32, (float) 0.33, (float) 0.52, (float) 0.37, (float) 0.47,
        (float) 0.51 };
    b.bucketSort(arr, 7);

    for (float i : arr)
      System.out.print(i + "  ");
  }
}

// C语言中的桶排序

#include <stdio.h>
#include <stdlib.h>

#define NARRAY 7   // 数组大小
#define NBUCKET 6  // 桶的数量
#define INTERVAL 10  // 每个桶的容量

struct Node {
  int data;
  struct Node *next;
};

void BucketSort(int arr[]);
struct Node *InsertionSort(struct Node *list);
void print(int arr[]);
void printBuckets(struct Node *list);
int getBucketIndex(int value);

// 排序函数
void BucketSort(int arr[]) {
  int i, j;
  struct Node **buckets;

  // 创建桶并分配内存大小
  buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET);

  // 初始化空桶
  for (i = 0; i < NBUCKET; ++i) {
    buckets[i] = NULL;
  }

  // 将相应元素填充到桶中
  for (i = 0; i < NARRAY; ++i) {
    struct Node *current;
    int pos = getBucketIndex(arr[i]);
    current = (struct Node *)malloc(sizeof(struct Node));
    current->data = arr[i];
    current->next = buckets[pos];
    buckets[pos] = current;
  }

  // 打印桶及其元素
  for (i = 0; i < NBUCKET; i++) {
    printf("Bucket[%d]: ", i);
    printBuckets(buckets[i]);
    printf("\n");
  }

  // 对每个桶的元素进行排序
  for (i = 0; i < NBUCKET; ++i) {
    buckets[i] = InsertionSort(buckets[i]);
  }

  printf("-------------\n");
  printf("排序后的桶\n");
  for (i = 0; i < NBUCKET; i++) {
    printf("Bucket[%d]: ", i);
    printBuckets(buckets[i]);
    printf("\n");
  }

  // 将排序后的元素放回 arr 中
  for (j = 0, i = 0; i < NBUCKET; ++i) {
    struct Node *node;
    node = buckets[i];
    while (node) {
      arr[j++] = node->data;
      node = node->next;
    }
  }

  return;
}

// 对每个桶的元素进行排序的函数
struct Node *InsertionSort(struct Node *list) {
  struct Node *k, *nodeList;
  if (list == 0 || list->next == 0) {
    return list;
  }

  nodeList = list;
  k = list->next;
  nodeList->next = 0;
  while (k != 0) {
    struct Node *ptr;
    if (nodeList->data > k->data) {
      struct Node *tmp;
      tmp = k;
      k = k->next;
      tmp->next = nodeList;
      nodeList = tmp;
      continue;
    }

    for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
      if (ptr->next->data > k->data)
        break;
    }

    if (ptr->next != 0) {
      struct Node *tmp;
      tmp = k;
      k = k->next;
      tmp->next = ptr->next;
      ptr->next = tmp;
      continue;
    } else {
      ptr->next = k;
      k = k->next;
      ptr->next->next = 0;
      continue;
    }
  }
  return nodeList;
}

int getBucketIndex(int value) {
  return value / INTERVAL;
}

void print(int ar[]) {
  int i;
  for (i = 0; i < NARRAY; ++i) {
    printf("%d ", ar[i]);
  }
  printf("\n");
}

// 打印桶
void printBuckets(struct Node *list) {
  struct Node *cur = list;
  while (cur) {
    printf("%d ", cur->data);
    cur = cur->next;
  }
}

// 主函数
int main(void) {
  int array[NARRAY] = {42, 32, 33, 52, 37, 47, 51};

  printf("初始数组：");
  print(array);
  printf("-------------\n");

  BucketSort(array);
  printf("-------------\n");
  printf("排序后的数组：");
  print(array);
  return 0;
}

// C++中的桶排序
#include <iomanip>
#include <iostream>
using namespace std;

#define NARRAY 7 // 数组大小
#define NBUCKET 6 // 桶的数量
#define INTERVAL 10 // 每个桶的容量

struct Node {
int data;
struct Node \*next;
};

void BucketSort(int arr[]);
struct Node *InsertionSort(struct Node *list);
void print(int arr[]);
void printBuckets(struct Node \*list);
int getBucketIndex(int value);

// 排序函数
void BucketSort(int arr[]) {
int i, j;
struct Node \*\*buckets;

// 创建桶并分配内存大小
buckets = (struct Node \*_)malloc(sizeof(struct Node _) \* NBUCKET);

// 初始化空桶
for (i = 0; i < NBUCKET; ++i) {
buckets[i] = NULL;
}

// 将相应元素填充到桶中
for (i = 0; i < NARRAY; ++i) {
struct Node _current;
int pos = getBucketIndex(arr[i]);
current = (struct Node _)malloc(sizeof(struct Node));
current->data = arr[i];
current->next = buckets[pos];
buckets[pos] = current;
}

// 打印桶及其元素
for (i = 0; i < NBUCKET; i++) {
cout << "Bucket[" << i << "] : ";
printBuckets(buckets[i]);
cout << endl;
}

// 对每个桶的元素进行排序
for (i = 0; i < NBUCKET; ++i) {
buckets[i] = InsertionSort(buckets[i]);
}

cout << "-------------" << endl;
cout << "排序后的桶" << endl;
for (i = 0; i < NBUCKET; i++) {
cout << "Bucket[" << i << "] : ";
printBuckets(buckets[i]);
cout << endl;
}

// 将排序好的元素放回 arr
for (j = 0, i = 0; i < NBUCKET; ++i) {
struct Node \*node;
node = buckets[i];
while (node) {
arr[j++] = node->data;
node = node->next;
}
}

// 释放桶内存
for (i = 0; i < NBUCKET; ++i) {
struct Node *node;
node = buckets[i];
while (node) {
struct Node *tmp;
tmp = node;
node = node->next;
free(tmp);
}
}
free(buckets);
return;
}

// 对每个桶的元素进行插入排序的函数
struct Node *InsertionSort(struct Node *list) {
struct Node *k, *nodeList;
if (list == 0 || list->next == 0) {
return list;
}

nodeList = list;
k = list->next;
nodeList->next = 0;
while (k != 0) {
struct Node *ptr;
if (nodeList->data > k->data) {
struct Node *tmp;
tmp = k;
k = k->next;
tmp->next = nodeList;
nodeList = tmp;
continue;
}

    for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
      if (ptr->next->data > k->data)
        break;
    }

    if (ptr->next != 0) {
      struct Node *tmp;
      tmp = k;
      k = k->next;
      tmp->next = ptr->next;
      ptr->next = tmp;
      continue;
    } else {
      ptr->next = k;
      k = k->next;
      ptr->next->next = 0;
      continue;
    }

}
return nodeList;
}

// 获取桶索引
int getBucketIndex(int value) {
return value / INTERVAL;
}

// 打印桶函数
void print(int ar[]) {
int i;
for (i = 0; i < NARRAY; ++i) {
cout << setw(3) << ar[i];
}
cout << endl;
}

void printBuckets(struct Node *list) {
struct Node *cur = list;
while (cur) {
cout << setw(3) << cur->data;
cur = cur->next;
}
}

// 主函数
int main(void) {
int array[NARRAY]

= {42, 32, 33, 52, 37, 47, 51};

cout << "初始数组: " << endl;
print(array);
cout << "-------------" << endl;

BucketSort(array);
cout << "-------------" << endl;
cout << "排序后的数组: " << endl;
print(array);
}

桶排序复杂度

时间复杂度
最佳	O(n+k)
最差	O(n^2)
平均	O(n)
空间复杂度	O(n+k)
---	---
稳定性	是
---	---

最差情况复杂度： O(n^2) 当数组中有范围接近的元素时，它们可能会被放置在同一个桶中。这可能导致某些桶中的元素数量多于其他桶。这使得复杂度取决于用于对桶中元素进行排序的算法。当元素顺序相反时，复杂度甚至会更糟。如果使用插入排序对桶中的元素进行排序，那么时间复杂度将变为 O(n^2)。
最佳情况复杂度： O(n+k) 当元素在桶中均匀分布，并且每个桶中的元素数量大致相等时，会发生这种情况。如果桶内元素已经排序，复杂度将变得更佳。如果使用插入排序对桶中的元素进行排序，那么在最佳情况下，总体复杂度将是线性的，即 O(n+k)。O(n) 是制作桶的复杂度，O(k) 是使用最佳情况下线性时间复杂度的算法对桶中元素进行排序的复杂度。
平均情况复杂度： O(n) 当元素在数组中随机分布时发生。即使元素没有均匀分布，桶排序也以线性时间运行。只要桶大小的平方和在总元素数量上是线性的，这一点就成立。

桶排序应用

桶排序用于以下情况：

输入在一个范围内均匀分布。
存在浮点数值

桶排序算法

桶排序的工作原理​

桶排序算法​

Python、Java 和 C/C++ 中的桶排序代码​

桶排序复杂度​

桶排序应用​

类似的排序算法​

桶排序的工作原理

桶排序算法

Python、Java 和 C/C++ 中的桶排序代码

桶排序复杂度

桶排序应用

类似的排序算法