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语言字典序排序算法解析及代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

时间: 2018-01-08

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

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

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排序算法之归并排序简单实现

算法描述:对于给定的一组记录,首先将每两个相邻的长度为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排序算法之堆排思想及代码实现

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

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

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

总结Java常用排序算法

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

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

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

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

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

基于Java实现的一层简单人工神经网络算法示例

本文实例讲述了基于Java实现的一层简单人工神经网络算法.分享给大家供大家参考,具体如下: 先来看看笔者绘制的算法图: 2.数据类 import java.util.Arrays; public class Data { double[] vector; int dimention; int type; public double[] getVector() { return vector; } public void setVector(double[] vector) { this.vect

Python实现基于二叉树存储结构的堆排序算法示例

本文实例讲述了Python实现基于二叉树存储结构的堆排序算法.分享给大家供大家参考,具体如下: 既然用Python实现了二叉树,当然要写点东西练练手. 网络上堆排序的教程很多,但是却几乎都是以数组存储的数,直接以下标访问元素,当然这样是完全没有问题的,实现简单,访问速度快,也容易理解. 但是以练手的角度来看,我还是写了一个二叉树存储结构的堆排序 其中最难的问题就是交换二叉树中两个节点. 因为一个节点最多与三个节点相连,那么两个节点互换,就需要考虑到5个节点之间的关系,也需要判断是左右孩子,这将是

Python实现的基于优先等级分配糖果问题算法示例

本文实例讲述了Python实现的基于优先等级分配糖果问题算法.分享给大家供大家参考,具体如下: 问题: 有n个人,每个人有一定的优先等级,等级高的人要比身边等级低得人得到的多,每个人都不会分不到 思路: 可以采用两头遍历的方法,顺序遍历保证等级高的人会比左边的人多,倒序遍历可以保证等级高的人比右边的人多 下面是具体实现: #!usr/bin/env python #encoding:utf-8 ''''' __AUthor__:沂水寒城 功能:分糖果 ''' def split_candy(ra

Java基于JDBC连接数据库及显示数据操作示例

本文实例讲述了Java基于JDBC连接数据库及显示数据操作.分享给大家供大家参考,具体如下: 1. 导入jdbc包 java要连接MySQL数据库需要用到JDBC工具(mysql-connector-java-5.1.39-bin.jar),这是一个jar包,不同的数据库对应不同的jar包,这里用的是MySQL数据库jar包,导入很简单,鼠标对项目右击 - Build Path - Configure Build Path - 右侧选Libraries - Add External JARs,选

Java实现合并两个有序序列算法示例

本文实例讲述了Java实现合并两个有序序列算法.分享给大家供大家参考,具体如下: 问题描述 输入:序列A<a0,a1,a2,...aq,aq+1,aq+2,...,ar>,其中a0<a1<...<aq,aq+1<aq+2<...<ar 输出:序列B<b0,b1,...,br>,其中b0<b1<...<br 算法思想 创建一个长度为r的数组R,将A中的序列看作是两个有序序列 B=A<a0,a1,a2,...,aq> C

java实现的AES秘钥生成算法示例

本文实例讲述了java实现的AES秘钥生成算法.分享给大家供大家参考,具体如下: import java.security.NoSuchAlgorithmException; import java.security.SecureRandom; import javax.crypto.KeyGenerator; import javax.crypto.SecretKey; public class Test { public static void main(String[] args) { g

java基于移位操作实现二进制处理的方法示例

本文实例讲述了java基于移位操作实现二进制处理的方法.分享给大家供大家参考,具体如下: /** * @author openks * @since 2013-9-21 移位操作实例 */ public class TestDisplacement { /** * @param args */ public static void main(String[] args) { // 十进制数字2向左移3位 即 二进制的10向左移3位即10000 转换为十进制为2的4次方 即16 System.ou

Java基于正则实现的日期校验功能示例

本文实例讲述了Java基于正则实现的日期校验功能.分享给大家供大家参考,具体如下: private void checkDate() throws IOException { // 4种分隔符 String sep = "[-\\./_]"; // 年份 String strPattern = "^(19[4-9]\\d|20\\d{2})" + sep; strPattern += "("; // 月(1,3,5,7,8,10,12) strP

PHP基于递归实现的约瑟夫环算法示例

本文实例讲述了PHP基于递归实现的约瑟夫环算法.分享给大家供大家参考,具体如下: 约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓.于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀.然后下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏. <?php $nu