Algorithm
快速排序
这个是面试中常问的算法题,它主要考察到双指针,以及递归的知识.
算法介绍:
首先,选定左端的作为基准值,下标i和j分别指向最左端和最右端;
接着,j向右移动,直到找到比基准值小的值y(如果j当前所指向的值就满足则不需要移动);等j停下来后,i开始向右移动(前提是i和j不相等时),直到找到比基准值大的的x,然后x和y互换,接着去移动.
直到, i和j相等,这个时候,将基准值和i所对应的值进行交换.这样第一次排序已经做完了,这时会发现基准值左边的都是<=它的,基准值右边的都是>=它的.
再接着,对于新产生的两个数组也进行类似的操作,直到最后所有的顺序都已经排好了,就可以结束了.
设计思路:
首先,确定函数的返回值,形参:
这里将数组直接作为形参传进去比较适合,它会自动转换为指针类型,这样对形参的改变就是对这个数组的改变. 此外为了递归传递值比较方便,把数组的最左侧位置和最右侧位置作为参数.
于是,有如下的函数结构: void quick_sort(int a[], int left, int right);
再者,确定i和j的行为:一开始我错误地以为,i和j是以一位为单位交替移动的,后来发现是找到符合条件的值停下来后,另一个才能够移动.并且很重要一点,需要保证j先去移动.
最后,确定递归结束的条件,可以认为如果数组只有一位时就可以结束当前层的排序了,或者使用left和right来判断.
代码实现
//quick_sort #include<stdio.h> void quick_sort(int a[], int left, int right) { if(left == right) { return; } int i = left; int j = right; int bm = a[left]; while(i != j) { //j does first! while((i < j) && (a[j] >= bm)) { j--; } while((i < j) && (a[i] <= bm)) { i++; } if( i < j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } //when i==j, swap(bm, a[i]) if(left < i) { int tmp = a[left]; //这里不可错写成bm,这样就没有作用到数组上了. a[left] = a[i]; a[i] = tmp; quick_sort(a, left, i-1); //基准将数组分为两部分 } if(i < right) { quick_sort(a, i+1, right); } } int main() { int a[] = {6, 1, 9, 5, 6, 7, 8}; quick_sort(a, 0, sizeof(a)/sizeof(int)-1); for(int i = 0; i < sizeof(a)/sizeof(int); i++) { printf("%d ", a[i]); } return 0; }
后来看了网上的实现,感觉可以更整洁一些.就是在递归调用的时候,可以把对于left,right判断放在函数的开头,而在调用时就不用那么多判断了.贴下网上的实现:
参考文章:https://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html
#include <stdio.h>
int a[101],n;//定义全局变量，这两个变量需要在子函数中使用
void quicksort(int left,int right)
{
int i,j,t,temp;
if(left>right)
return;
temp=a[left]; //temp中存的就是基准数
i=left;
j=right;
while(i!=j)
{
//顺序很重要，要先从右边开始找
while(a[j]>=temp && i<j)
j--;
//再找右边的
while(a[i]<=temp && i<j)
i++;
//交换两个数在数组中的位置
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最终将基准数归位
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程
quicksort(i+1,right);//继续处理右边的 ，这里是一个递归的过程
}
int main()
{
int i,j,t;
//读入数据
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
quicksort(1,n); //快速排序调用
//输出排序后的结果
for(i=1;i<=n;i++)
printf("%d ",a[i]);
getchar();getchar();
return 0;
}
Review
How To Ask Questions The Smart Way(7/8)
How To Interpret Answers
There is an ancient and hallowed tradition: if you get a reply that reads “RTFM”, the person who sent it thinks you should have Read The Fucking Manual. He or she is almost certainly right. Go read it.
RTFM has a younger relative. If you get a reply that reads “STFW”, the person who sent it thinks you should have Searched The Fucking Web. He or she is almost certainly right. Go search it. (The milder version of this is when you are told “Google is your friend!”)
In Web forums, you may also be told to search the forum archives. In fact, someone may even be so kind as to provide a pointer to the previous thread where this problem was solved. But do not rely on this consideration; do your archive-searching before asking.
Often, the person telling you to do a search has the manual or the web page with the information you need open, and is looking at it as he or she types. These replies mean that the responder thinks (a) the information you need is easy to find, and (b) you will learn more if you seek out the information than if you have it spoon-fed to you.
You shouldn't be offended by this; by hacker standards, your respondent is showing you a rough kind of respect simply by not ignoring you. You should instead be thankful for this grandmotherly kindness.
If you don't understand the answer, do not immediately bounce back a demand for clarification. Use the same tools that you used to try and answer your original question (manuals, FAQs, the Web, skilled friends) to understand the answer. Then, if you still need to ask for clarification, exhibit what you have learned.
For example, suppose I tell you: “It sounds like you've got a stuck zentry; you'll need to clear it.” Then: here's a bad followup question: “What's a zentry?” Here's a good followup question: “OK, I read the man page and zentries are only mentioned under the -z and -p switches. Neither of them says anything about clearing zentries. Is it one of these or am I missing something here?”
Much of what looks like rudeness in hacker circles is not intended to give offense. Rather, it's the product of the direct, cut-through-the-bullshit communications style that is natural to people who are more concerned about solving problems than making others feel warm and fuzzy.
When you perceive rudeness, try to react calmly. If someone is really acting out, it is very likely a senior person on the list or newsgroup or forum will call him or her on it. If that doesn't happen and you lose your temper, it is likely that the person you lose it at was behaving within the hacker community's norms and you will be considered at fault. This will hurt your chances of getting the information or help you want.
On the other hand, you will occasionally run across rudeness and posturing that is quite gratuitous. The flip-side of the above is that it is acceptable form to slam real offenders quite hard, dissecting their misbehavior with a sharp verbal scalpel. Be very, very sure of your ground before you try this, however. The line between correcting an incivility and starting a pointless flamewar is thin enough that hackers themselves not infrequently blunder across it; if you are a newbie or an outsider, your chances of avoiding such a blunder are low. If you're after information rather than entertainment, it's better to keep your fingers off the keyboard than to risk this.
(Some people assert that many hackers have a mild form of autism or Asperger's Syndrome, and are actually missing some of the brain circuitry that lubricates “normal” human social interaction. This may or may not be true. If you are not a hacker yourself, it may help you cope with our eccentricities if you think of us as being brain-damaged. Go right ahead. We won't care; we like being whatever it is we are, and generally have a healthy skepticism about clinical labels.)
Jeff Bigler's observations about tact filters are also relevant and worth reading.
In the next section, we'll talk about a different issue; the kind of “rudeness” you'll see when you misbehave.
Odds are you'll screw up a few times on hacker community forums — in ways detailed in this article, or similar. And you'll be told exactly how you screwed up, possibly with colourful asides. In public.
When this happens, the worst thing you can do is whine about the experience, claim to have been verbally assaulted, demand apologies, scream, hold your breath, threaten lawsuits, complain to people's employers, leave the toilet seat up, etc. Instead, here's what you do:
Get over it. It's normal. In fact, it's healthy and appropriate.
Community standards do not maintain themselves: They're maintained by people actively applying them, visibly, in public. Don't whine that all criticism should have been conveyed via private e-mail: That's not how it works. Nor is it useful to insist you've been personally insulted when someone comments that one of your claims was wrong, or that his views differ. Those are loser attitudes.
There have been hacker forums where, out of some misguided sense of hyper-courtesy, participants are banned from posting any fault-finding with another's posts, and told “Don't say anything if you're unwilling to help the user.” The resulting departure of clueful participants to elsewhere causes them to descend into meaningless babble and become useless as technical forums.
Exaggeratedly “friendly” (in that fashion) or useful: Pick one.
Remember: When that hacker tells you that you've screwed up, and (no matter how gruffly) tells you not to do it again, he's acting out of concern for (1) you and (2) his community. It would be much easier for him to ignore you and filter you out of his life. If you can't manage to be grateful, at least have a little dignity, don't whine, and don't expect to be treated like a fragile doll just because you're a newcomer with a theatrically hypersensitive soul and delusions of entitlement.
Sometimes people will attack you personally, flame without an apparent reason, etc., even if you don't screw up (or have only screwed up in their imagination). In this case, complaining is the way to really screw up.
These flamers are either lamers who don't have a clue but believe themselves to be experts, or would-be psychologists testing whether you'll screw up. The other readers either ignore them, or find ways to deal with them on their own. The flamers' behavior creates problems for themselves, which don't have to concern you.
Don't let yourself be drawn into a flamewar, either. Most flames are best ignored — after you've checked whether they are really flames, not pointers to the ways in which you have screwed up, and not cleverly ciphered answers to your real question (this happens as well).
如何解读答案
RTFM和STFW：如何知道你已完全搞砸了
有一个古老而神圣的传统：如果你收到RTFM （Read The Fucking Manual）的回应，回答者认为你应该去读他妈的手册。当然，基本上他是对的，你应该去读一读。
RTFM 有一个年轻的亲戚。如果你收到STFW（Search The Fucking Web）的回应，回答者认为你应该到他妈的网上搜索过了。那人多半也是对的，去搜索一下吧。（更温和一点的说法是 Google是你的朋友！）
在论坛，你也可能被要求去爬爬论坛的旧文。事实上，有人甚至可能热心地为你提供以前解决此问题的讨论串。但不要依赖这种关照，提问前应该先搜索一下旧文。
通常，用这两句之一回答你的人会给你一份包含你需要内容的手册或者一个网址，而且他们打这些字的时候也正在读着。这些答复意味着回答者认为
- 你需要的信息非常容易获得；
- 你自己去搜索这些信息比灌给你能让你学到更多。
你不应该因此不爽；依照黑客的标准，他已经表示了对你一定程度的关注，而没有对你的要求视而不见。你应该对他祖母般的慈祥表示感谢。
如果还是搞不懂
如果你看不懂回应，别立刻要求对方解释。像你以前试着自己解决问题时那样（利用手册，FAQ，网络，身边的高手），先试着去搞懂他的回应。如果你真的需要对方解释，记得表现出你已经从中学到了点什么。
比方说，如果我回答你：看来似乎是 zentry 卡住了；你应该先清除它。，然后，这是一个**很糟的**后续问题回应：zentry是什么？ **好**的问法应该是这样：哦~~~我看过说明了但是只有 -z 和 -p 两个参数中提到了 zentries，而且还都没有清楚的解释如何清除它。你是指这两个中的哪一个吗？还是我看漏了什么？
处理无礼的回应
很多黑客圈子中看似无礼的行为并不是存心冒犯。相反，它是直接了当，一针见血式的交流风格，这种风格更注重解决问题，而不是使人感觉舒服而却模模糊糊。
如果你觉得被冒犯了，试着平静地反应。如果有人真的做了出格的事，邮件列表、新闻群组或论坛中的前辈多半会招呼他。如果这**没有发生而你却发火了，那么你发火对象的言语可能在黑客社区中看起来是正常的，而你**将被视为有错的一方，这将伤害到你获取信息或帮助的机会。
另一方面，你偶而真的会碰到无礼和无聊的言行。与上述相反，对真正的冒犯者狠狠地打击，用犀利的语言将其驳得体无完肤都是可以接受的。然而，在行事之前一定要非常非常的有根据。纠正无礼的言论与开始一场毫无意义的口水战仅一线之隔，黑客们自己莽撞地越线的情况并不鲜见。如果你是新手或外人，避开这种莽撞的机会并不高。如果你想得到的是信息而不是消磨时光，这时最好不要把手放在键盘上以免冒险。
（有些人断言很多黑客都有轻度的自闭症或亚斯伯格综合症，缺少用于润滑人类社会正常交往所需的神经。这既可能是真也可能是假的。如果你自己不是黑客，兴许你认为我们脑袋有问题还能帮助你应付我们的古怪行为。只管这么干好了，我们不在乎。我们**喜欢**我们现在这个样子，并且通常对病患标记都有站得住脚的怀疑。）
在下一节，我们会谈到另一个问题，当**你**行为不当时所会受到的冒犯。
如何避免扮演失败者
在黑客社区的论坛中有那么几次你可能会搞砸 -- 以本指南所描述到的或类似的方式。而你会在公开场合中被告知你是如何搞砸的，也许攻击的言语中还会带点夹七夹八的颜色。
这种事发生以后，你能做的最糟糕的事莫过于哀嚎你的遭遇、宣称被口头攻击、要求道歉、高声尖叫、憋闷气、威胁诉诸法律、向其雇主报怨、忘了关马桶盖等等。相反地，你该这么做：
熬过去，这很正常。事实上，它是有益健康且合理的。
社区的标准不会自行维持，它们是通过参与者积极而**公开地**执行来维持的。不要哭嚎所有的批评都应该通过私下的邮件传送，它不是这样运作的。当有人评论你的一个说法有误或者提出不同看法时，坚持声称受到个人攻击也毫无益处，这些都是失败者的态度。
也有其它的黑客论坛，受过高礼节要求的误导，禁止参与者张贴任何对别人帖子挑毛病的消息，并声称如果你不想帮助用户就闭嘴。 结果造成有想法的参与者纷纷离开，这么做只会使它们沦为毫无意义的嘮叨与无用的技术论坛。
夸张的讲法是：你要的是友善（以上述方式）还是有用？两个里面挑一个。
记着：当黑客说你搞砸了，并且（无论多么刺耳）告诉你别再这样做时，他正在为关心你和他的社区而行动。对他而言，不理你并将你从他的生活中滤掉更简单。如果你无法做到感谢，至少要表现地有点尊严，别大声哀嚎，也别因为自己是个有戏剧性超级敏感的灵魂和自以为有资格的新来者，就指望别人像对待脆弱的洋娃娃那样对你。
有时候，即使你没有搞砸（或者只是在他的想像中你搞砸了），有些人也会无缘无故地攻击你本人。在这种情况下，抱怨倒是**真的**会把问题搞砸。
这些来找麻烦的人要么是毫无办法但自以为是专家的不中用家伙，要么就是测试你是否真会搞砸的心理专家。其它读者要么不理睬，要么用自己的方式对付他们。这些来找麻烦的人在给他们自己找麻烦，这点你不用操心。
也别让自己卷入口水战，最好不要理睬大多数的口水战 -- 当然，是在你检验它们只是口水战，而并未指出你有搞砸的地方，且也没有巧妙地将问题真正的答案藏于其后（这也是有可能的）
Tips:
1.Qt中查看数组中所有值的方便做法: 输入（类型[长度]）*数组名，如（int[10]）*a.
2.可以在健身的时候去听极客时间的<10X程序员工作法>