数据结构(九)计数排序

深藏阁楼爱情的钟 2022-05-31 03:12 152阅读 0赞

**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;
    }