字符串排序:键索引计数法

2024-08-30 10:18

本文主要是介绍字符串排序:键索引计数法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

字符串排序:键索引计数法

  • 描述
  • 适用性
  • 步骤
    • 1、频率统计
    • 2、构建索引
    • 3、数据分类
    • 4、回写数组
  • 代码实现
  • 总结
  • 参考

描述

关于字符串的排序有很多种方式,像《算法》一书中列举的低位优先、高位优先等,其中最先提到的是键索引计数法,它也是其他排序方式的基础,我们先来了解下。

适用性

关于键索引计数法进行字符串排序,并不是全部都适用,因为它的排序算法核心就是通过统计元素出现频次、构建排序因子的索引边界来递进式完成所有元素排序,它主要适合于以下场景:

  • 用于小整数键的算法
    比如数组arr ={1,2,3,4,2,3,4,2,1,3,4,2,3,4},它里面重复的数字比较多,不重复的只有1,2,3,4,这时就可以用此方法。
  • 用于小整数键的分组排序
    还可以应用在基于小整数键的分组排序,比如有字母{a,b,c,d,e,f,g,h},各字母不重复、但是分组重复,其分组序号格式{字母,分组号}描述为{a,1}、{b,2}、{c,1}、{d,2}、{e,3}、{f,4}、{g,4}、{h,1},最终按照分组号进行排序实现的元素排列为a、c、h、b、d、e、f、g
    在这里插入图片描述
    综上,我们可以看到按照分组号可以将元素归纳如下:
分组号元素
1a、c、h
2b、d
3e
4f、g

步骤

1、频率统计

在这里插入图片描述
我们可以看到,每个分组出现频次如下:

分组号元素元素出现频次
1a、c、h3
2b、d2
3e1
4f、g2

统计频次的目的是为了给构建索引提供条件,我们知道所谓键索引计数就是通过索引 + 频次来完成的。索引可以理解为每个分组的排序边界,每个分组的起始索引即较小一侧边界,而每个分组的结束索引即较大一侧边界,如果索引边界为startIndexendIndex,分组内元素出现频次为t,那么每个分组中的索引边界和分组内元素出现频次的关系是endIndex = startIndex + t,每个分组都按照逻辑序号紧紧相邻,较大的分组起始索引与它相邻的第一个较小分组的结束索引一致。

如果将这个场景延展到一个直线上,也可以将索引边界理解为坐标点,将频次理解为步长,或者是坐标点之间的间距

2、构建索引

在这里插入图片描述
当已知了间距,下面根据间距从0开始计算和整理索引边界,可以参考上图,方法很简单,是从0开始递增每个分组的频次即可。

3、数据分类

在这里插入图片描述
当建立好索引后,下面开始进行数据分类,说白了这一步就是将元素排序填充的过程,因为已经知道了所有排序分组的起止边界了,也知道每个分组的容量了,接下来就是挨个映射填充就可以完成排序工作了。

分组元素填充后,起始索引递增
这里面的填充技巧的细节点在于,每填充一个分组内元素后,将对应的该分组的起始索引递增1,代表完成了一个分组内地排序,若后续还有同样分组内的元素填充则理所当然填充到该分组的下一个临近位即可。

4、回写数组

这一步是将已排序好的元素重新回写到原数组中即可。

代码实现

  • 纯小整数版
/*** @author: <a href=mailto:keycasiter@qq.com>guanjian</a>* @date: 2021/4/8 13:15* @description: */
public class IndexCountSortDemo {public static void main(String[] args) {int[] nums = {2, 3, 4, 1, 2, 4, 3, 1, 2, 2, 1};indexCountIndex(nums);//打印结果   1 1 1 2 2 2 2 3 3 4 4}public static void indexCountIndex(int[] nums) {int[] count = new int[6];//计算频率for (int i = 0; i < nums.length; i++) {count[nums[i] + 1]++;}//将频率转化为索引for (int i = 1; i < count.length; i++) {count[i] = count[i] + count[i - 1];}//数据分类int[] aux = new int[nums.length];for (int i = 0; i < nums.length; i++) {aux[count[nums[i]]++] = nums[i];//aux[count[nums[i]]] = nums[i];//count[nums[i]]++;}//回写数据(这里是打印)for (int i = 0; i < nums.length; i++) {System.out.print(aux[i] + " ");}}
}
  • 小整数分组排序元素
/*** @author: <a href=mailto:keycasiter@qq.com>guanjian</a>* @date: 2021/4/8 13:15* @description: */
public class IndexCountSortDemo {public static class Item<T> {private int group;private T data;public Item(int group, T data) {this.group = group;this.data = data;}public int getGroup() {return group;}public void setGroup(int group) {this.group = group;}public T getData() {return data;}public void setData(T data) {this.data = data;}}public static void main(String[] args) {Item<String>[] arr = new Item[]{new Item(1, "a"),new Item(2, "b"),new Item(1, "c"),new Item(2, "d"),new Item(3, "e"),new Item(4, "f"),new Item(4, "g"),new Item(1, "h")};indexCountIndexByItem(arr);//打印结果   a c h b d e f g}public static void indexCountIndexByItem(Item[] arr) {int[] count = new int[6];//计算频率for (int i = 0; i < arr.length; i++) {count[arr[i].group + 1]++;}//将频率转化为索引for (int i = 1; i < count.length; i++) {count[i] = count[i] + count[i - 1];}//数据分类Item[] aux = new Item[arr.length];for (int i = 0; i < arr.length; i++) {aux[count[arr[i].group]++] = arr[i];// aux[count[arr[i].group]] = arr[i];// count[arr[i].group]++;}//回写数据(这里是打印)for (int i = 0; i < arr.length; i++) {System.out.print(aux[i].data + " ");}}
}

总结

键索引计数法是一种对于小整数键排序非常有效却常常被忽略的排序方法。理解它的工作原理是理解字符串排序的第一步,它是一个线性时间级别的排序方法。

参考

字符串排序:键索引计数法
《算法》第4版

这篇关于字符串排序:键索引计数法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1120534

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

Mysql中InnoDB与MyISAM索引差异详解(最新整理)

《Mysql中InnoDB与MyISAM索引差异详解(最新整理)》InnoDB和MyISAM在索引实现和特性上有差异,包括聚集索引、非聚集索引、事务支持、并发控制、覆盖索引、主键约束、外键支持和物理存... 目录1. 索引类型与数据存储方式InnoDBMyISAM2. 事务与并发控制InnoDBMyISAM