求解一道腾讯笔试题(帮帮忙)

本文主要是介绍求解一道腾讯笔试题(帮帮忙)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大家帮帮忙。

题：关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要按照关键码值递增的次序进行排序，若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是FHCDQAMQRSYX。

题目答案应该是正确的(好多年前的考研题).但是我有个疑问，感觉题目是不是有多个答案。因为排序算法有多个实现版本。多个版本导致第一趟的结果不同，但最终结果是一样的。

1. 首先说答案的版本，答案中的版本是wikipedia上的simple version，流程如下

Q H C Y Q A M S R D F X

F Q C Y Q A M S R D H X

F A Q Y Q C M S R D H X

.......之后的就不写了，太多了。

简单就是将Q一步一步向右移。

2. 我做的答案：F H C Q A M D Q R Y S X 。我做出这个答案是因为看的是算法导论上的快速排序版本。

伪代码：选取关键数值A[r],p=1

1. PARTITION(A, p, r)  
2. 1  x ← A[r]  
3. 2  i ← p - 1  
4. 3  for j ← p to r - 1  
5. 4       do if A[j] ≤ x  
6. 5             then i ← i + 1  
7. 6                  exchange A[i] ↔ A[j]  
8. 7  exchange A[i + 1] ↔ A[r]  
9. 8  return i + 1  

注意到两个版本的差别就是，算法导论中是最后才交换关键数值A[r]的，而wikipedia上是一直在移动关键数值。

所以我想问下大家，是不是这道题真有多个答案，还是我自己思路错了。

 

这篇关于求解一道腾讯笔试题(帮帮忙)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---