学步园

昨天参加了华为赛门铁克科技有限公司的面试。分别经历了笔试、技术面试、电话面试、等待结果...

笔试题主要是考察C语言，下来之后，发现自己的基础还不是很牢固，做错了很多不应该错的题。提醒自己做题首先要认真读题，理解题意以后再动笔，如果基础牢固，就可以很容易地看出此题考察的是什么，还要注意平时的积累，注意一些看似不起眼的问题，永远要牢记“天下大事必作于细”。此篇文章中，主要总结一下其中的一道编程题——冒泡排序，题目不难，但有很多细节需要注意。
/*<br /> * 冒泡排序<br /> * 基本思想：对存放原始数据的数组，按从后往前的方向进行多次扫描，<br /> * 每次扫描称为“一趟”(pass)。当发现相邻两个数据的次序与排序要求<br /> * 的“递增次序”不符合时，即将这两个数据进行互换。这样，较小的数据<br /> * 就会逐单元向前移动，好像气泡向上浮起一样。<br /> * 请编写一个程序，在数组r[n]，n>=1中实现冒泡排序的<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>。<br /> * 函数原型：void bubllesort(int r[], int n);<br /> *<br /> * 此题关键：通过上述方法，这样一趟下来，最小的元素就会被交换到最前，<br /> * 然后下一趟就不用对第一个元素进行比较交换了，所以，每一趟交换的次数<br /> * 都比上一趟的次数少1。当然为了提高效率，可以在每一趟遍历时，设置<br /> * 一个标识来记录是否有交换发生，如果没有，则说明前面元素已经按升序排列，<br /> * 因此，排序完成，可以退出bubblesort函数。<br /> */<br /> #include <iostream><br /> using std::cin;<br /> using std::cout;<br /> using std::endl;<br /> #define ARRAYLEN(a) (sizeof(a)/sizeof(*a))<br /> #define SWAP(nx,ny) do {/<br /> nx^=ny;/<br /> ny^=nx;/<br /> nx^=ny;/<br /> } while(0)/<br /> void bubblesort(int r[], int n);<br /> int main()<br /> {<br /> //int iarr[]={4,3,2,5,1};<br /> int iarr[]={1,2,3,5,4};<br /> cout<<"before bubblesort, the iarr is:"<<endl;<br /> int i;<br /> for (i=0; i!=ARRAYLEN(iarr); ++i)<br /> {<br /> cout<<*(iarr+i)<<" ";<br /> }</p> <p> cout<<endl<<"after bubblesort, the iarr is:"<<endl;<br /> bubblesort(iarr,ARRAYLEN(iarr));<br /> for (i=0; i!=ARRAYLEN(iarr); ++i)<br /> {<br /> cout<<*(iarr+i)<<" ";<br /> }<br /> cout<<endl;<br /> return 0;<br /> }<br /> void bubblesort(int r[], int n)<br /> {<br /> for (int j=n-1; j!=0; --j)// the times that each pass should be compared, the maxtime is n-1<br /> {<br /> bool bSwap=false;// if in one pass there is no SWAP, the bubblesort will stop</p> <p> for (int i=n-1; i!=n-1-j; --i)// in each pass, compare adjacent element form front to end.<br /> {<br /> if (r[i-1]>r[i])<br /> {<br /> SWAP(r[i-1],r[i]);<br /> bSwap=true;<br /> }<br /> }<br /> if (!bSwap)<br /> {<br /> return;// the bubblesort stop<br /> }<br /> }<br /> }<br /> /*<br /> 输出：<br /> before bubblesort, the iarr is:<br /> 1 2 3 5 4<br /> after bubblesort, the iarr is:<br /> 1 2 3 4 5<br /> Press any key to continue<br /> */