桶排序&&计数排序&&基数排序

今天把三种排序放到一起写，因为原理都差不多。

桶排序

桶排序的代码我没有写，讲下思想就可以了。

图片.png

时间复杂度

O(n)

空间复杂度

O(n * m) n是多少个桶 m每个桶多少个元素

稳定排序

取决于每个桶中的元素使用什么排序算法

算法核心思想

将待排序元素按顺序拆分为N个桶，再对每个桶中的元素进行排序。之后按顺序输出每个桶中的元素。

计数排序

废话不多说先上代码

void countingSort(int arr[], int length) {
    int max = arr[0];
    for (int i = 1; i < length; ++i)
    {
        if (max < arr[i])
        {
            max = arr[i];
        }
    }

    int counting[max + 1];
    memset(&counting, 0, sizeof(int) * (max + 1));

    for (int i = 0; i < length; ++i)
    {
        counting[arr[i]]++;
    }

    for (int i = 1; i < max + 1; ++i)
    {
        counting[i] += counting[i - 1];
    }

    int temp[length];

    for (int i = length - 1; i >= 0; --i)
    {
        temp[--counting[arr[i]]] = arr[i];
    }

    for (int i = 0; i < length; ++i)
    {
        arr[i] = temp[i];
    }

    return;
}

时间复杂度

O(n)

空间复杂度

额外需要数组中最大元素大小的空间

稳定排序

算法核心思想

根据数组中最大元素创建一个临时数组。
扫描一遍数组，将临时数组中下标与当前元素对应的值加1。
将临时数组中值不为1的元素的下标输出，值为1就输出下标1次，值为2就输出下标两次，值为几就输出下标几次。
思想就这么简单，实现的逻辑有些绕。

一步步实现计数排序

根据数组中最大元素申请额外空间。

void countingSort(int arr[], int length) {
    int max = arr[0];
    for(int i = 1; i < length; ++i)
    {
        if(max < arr[i])
        {
             max = arr[i];
        }
    }

    //申请一个大小为最大数加1的数组
    int counting[max + 1];
    memset(&counting, 0, sizeof(int) * (max + 1));
}

计算每个元素出现的次数

void countingSort(int arr[], int length) {
    int max = arr[0];
    for(int i = 1; i < length; ++i)
    {
        if(max < arr[i])
        {
             max = arr[i];
        }
    }

    //申请一个大小为最大数加1的数组
    int counting[max + 1];
    memset(&counting, 0, sizeof(int) * (max + 1));

    //计算每个元素出现的次数，将对应下标的值加1
    for(int i = 0; i < length; ++i)
    {
        counting[arr[i]]++;
    }
}

将元素按顺序填装回数组

这里的填装顺序决定了计数排序是否为稳定算法

void countingSort(int arr[], int length) {
    int max = arr[0];
    for(int i = 1; i < length; ++i)
    {
        if(max < arr[i])
        {
             max = arr[i];
        }
    }

    //申请一个大小为最大数加1的数组
    int counting[max + 1];
    memset(&counting, 0, sizeof(int) * (max + 1));

    //计算每个元素出现的次数，将对应下标的值加1
    for(int i = 0; i < length; ++i)
    {
        counting[arr[i]]++;
    }

    //这一步计算出下标对应的元素应该在原数组中的位置
    //这个位置是从后往前计算的
    //假如有两个2 这里存储的是第二个 2 应该在原数组中的下标
    for(int i = 1; i < max + 1; ++i)
    {
        counting[i] += counting[i - 1];
    }

    //申请一个和原数组一样大的临时数组
    int temp[length];

    //将arr数组元素按照counting的对应关系赋值给temp
    for(int i = 0; i < length; ++i)
    {
        //counting[arr[i]] 就是 arr应该在的位置 下标从0开始要先减1
        temp[--counting[arr[i]]] = arr[i];
    }

    //将temp 赋值给 arr
    for(int i = 0; i < length; ++i)
    {
        arr[i] = temp[i];
    }
}

计数排序就已经完成了，难点就在计算原数组对应关系这，可以自己写写理解一下。

基数排序

基数排序就是计数排序的另一个版本，我们要对284，385，235这样的少量且值大的数组排序，如果用计数排序就太占用空间了，这是我们就可以使用基数排序。

先看代码

int lastNum(int num, int place) {
    int base = 1;
    while(place > 1) {
        place--;
        base *= 10;
    }

    printf("返回值 %d\n", (num / base) % 10);
    return (num / base) % 10;
}

void radixSort(int arr[], int length) {
    int max = arr[0];
    for (int i = 1; i < length; ++i)
    {
        if (max < arr[i])
        {
            max = arr[i];
        }
    }

    int max_size = 0;
    while(max > 0) {
        ++max_size;
        max /= 10;
    }

    for (int j = 1; j <= max_size; ++j)
    {

        int counting[10];
        memset(&counting, 0, sizeof(int) * 10);

        for (int i = 0; i < length; ++i)
        {
            counting[lastNum(arr[i], j)]++;
        }

        for (int i = 1; i < 10; ++i)
        {
            counting[i] += counting[i - 1];
        }


        int temp[length];

        for (int i = length - 1; i >= 0; --i)
        {
            temp[--counting[lastNum(arr[i], j)]] = arr[i];
        }

        for (int i = 0; i < length; ++i)
        {
            arr[i] = temp[i];
        }
    }
}

时间复杂度

O(n)

空间复杂度

每一位的范围不同而变化

稳定排序

算法核心思想

先对低位进行计数排序，然后在对高位进行计数排序，因为计数排序是稳定排序，将所有位都进行排序后整个数组就有序了。

因为基数排序就是基于计数排序实现的，我这里只讲一些不同的地方。

取数组中的某一位

int lastNum(int num, int place) {
    int base = 1;
    while(place > 1) {
        place--;
        base *= 10;
    }

    printf("返回值 %d\n", (num / base) % 10);
    return (num / base) % 10;
}

计算数组中最大元素的位数

void radixSort(int arr[], int length) {
    int max = arr[0];
    for (int i = 1; i < length; ++i)
    {
        if (max < arr[i])
        {
            max = arr[i];
        }
    }

    int max_size = 0;
    while(max > 0) {
        ++max_size;
        max /= 10;
    }
}

对每一位进行计数排序

void radixSort(int arr[], int length) {
    int max = arr[0];
    for (int i = 1; i < length; ++i)
    {
        if (max < arr[i])
        {
            max = arr[i];
        }
    }

    int max_size = 0;
    while(max > 0) {
        ++max_size;
        max /= 10;
    }
    
    //最大数的位数，有几位进行几次计数排序
    for (int j = 1; j <= max_size; ++j)
    {

        int counting[10];
        memset(&counting, 0, sizeof(int) * 10);

        for (int i = 0; i < length; ++i)
        {
            //通过lastNum函数获取对应位
            counting[lastNum(arr[i], j)]++;
        }

        for (int i = 1; i < 10; ++i)
        {
            counting[i] += counting[i - 1];
        }


        int temp[length];

        for (int i = length - 1; i >= 0; --i)
        {
            temp[--counting[lastNum(arr[i], j)]] = arr[i];
        }

        for (int i = 0; i < length; ++i)
        {
            arr[i] = temp[i];
        }
    }
}

如果你会计数排序的话基数排序已然不在话下了

看到这了，点个赞再走~