Java语言字典序排序算法解析及代码示例

字典序法就是按照字典排序的思想逐一产生所有排列。

在数学中，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法。 这种泛化主要在于定义有序完全有序集合（通常称为字母表）的元素的序列（通常称为计算机科学中的单词）的总顺序。

对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。

例如，由1,2,3组成的所有排列，从小到大的依次为：

123,132,213,231,312,321
由1,2,3,4组成的所有排列：

1234, 1243, 1324, 1342, 1423, 1432,
2134, 2143, 2314, 2341, 2413, 2431,
3124, 3142, 3214, 3241, 3412, 3421,
4123, 4132, 4213, 4231, 4312, 4321.

首先要对给定的字符集中的字符规定了一个先后关系，在此基础上按照顺序依次产生每个排列。

[例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。

生成给定全排列的下一个排列，所谓一个的下一个就是这一个与下一个之间没有字典顺序中相邻的字符串。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

后一个排列与前一个排列之间存在一定的关系，后一个排列的求解过程如下：

设有排列(p)=2763541，按照字典式排序，它的下一个排列是什么？

2763541 （找最后一个正序35）
2763541 （找3后面比3大的最后一个数4）
2764531（交换3,4的位置）
2764135 （把4后面的5,3,1反转）

下面给出求 p[1…n] 的下一个排列的描述：

求 i = max{j | p[j – 1] < p[j]} （找最后一个正序）
求 j = max{k| p[i – 1] < p[k]} （找最后大于 p[i – 1] 的）
交换 p[i – 1] 与 p[j]得到 p[1] … p[i-2] p[j] p[i] p[i+1] … p[j-1] p[i-1] p[j+1] … p[n]
反转 p[j] 后面的数得到 p[1] …p[i-2] p[j] p[n] … p[j+1] p[i-1] p[j-1] … p[i]

代码实现如下：

private static int[] getPermutation(int[] in) {
	int[] ns = in;
	int base = -1;
	for (int i=ns.length-1; i>=1; i--) {
		if (ns[i-1] < ns[i]) {
			base = i-1;
			break;
		}
	}
	//已经到最后一个排列了 全部是逆序
	if (base == -1) return null;
	int bigger=0;
	for (int i=ns.length-1; i>=base; i--) {
		if (ns[i] > ns[base]) {
			bigger = i;
			break;
		}
	}
	//   System.out.println(bigger);
	swap(ns, base, bigger);
	reverse(ns,base+1,ns.length-1);
	return ns;
}
private static void reverse(int[] ns, int i, int j) {
	int left = i, right = j;
	while (left < right) {
		swap(ns, left, right);
		left++;
		right--;
	}
}
private static void swap(int[] ns, int base, int bigger) {
	int temp = ns[base];
	ns[base] = ns[bigger];
	ns[bigger] = temp;
}

总结

以上就是本文关于Java语言字典序排序算法解析及代码示例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

赞 (0)

相关推荐

  • Java排序算法之堆排思想及代码实现

    Java排序算法之堆排思想及代码实现

    在介绍堆排序前,我们需要了解一下一种数据结构 -- 顶堆. 什么是顶堆? 它是一颗完全二叉树,顶堆有大顶堆和小顶堆两种.所谓大顶堆就是在这颗完全二叉树中,任何一颗子树都满足:父结点的值 > 孩子结点的值:小顶堆则相反. 如图: 什么是堆排序(Heapsort)? 利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种.可以利用数组的特点快速定位指定索引的元素. 现在给我们一个无序数组,我们将其从小到大排序,使用堆排序的实现步骤和思想如下: 1.让这个数组变成一个大根堆 2.将最后一

  • java实现的各种排序算法代码示例

    折半插入排序 折半插入排序是对直接插入排序的简单改进.此处介绍的折半插入,其实就是通过不断地折半来快速确定第i个元素的 插入位置,这实际上是一种查找算法:折半查找.Java的Arrays类里的binarySearch()方法,就是折半查找的实现,用 于从指定数组中查找指定元素,前提是该数组已经处于有序状态.与直接插入排序的效果相同,只是更快了一些,因 为折半插入排序可以更快地确定第i个元素的插入位置 代码: package interview; /** * @author Administrat

  • 总结Java常用排序算法

    排序算法常用的有冒泡排序,选择排序和插入排序,下面将用Java语言实现这三种排序方式,并且介绍一种由插入排序拓展出来的希尔排序. 1.冒泡排序(BubbleSort)是一种最简单的排序算法.它的基本思想是迭代地对输入序列的第一个元素到最后一个元素进行俩俩比较,当满足条件时交换这俩个元素的位置,该过程持续到不需要执行上述过程的条件时. 2.我们自定义一个排序的函数为sorter(int[]array); private static void sorter(int[] array) for(int

  • Java数组常用排序算法实例小结

    本文实例讲述了Java数组常用排序算法.分享给大家供大家参考,具体如下: 1.冒泡排序法 SortArray_01.java public class SortArray_01 { public static void main(String args[]) { int[] array = { 14, 5, 86, 4, 12, 3, 21, 13, 11, 2, 55, 66, 22 }; // 创建一个初始化的一维数组array System.out.println("未排序的数组:&quo

  • Java基于分治法实现的快速排序算法示例

    Java基于分治法实现的快速排序算法示例

    本文实例讲述了Java基于分治法实现的快速排序算法.分享给大家供大家参考,具体如下: package cn.nwsuaf.quick; /** * 随机产生20个数,并对其进行快速排序 * * @author 刘永浪 * */ public class Quick { /** * 交换函数,实现数组中两个数的交换操作 * * @param array * 待操作数组 * @param i * 交换数组的第一个下标 * @param j * 交换数组的第二个下标 */ public static

  • 快速排序算法在Java中的实现

    快速排序算法在Java中的实现

    快速排序的原理:选择一个关键值作为基准值.比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的).一般选择序列的第一个元素. 一次循环:从后往前比较,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换.找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换.直到从前往后的比较索引>从后往前比较的索引,结束第一次循环,此时,对于基准值来说,左右两

  • Java排序算法之归并排序简单实现

    算法描述:对于给定的一组记录,首先将每两个相邻的长度为1的子序列进行归并,得到 n/2(向上取整)个长度为2或1的有序子序列,再将其两两归并,反复执行此过程,直到得到一个有序序列. package sorting; /** * 归并排序 * 平均O(nlogn),最好O(nlogn),最坏O(nlogn);空间复杂度O(n);稳定;较复杂 * @author zeng * */ public class MergeSort { public static void merge(int[] a,

  • Java分治归并排序算法实例详解

    本文实例讲述了Java分治归并排序算法.分享给大家供大家参考,具体如下: 1.分治法 许多有用的算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归地调用其自身以解决紧密相关的若干子问题.这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解. 分治模式在每层递归时都有三个步骤: (1)分解原问题为若干子问题,这些子问题是原问题的规模较小的实例. (2)解决这些子问题,递归地求解各子问题.然而,

  • Java语言字典序排序算法解析及代码示例

    字典序法就是按照字典排序的思想逐一产生所有排列. 在数学中,字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法. 这种泛化主要在于定义有序完全有序集合(通常称为字母表)的元素的序列(通常称为计算机科学中的单词)的总顺序. 对于数字1.2.3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的.例如对于5个数字的排列 12354和12345,排列12345在前,排列12354在后.按照这样的规定,5个数字的所有的

  • Java语言描述存储结构与邻接矩阵代码示例

    Java语言描述存储结构与邻接矩阵代码示例

    存储结构 要存储一个图,我们知道图既有结点,又有边,对于有权图来说,每条边上还带有权值.常用的图的存储结构主要有以下二种: 邻接矩阵 邻接表 邻接矩阵 我们知道,要表示结点,我们可以用一个一维数组来表示,然而对于结点和结点之间的关系,则无法简单地用一维数组来表示了,我们可以用二维数组来表示,也就是一个矩阵形式的表示方法. 我们假设A是这个二维数组,那么A中的一个元素aij不仅体现出了结点vi和结点vj的关系,而且aij的值正可以表示权值的大小. 以下是一个无向图的邻接矩阵表示示例: 从上图我们可

  • C语言选择排序算法及实例代码

    选择排序是排序算法的一种,这里以从小到大排序为例进行讲解. 基本思想及举例说明 选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置:然后,选出第二小的数,放在第二个位置:以此类推,直到所有的数从小到大排序. 在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换. 下面,以对 3  2  4  1 进行选择排序说明排序过程,使用min_index 记录当前最小的数所在的位置. 第1轮 排序过程 (寻找第1小的数所在的位置) 3  2  4  1(最初, m

  • Java语言资源国际化步骤解析

    这篇文章主要介绍了Java语言资源国际化步骤解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 语言资源国际化步骤: 1. 定义资源文件(如:language),需要使用命令native2ascii命令进行转码:(native2ascii是jdk中的转码工具,在jdk的bin目录下) 2. 定义工具类(LangusgeUtils)读取资源文件: 3. 定义调用资源文件类(TestResourceBundle) 注意:native2ascii 命

  • Java语言Consistent Hash算法学习笔记（代码示例）

    本文研究的主要是ConsistentHashing算法代码. 一致性哈希(Consistent Hash) 协议简介 一致性哈希算法在1997年由麻省理工学院提出(参见0),设计目标是为了解决因特网中的热点(Hot pot)问题,初衷和CARP十分类似.一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用. 哈希算法 一致性哈希提出了在动态变化的Cache环境中,哈希算法应该满足的4个适应条件: 平衡性(Balance) 平衡性是指哈希的结果能够尽可能分

  • C语言 八大排序算法的过程图解及实现代码

    C语言 八大排序算法的过程图解及实现代码

    目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具有相同的关

  • C语言 八大排序算法的过程图解及实现代码

    C语言 八大排序算法的过程图解及实现代码

    目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 代码实现 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具

  • Java实现基本排序算法的示例代码

    Java实现基本排序算法的示例代码

    目录 1. 概述 2. 插入排序 2.1 直接插入排序 2.2 希尔排序(缩小增量排序) 3. 选择排序 3.1 直接选择排序 3.2 堆排序 4. 交换排序 4.1 冒泡排序 4.2 快速排序 5. 归并排序 6. 计数排序(非比较类型的排序) 7. 排序算法总结 1. 概述 排序概念:就是将一串记录按照其中某个或某些关键字的大小,递增或递减的排列起来的操作. 稳定性:通俗的将就是数据元素不发生有间隔的交换,例如: 内部排序:数据元素全部放在内存中的排序 外部排序:数据元素太多不能一次加载到内

  • Java实现拓扑排序算法的示例代码

    Java实现拓扑排序算法的示例代码

    目录 拓扑排序原理 1.点睛 2.拓扑排序 3.算法步骤 4.图解 拓扑排序算法实现 1.拓扑图 2.实现代码 3.测试 拓扑排序原理 1.点睛 一个无环的有向图被称为有向无环图.有向无环图是描述一个工程.计划.生产.系统等流程的有效工具.一个大工程可分为若干子工程(活动),活动之间通常有一定的约束,例如先做什么活动,有什么活动完成后才可以开始下一个活动. 用节点表示活动,用弧表示活动之间的优先关系的有向图,被称为 AOV 网. 在 AOV 网中,若从节点 i 到节点 j 存在一条有向路径,则称

  • C语言 奇偶排序算法详解及实例代码

    C语言 奇偶排序算法详解及实例代码

    C语言奇偶排序算法 奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算.这是与冒泡排序特点类似的一种比较排序.该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换.下一步重复该操作,但针对所有的(偶-奇)位置数字对.如此交替进行下去. 使用奇偶排序法对一列随机数字进行排序的过程 处理器数组的排序 在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连.所有处理器可同时与邻居进行比较.交

随机推荐