待字闺中之巧妙排序分析：[通俗易懂]
待字闺中之巧妙排序分析：[通俗易懂]
大家好，又见面了，我是全栈君。
题目来源。待字闺中。原创@陈利人
排序仅仅有1。2，3三个元素的数组。不能统计1，2。3的个数。
分析：这个题目，虽然也是排序，但却不能使用高速排序的方法。仅仅有三个元素，假设时间复杂度仍旧是O(nlogn)。显然不是最好的。那就行使用线性的排序算法，比如计数排序。但是题目中要求，不可以对1，2，3进行统计个数。那该怎样处理呢？请大家看以下的方法，我们首先通过样例来说明：
2 | 1 | 1 | 3 | 3 | 2 |
|---|---|---|---|---|---|
p1 | p2 | p3 |
如果，我们有三个指针：p1、p2、p3.p1从左側開始，指向第一个非1的数字。p3从右側開始，指向第一个非3的数字。
p2从p1開始遍历。如果是2，p2继续遍历，直到p2遇到1或者3：
假设遇到1，则和p1进行交换，然后p1向右，指向第一个非1的数字
假设遇到3，则和p3进行交换。然后p3向左。指向第一个非3的数字
1 | 2 | 1 | 3 | 3 | 2 |
|---|---|---|---|---|---|
p1,p2 | p3 | ||||
交换之后，p2继续从p1開始。假设是2继续遍历。假设是1或者3，反复上面的步骤，所得例如以下：
1 | 1 | 2 | 3 | 3 | 2 |
|---|---|---|---|---|---|
p1，p2 | p3 |
依据上面的方法继续下去
1 | 1 | 2 | 2 | 3 | 3 |
|---|---|---|---|---|---|
p1 | p3 | p2 | |||
p2在p3右側。算法结束。详细代码例如以下：
void SortWithThreePointer(vector<int>& data)//用三个指针进行排序。缺点。仅仅能对三个数有效{ int length = data.size(); if(length <= 0)return; int begin = 0,cur = 0,end = length -1; while(cur <= end ) { if(data[cur] == 1) { swap(data[begin],data[cur]); begin ++; cur ++; } else if(data[cur] == 3) { swap(data[cur],data[end]); end --; } else cur ++; }}基于快排划分的思路
上面的思路。是针对三个数的，假设有很多其它的数，怎么处理呢？比方，4个，5个等等。以下依据高速的排序的启示，介绍一种算法，虽然在处理三个数的时候。比較次数会多些，但，具有非常好的通用性。
思路来自快排的划分部分。快排的划分部分：给定pivot，然后将数据划分为<=pivot和>pivot两部分。这样。三个数字时，须要两次划分：
第一次，用1作为pivot,划分1到最左边。
第二次，用2作为pivot。划分2到左边，则得到总体的排序。
详细代码例如以下：
int partition(vector<int>& data,int provit,int begin,int end)
{
int i;
for(i = begin;i <= end;i++)
{
if(data[i] == provit)
{
swap(data[begin],data[i]);//找到给定的provit，交换到第一个位置
break;
}
}
if(i == end+1)return begin-1;
while(begin < end)
{
while(begin < end && data[end] > provit ) end --;
if(begin < end) data[begin++] = data[end];
while(begin < end && data[begin] <= provit) begin++;
if(begin < end)data[end--] = data[begin];
}
data[begin] = provit;
return begin;
}
//numbers是已经排好序的可能会出现的数字，如1。2。3，对每个数字进行partition
void SortWithPartition(vector<int>& data,vector<int>& number)
{
int i,provit,dataLen = data.size(),numberLen = number.size();
if(dataLen <= 0 || numberLen <= 0)return;
int begin = 0,end = dataLen-1;
for(i=0;i<numberLen && begin < end;i++)
{
provit = partition(data,number[i],begin,end);
begin = provit + 1;
}
}最巧妙的思路
我们将1，2，3。替换为互质的2，3，5，得到例如以下：
2 | 1 | 1 | 3 | 3 | 2 |
|---|---|---|---|---|---|
3 | 2 | 2 | 5 | 5 | 3 |
之后，乘起来得到的900.这900里，除以2。有多少个2。就有多少个1；然后除以3，有多少个3，就有多少个3相应的2；然后除以5。有多少个5，就有多少个5相应的3。
这是怎样保证的呢？由于2，3，5是互质的。
例如以下：
被除数 | 除数 | 商 | 余数 | 排序结果 |
|---|---|---|---|---|
900 | 2 | 450 | 0 | 1 |
450 | 2 | 225 | 0 | 1 |
225 | 2 | 112 | 1 | 2尝试结束，尝试3 |
225 | 3 | 75 | 0 | 2 |
75 | 3 | 25 | 0 | 2 |
25 | 3 | 8 | 1 | 3尝试结束，尝试5 |
25 | 5 | 5 | 0 | 3 |
5 | 5 | 1 | 0 | 3 |
1 | 5 | 1 | 1 | 所有结束 |
终于结果为112233.上面的这样的思路。实际上是计数的一种变种。没有直接的技术。那自然就是能够的。
详细代码例如以下：
//numbers是已经排好序的可能会出现的数字。如1。2，3。把每个数映射为素数，该方法的缺陷是可能会出现溢出void SortWithPrimeNum(vector<int>& data,vector<int>& number){ int prime[26] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};//100以内的素数 int dataLen = data.size(),numberLen = number.size(); if(dataLen <= 0 || numberLen <= 0 || numberLen >= 25)return; map<int,int> hashMap; int i,j=0,product = 1; for(i=0;i<numberLen;i++) { hashMap[number[i]] = prime[i];//把可能出现的数字映射为素数 } for(i=0;i<dataLen;i++) { product *= hashMap[data[i]]; } for(i=0;i<numberLen && product != 0;i++) { cout << hashMap[number[i]] << endl; while(product % hashMap[number[i]] == 0) { data[j++] = number[i]; product = product / hashMap[number[i]]; } }}发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/115925.html原文链接：https://javaforall.cn
腾讯云开发者
