编辑代码

#include <iostream>
#include <math.h>

using namespace std;

bool insertSort(int array[], size_t arrLen) {
    if (arrLen < 0) {
        cout << "Please check your input." << endl;
        return false;
    }

    for (int orderedNum = 1; orderedNum < arrLen; ++orderedNum) {
        int insertValue = array[orderedNum];
        int orderedIndex = orderedNum - 1;
        for (; orderedIndex >= 0; --orderedIndex) {
            if (insertValue < array[orderedIndex]) {
                array[orderedIndex + 1] = array[orderedIndex];
            }
            else {
                break;
            }
        }
        array[orderedIndex+1] = insertValue;
    }

    return true;
}

bool insertSort_Sen(int array[], size_t arrLen) {
     if (arrLen < 0) {
        cout << "Please check your input." << endl;
        return false;
    }

    for (int orderedNum = 1; orderedNum < arrLen; ++orderedNum) {
        int insertValue = array[orderedNum];
        int orderedIndex = orderedNum - 1;
        while(orderedIndex >=0 && array[orderedIndex] > insertValue) {
           array[orderedIndex + 1] = array[orderedIndex];
           --orderedIndex;
        }
        array[orderedIndex+1] = insertValue;
    }

    return true;
}

void printArray(int array[], int arrLen) {
    for (int i = 0; i < arrLen; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

// 桶排序的核心思想：
// (1) 根据待排序数据的数据范围和桶的个数, 计算出每个桶内要装入的数据的范围
// (2) 遍历数组，把它里面的数据放入所在范围的桶
// (3) 对桶内数据进行排序
// (4) 按照桶的顺序取出桶内排序后的数据
bool bucketSort(int array[], size_t arrLen, size_t bucketCount) {
    const int DEFAULT_BUCKET_COUNT = 10;
    if(arrLen < 2) {
        return true;
    }

    if (bucketCount < 1) {
        bucketCount = DEFAULT_BUCKET_COUNT;
    }

    // 找出数组中的最大值和最小值
    int min = array[0];
    int max = array[0];

    for (size_t i = 1; i < arrLen; ++i)
    {
        if (min > array[i]) {
            min = array[i];
        }
        else if (max < array[i]) {
            max = array[i];
        }
    }

    // 创建桶
    int **buckets = new int*[bucketCount]();//创建桶

    //创建桶空间，只有桶里面有空间才能放数据
    for (size_t j = 0; j < bucketCount; j++)
    {
        buckets[j] = new int[arrLen]();
    }
    // 记录桶里面数据的个数
    int *bucketLen = new int[bucketCount]();//创建记录当前桶内数据个数，初始化为0
    

    

    //计算桶内数据的范围，可以把它想象为把一个线段，平均分成bucketSize个小线段，小线段的长度的范围就是bucketScope
    //为什么+1，大家知道min=10，max=90，其实有81个数据，如果按照（90-10）/10来分，你桶里面的数据范围只能从10到89，所以要用1补齐
    int bucketScope = floor((max - min)/bucketCount) + 1; 

    int bucketIndex = -1;

    // Put array value to buckets
    for (size_t k = 0; k < arrLen; ++k)
    {
        bucketIndex = floor((array[k] - min)/bucketScope); //计算数据所在桶的下标
        buckets[bucketIndex][bucketLen[bucketIndex]++] = array[k];//将数据放入桶中
    }

    // 按照桶的从小到大对数据进行排序
    int arrayIndex = 0;
    for (size_t l = 0; l < bucketCount; l++)
    {
        if (bucketLen[l] > 1) {
            insertSort(buckets[l], bucketLen[l]); //对桶内数据进行排序
        }

        for (size_t m = 0; m < bucketLen[l]; ++m) {
            array[arrayIndex++] = buckets[l][m];//将排好序的数据放回原数组
        }
        delete [] buckets[l];
        buckets[l] = NULL;
    }

    delete [] buckets;
    delete [] bucketLen;

    return true;

}

int main(){
    int array0[] = {};
    int arrayLen = sizeof(array0)/sizeof(int);

    printArray(array0, arrayLen);
    insertSort(array0, arrayLen);
    printArray(array0, arrayLen);

    cout << "=========================================" << endl;

    int array1[] = {1};
    arrayLen = sizeof(array1)/sizeof(int);

    printArray(array1, arrayLen);
    bucketSort(array1, arrayLen, 1);
    printArray(array1, arrayLen);

    cout << "=========================================" << endl;

    int array2[] = {2, 1};
    arrayLen = sizeof(array2)/sizeof(int);

    printArray(array2, arrayLen);
    bucketSort(array2, arrayLen, 2);
    printArray(array2, arrayLen);

    cout << "=========================================" << endl;

    int array3[] = {1, 5, 3};
    arrayLen = sizeof(array3)/sizeof(int);

    printArray(array3, arrayLen);
    bucketSort(array3, arrayLen, 2);
    printArray(array3, arrayLen);


    cout << "=========================================" << endl;

    int array4[] = {9, 12, 8, 7};
    arrayLen = sizeof(array4)/sizeof(int);

    printArray(array4, arrayLen);
    bucketSort(array4, arrayLen, 2);
    printArray(array4, arrayLen);

    cout << "=========================================" << endl;

    int array5[] = {9, 12, 8, 7, 3};
    arrayLen = sizeof(array5)/sizeof(int);

    printArray(array5, arrayLen);
    bucketSort(array5, arrayLen, 2);
    printArray(array5, arrayLen);
}