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

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# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

MySQL更新某个字段拼接固定字符串的实现

《MySQL更新某个字段拼接固定字符串的实现》在MySQL中,我们经常需要对数据库中的某个字段进行更新操作,本文就来介绍一下MySQL更新某个字段拼接固定字符串的实现,感兴趣的可以了解一下... 目录1. 查看字段当前值2. 更新字段拼接固定字符串3. 验证更新结果mysql更新某个字段拼接固定字符串 -

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

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

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