一道关于下标排序的金山笔试题

不念不忘少年蓝@ 2022-07-13 00:58 179阅读 0赞

有这样一道笔试题它是这样描述的：对一个数组按照给定下标排序，仅使用两两交换的方式，要求尽可能少的额外空间。栗子：原数组:A B C D E，假若它的排序下标为：3 0 1 4 2，那仫排序后为 D A B E C。

刚开始看到这道题，我想了一种最简单的实现方式就是重新开辟和数组pArr一样大的空间，通过遍历pPos将对应元素放入新开辟的数组空间中，最后再将新开辟数组中的内容放入数组pArr中，于是我很开心的写下了下面的代码:

void SwapSort(char *pArr,int *pPos,int n)
    {
    	assert(pArr);
    	assert(pPos);
    	int *tmp=new int[n];
    	for (int i=0;i<n;++i)
    	{
    		tmp[i]=pArr[pPos[i]];
    	}
    	for (int i=0;i<n;++i)
    	{
    		pArr[i]=tmp[i];
    	}
    	delete []tmp;
    }

转念一想原来这道题目的要求是尽可能少的额外空间，而我重新开辟空间它的时间复杂度和空间复杂度都是不满足要求的，后来通过高人指点我才对这道题有了一点点的想法.其实也没有什仫可卖关子的，其实这道题就是快排的玩坑法的一种变形。

![Center][]

大概的流程如上图所分析的，但是这是一个特殊的栗子因为tmp的数据是在最后才放入正确的位置的，如果tmp在未访问完数组的时候就填充到了正确的位置，那仫下一个可供选择的坑应该是哪个呢？我的想法是如果tmp在未遍历完pArr数组时就已经填入了正确的位置那仫就让flag的下一个位置做新的坑

栗子：原数组:A B C D E，假若它的排序下标为：3 4 1 0 2，那仫排序后为 D E B A C。

void SwapSort(char *pArr,int *pPos,int n)
    {
    	int i=0;
    	char tmp=0;
    	int count=0;    //记录排序过的数据个数
    	int flag=0;     //标记坑的位置
    	assert(pArr);
    	assert(pPos);
    	while (count < n)
    	{
    		if (i == pPos[i])
    		{
    			i++;
    			count++;
    		}
    		else
    		{
    			tmp=pArr[i];
    			flag=i;
    			while (1)
    			{
    				pArr[i]=pArr[pPos[i]];
    				i=pPos[i];
    				count++;
    				if(flag == pPos[i])    //如果此位置恰好要填tmp
    					break;
    			}
    			pArr[i]=tmp;
    			count++;
    			//如果tmp不是在最后一次才被填入正确的位置
    			//从当前坑的下一个位置做新的坑
    			i=flag+1;
    		}
    	}
    }

这种解法成功的解决了上述两种情况的问题，此时还未想到存在其他的情况~~~

[Center]: /images/20220713/fe08a452e40f46a597e04c3a6bee6b3b.png