当前位置: 首页> 文旅> 酒店 > 爱购商城_中企动力官网邮箱_百度霸屏推广一般多少钱_广告联盟怎么做

爱购商城_中企动力官网邮箱_百度霸屏推广一般多少钱_广告联盟怎么做

时间:2025/7/11 14:28:49来源:https://blog.csdn.net/2302_80836956/article/details/143779559 浏览次数:0次
爱购商城_中企动力官网邮箱_百度霸屏推广一般多少钱_广告联盟怎么做

文章目录

  • 1. 计数排序(CountSort)
    • 1.1 核心思路
    • 1.2 实现代码
  • 2. 时间复杂度比较

1. 计数排序(CountSort)

1.1 核心思路

计数排序的核心思路是另外创建一个数组,记录原数组中出现的成员个数,再依次打印新数组中的成员个数。

在这里插入图片描述

以上述数组为例。已知数组中最小的数是1,最大的数是67.那么就需要开辟一个大小为max - min + 1的新数组。并且遍历原数组,将原数组成员的相应出现次数记录在新数组中。得到:

在这里插入图片描述

接着我们在遍历新数组,当新数组成员不等于0时,我们就打印相应的位置并且加上min。得到:

在这里插入图片描述

注意:由于计数排序需要另外开辟一个根据成员大小来决定大小的数组。所以计数排序的使用需要注意空间复杂度。当原数组的数据比较集中时,才推荐使用计数排序。

1.2 实现代码

// 计数排序
void CountSort(int* arr, int n)
{int max = arr[0], min = arr[0];for (int i = 1; i < n; i++){if (arr[i] > max)max = arr[i];if (arr[i] < min)min = arr[i];}//找到数组中的最大和最小值,方便开辟数组空间int range = max - min + 1;//数组的空间int* count = (int*)malloc(sizeof(int) * range);//开辟新数组countif (count == NULL)//count开辟失败就直接退出程序{perror("malloc fail!");exit(1);}memset(count, 0, sizeof(int) * range);//将新开辟的数组count的成员全部置于0for (int i = 0; i < n; i++){count[arr[i] - min]++;//已知数组的空间第一位是min,将arr[i] - min之后就是该成员在新数组的位置}int index = 0;for (int i = 0; i < range; i++)//将数组中全部的成员依次放回原数组{while (count[i]--)//count[i]表示该成员重复出现的次数{arr[index++] = i + min;//将排序完的数依次放回原数组中}}
}

2. 时间复杂度比较

在这里插入图片描述

根据时间复杂度来看,只推荐使用希尔排序,堆排序,快速排序,归并排序,计数排序。但是由于计数排序需要注意空间复杂度上面的问题,所以一般情况下,只推荐使用希尔,堆,快速,归并这四种排序方法。

另外关于“稳定性”,什么是稳定性?稳定性就是数组在排完序之后,原数组中成员的位置没有改变。例如:

在这里插入图片描述

上面的数组,将第一个出现的5定义为第一个5,第二个出现的5定义为第二个5,在排完序之后,应该是:

在这里插入图片描述

那么此时数组里的第一个5是不是刚才我们定义的第一个5呢?如果是,那么就可以说该排序方法具有稳定性;如果不是,则不具有稳定性。

以上就是所有的数组排序方法,可以根据具体的需求使用相应的排序方法。

关键字:爱购商城_中企动力官网邮箱_百度霸屏推广一般多少钱_广告联盟怎么做

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: