桶排序是计数排序的升级版，也是分治算法。
它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序
（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
简言之，将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。

#include <stdio.h>
#include <stdlib.h>
 
// 桶排序函数
void bucketSort(int arr[], int n) {
    // 创建桶数组
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    int bucket[maxVal + 1];
    for (int i = 0; i <= maxVal; i++) {
        bucket[i] = 0;
    }
 
    // 将元素放入桶中
    for (int i = 0; i < n; i++) {
        bucket[arr[i]]++;
    }
 
    // 从桶中取出元素并排序
    int index = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (bucket[i] > 0) {
            arr[index++] = i;
            bucket[i]--;
        }
    }
}
 
// 测试桶排序
int main() {
    int arr[] = {5, 2, 8, 4, 9, 1, 3, 7, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    printf("原始数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
 
    bucketSort(arr, n);
 
    printf("排序后数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
 
    return 0;
}

// 交换宏
#define swap(x,y) x=x+y,y=x-y,x=x-y

void bubbleSort(int arr[], int n)
{
	bool bExchange = false; // 交换标志

	for (int i = 0; i < n - 1; i++) // 最多做n-1趟排序 
	{
		bExchange = false;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(arr[j + 1], arr[j]);
				bExchange = true; // 发生了交换，故将交换标志置为真
			}
		}

		if (!bExchange) // 考虑有一趟排序未发生交换的理想情况，可以提前终止算法
			return;
	}
}