拜托,面试别再问我计数排序了!!!
排序,面试中,问的比较多。 时间复杂度为O(n)的排序,除了基数排序(Radix Sort),还有计数排序(Counting Sort)。今天,1分钟,通过几幅图,争取让大家搞懂计数排序。 计数排序的适用范围? 待排序的元素在某一个范围[MIN, MAX]之间。 画外音:很多业务场景是符合这一场景,例如uint32的数字排序位于[0, 2^32]之间。 计数排序的空间复杂度? 计数排序需要一个辅助空间,空间大小为O(MAX-MIN),用来存储所有元素出现次数(“计数”)。 画外音:计数排序的核心是,空间换时间。 计数排序的关键步骤? 步骤一:扫描待排序数据arr[N],使用计数数组counting[MAX-MIN],对每一个arr[N]中出现的元素进行计数; 步骤二:扫描计数数组counting[],还原arr[N],排序结束; 举个栗子: 假设待排序的数组, arr={5, 3, 7, 1, 8, 2, 9, 4, 7, 2, 6, 6, 2, 6, 6} 很容易发现,待排序的元素在[0, 10]之间,可以用counting[0,10]来存储计数。 第一步:统计计数 扫描未排序的数组...
