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