数据结构-计数排序

矫情吗；* 2022-06-04 01:21 196阅读 0赞

#### 计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置。通过以下几步就可以实现： ####

##### <1>:先遍历数组，找出最大值和最小值； #####

##### <2>:利用最大值最小值的差值，开辟一个大小为max-min+1的临时数组，并将元素初始化为0； #####

##### <3>:遍历源数组，把源数组每个元素的值减去min后作为临时数组的下标，同时在临时数组中对对应下标的数值进行自增操作；**源数组元素值 - min 作为 临时数组的下标。** #####

##### <4>:遍历临时数组，按照上面的公式，源数组的元素值 == 临时数组的下标 + min；需要注意的是可能源数组中一个数字出现了多次，所有在遍历时需要使用while循环，直至临时数组的元素值都减到0. #####

--------------------

#### **实现代码：** ####

#define _CRT_SECURE_NO_WARNINGS 1
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    void CountSort(int* arr, int sz)
    {
        int max = arr[0];
        int min = arr[0];
    
        //遍历找到最大最小值
        for (int i = 0; i < sz; i++)
        {
            if (arr[i] > max)
                max = arr[i];
            if (arr[i] < min)
                min = arr[i];
        }
    
        int len = max - min +1;
        vector<int> tmp(len, 0);
    
        for (int i = 0; i < sz; i++)
            tmp[arr[i] - min]++;
    
        //开始排序
        int index = 0;
        for (int i = 0; i < tmp.size(); i++)
        {
            while (tmp[i]--)
                arr[index++] = i + min;
        }
    }
    
    
    
    int main()
    {
        int arr[] = { 1,5,5,7,2,11};
        CountSort(arr,sizeof(arr)/sizeof(arr[0]));
    
        system("pause");
        return 0;
    }

--------------------

#### **临时数组对应截图** ####

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220604/fbfad62b90ea468486fbef68e8def94f.png