字典排序算法（通俗易懂）

2024-07-17 19:08| 来源: 网络整理| 查看: 265

我们先看一个例子。

示例： 1 2 3的全排列如下：

1 2 3 ， 1 3 2 ， 2 1 3 ， 2 3 1 ， 3 1 2 ， 3 2 1

我们这里是通过字典序法找出来的。

那么什么是字典序法呢？

从上面的全排列也可以看出来了，从左往右依次增大，对这就是字典序法。可是如何用算法来实现字典序法全排列呢？

我们再来看一段文字描述：（用字典序法找124653的下一个排列）

你主要看红色字体部分就行了，这就是步骤。

如果当前排列是124653,找它的下一个排列的方法是，从这个序列中从右至左找第一个左邻小于右邻的数，

如果找不到，则所有排列求解完成，如果找得到则说明排列未完成。

本例中将找到46,计4所在的位置为i,找到后不能直接将46位置互换，而又要从右到左到第一个比4大的数，

本例找到的数是5，其位置计为j，将i与j所在元素交换125643,

然后将i+1至最后一个元素从小到大排序得到125346，这就是124653的下一个排列。

下图是用字典序法找1 2 3的全排列（全过程）：

总结得出字典排序算法四步法：

字典排序：第一步：从右至左找第一个左邻小于右邻的数，记下位置i，值list[a] 第二部：从右边往左找第一个右边大于list[a]的第一个值，记下位置j，值list[b] 第三步：交换list[a]和list[b]的值第四步：将i以后的元素重新按从小到大的顺序排列举例：125643的下一个字典序列第一步：右边值大于左边的35,j=3;list[b]=6; 第三步：交换list[a]和list[b]的值，序列125643->126543 第四步：将位置2以后的元素重新排序,126543->126345; 结束： 126345即125643的下一个序列

代码实现（C语言）：

#include #define swap(a,b) {int temp=a;a=b;b=temp;} //交换a，b值 void sort(int arr[],int start,int end)//冒泡排序，从start到end的排序，使用时注意是数组的下标，如数组下标0-3排序，sort（arr,0,3） { int i,j; for(i=0;iarr[a]) //这是字典排序第二步，获取arr[b]的值 { b=j1; break; } } swap(arr[a],arr[b]); //这是第三步 sort(arr,a+1,n-1); //这是第四步 } } int main() { int arr[]={1,2,4,3}; permutation(arr,4); return 0; }

运行结果（DEV-C）：

引用博客： https://www.cnblogs.com/darklights/p/5285598.html

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章