本文主要是介绍一道特殊的排序面试题(交换思想活学活用)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
如字符串abcdefg，现在需要按索引顺序1、4、2、0、5、3、6重排序，如对于、4、2、0、5、3、6，排序结果为becafdg
面试中很可能遇到这种非常突兀的问题，这需要基础概念牢固到能够随时运用的地步，本题就是一个锻炼
遇到这种题，步骤：在纸上画心里思考，尽力找出一种较为简单的规律，能够正确完成这样的变化要求！
算法题，一部分是考察数据结构掌握，另一部分就是看逻辑思维，随便过来一个问题，能不能分析出规律，能不能找到靠谱的方法，能不能转化为解决问题的代码！
像二叉树也好，链表数组栈队列也好，字符串也好，图也好，本身数据结构组成和原理就是那些，包括排序查找的常规套路就是那些，但是仅仅“理解了”、“背下来了”、“会了”，但运用很差，甚至代码还处于漏洞百出，那么，不仅并不足以通过高难度面试，而且更不足以完成更有挑战难度的工作
如本题，在纸上画个简单的例子，如：
自己假设abcde按1、2、4、0、3变化，如以第一个字符为“当前”字符，暂存其值a，不断的修改为新值，直到最后某个地方，它需要填充新值a时，结束，可不可以呢？在纸上试试
第1步：bbcde，当前为a，a要跳到1，替换a为原串第1个字符b，
第2步：bccde，当前为b，b要跳到2，替换b为原串第2个字符c
第3步：bcede，当前为c，c要跳到4，替换c为原串第4个字符e
第4步：bcedd，当前为e，e要跳到3，替换c为原串第3个字符d
第5步：bcead，当前为d，d要跳到0，替换c为原串第0个字符a，a就是第一个暂存的字符，直接替换掉结束，结果为：bcead，正确，时间复杂度O(N)
ok，纸上找到了正确的思路，然后就是思路转化为代码，用一个变量代表当前所在索引，再用一个变量代表下一步跳到哪里，用一个字符变量暂存第一个字符，
每跳一次前更新当前所在索引的新值，然后更新当前索引和下一步跳的索引
注意代码中main中大片部分是为了生成一个[0, N-1]范围内的不重复的随机序列(如[0, 7-1]范围内的“、4、2、0、5、3、6”)
代码：
#include <iostream>
#include <string>
#include <random>void sort_by_turn (const std::string &str, int *turn) {std::string res = str;if (!turn || str == "") {return;}size_t idx = 0, next = turn[idx], firstidx = idx;char flag = res[idx];do {res[idx] = res[next];idx = next;next = turn[idx];} while (firstidx != next);res[idx] = flag;std::cout << "result: " << res << std::endl;return;
}int main () {std::string str = "abcdefg";int raw[str.length()];int turn[str.length()];for (int i = 0; i < str.length(); i++) {raw[i] = i;}std::random_device rd;for (int i = 0; i < str.length(); i++) {int num;if (i < str.length() - 1) {int idx = rd() % (str.length() - 1 - i);int num = raw[idx + i];turn[i] = num;int t = raw[i];raw[i] = num;raw[i + idx] = t;} else {turn[i] = raw[i];}}for (int i = 0; i < str.length(); i++) {std::cout << turn[i] << "\t";}std::cout << std::endl;sort_by_turn(str, turn);return 0;
}这篇关于一道特殊的排序面试题(交换思想活学活用)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
