基础算法(2)：排序(2)：计数排序

1.计数排序实现

? ? ?计数排序是一个非基于比较的稳定的线性时间的排序算法，而选择排序是基于比较的，计数排序不用，它的实现依靠计数。

? ? ?工作原理：使用一个额外的数组，其中第i个位置是待排序数组1中值等于i的元素的个数，任何根据额外数组来将待排序数组的元素排到正确的位置。

? ? ? ? ? 其实就是做了个映射处理，这个思想和哈希表很像，以后会讲到

? ? ? ? ? 很显然，这是牺牲了空间来换取时间，当待排序数组的值很大时，开辟的空间会很大，浪费了很多空间，所以算法本身就有优点有缺点，下面来看具体实现：

void countSort(int* a,int len)
{
  int max=a[0];
  for(int i=0;i<len;i++)//先找到最大值，方便后面开辟空间
  {
    if(a[i]>max)
     {
       max=a[i];
     }
   }
   int range=max+1;
   int* arr=(int*)calloc(range,sizeof(int));//开辟一个额外数组，并初始化为0
   for(int i=0;i<len;i++)
   {
     arr[a[i]]++;//进行映射，这是核心
   }
   int j=0;
   for(int i=0;i<range;i++)
   {
      while(arr[i]--)//将排好序的元素放回数组中
      {
        a[j]=i;
        j++;
      }
   }
    free(arr);
    arr=NULL;

2.计数排序的时间复杂度

? ? ? 很显然，问题规模为n，只进行了一次循环，没有进行比较，为n次，时间复杂度为O(n)，这是很可观的

3.leetcode题目

3.1 找不同

void countingSort(char* s)
{
    int* arr=(int*)calloc(256,sizeof(int));
    for(int i=0;s[i];i++)
    {
        arr[s[i]]++;
    }
     int j=0;
    for(int i=0;i<256;i++)
    {
        while(arr[i]--)
        {
            s[j]=i;
            j++;
        }
    }
      s[j]='\0';
}
char findTheDifference(char* s, char* t) {
    countingSort(s);
    countingSort(t);
     int i=0;
    for(;s[i];i++)
    {
        if(s[i]!=t[i])
        {
            return t[i];
        }
    }
    return t[i];
}

?3.2 既不是最小值也不是最大值

void countingSort(int* a,int len)
{
     int* arr=(int*)calloc(101,sizeof(int));
     for(int i=0;i<len;i++)
     {
          arr[a[i]]++;
     }
     int j=0;
     for(int i=0;i<101;i++)
     {
         while(arr[i]--)
         {
             a[j]=i;
             j++;
         }
     }
     free(arr);
     arr=NULL;
}
int findNonMinOrMax(int* nums, int numsSize){
     countingSort(nums,numsSize);
     for(int i=0;i<numsSize;i++)
     {
         if(nums[i]==nums[0])continue;
         if(nums[i]==nums[numsSize-1])continue;
         return nums[i];
     }
      return -1;
}

?