数据结构(九)计数排序

1、算法流程

(1)求取待排序数组A的最大值max；

(2)创建一个新的数组C[max+1],用于统计数组A中的每个元素a，小于等于a的个数。

(3)根据小于等于a的个数，来确定排序后，a在排序数组中的位置，进行位置填充；

2、代码实现

写代码需要注意事项：

(1)计数统计结束后，我们根据C[a]的大小填充元素a，每填充一次C[a]要减去1，这样是为了保证重复数据可以正常填充；

(2)填充如果是要稳定排序，那么需要使用反向填充的方案；

int * count_sort(int *data,int length)
{
    int max=data[0];
    for (int i = 1; i <length ; ++i) {
        if(max<data[i])
            max=data[i];
    }

    //统计每个数值计数
    int *count=new int[max+1]();
    for (int i = 0; i<length ; ++i) {
        count[data[i]]++;
    }

    //从左往右，统计小于data[i]的数值个数
    for (int i = 1; i <=max ; ++i) {
        count[i]+=count[i-1];
    }


    int *sort_data=new int[length]();
    for (int i = 0; i<length; ++i) {//不稳定排序，因为相等的数值，位置会调换，如果要实现稳定排序，那么就需要反向填充，用i--的方式循环
        sort_data[count[data[i]]-1]=data[i];//这边需要注意索引值等于：个数-1
        count[data[i]]--;//重复数据问题，每填充一次，索引值就要往前移位
    }

    delete[] count;


    return sort_data;
}


int test_sort() {


    int data[10]={5,1,6,7,8,4,2,2,10,13};
    //非比较排序算法

    int * sort_data=count_sort(data,10);
    for(int i=0;i<10;i++)
    {
        std::cout<<sort_data[i]<<std::endl;
    }
    delete[]sort_data;


    return 0;
}