• 好好学习,天天向上~
  • 欢迎欢迎~

C语言面试题详解第15节

c语言 lcc 129℃ 0评论

上一节介绍了算法的概念,讨论了算法与程序开销,以及程序工作效率之间的关系,并且在最后给出了一道面试题,要求使用C语言写出几种常用的数组排序算法,并比较各种方法的工作效率。限于篇幅,上一节主要讨论了插入排序法,本节我们再来看看其他几个常用的数组排序算法。

当然了,为了让文章不至于空洞,本节仍然以分析知名公司面试题的形式,讨论另外几种常用的数组排序算法。

冒泡排序法

提到数组排序,就不得不说一下冒泡排序法,这个排序法的名字比较有趣,属于非常基础的排序算法,常作为C语言初学者的编程练习题出现。不过,虽然比较基础,冒泡排序法也常常出现在各大公司的面试题中,例如,中国著名通信企业H公司有道面试题如下:

请用 C 语言写出一个冒泡排序程序,要求输入10个整数,输出排序结果。

将数组 list 中的每个元素看作是密度为 list[i] 且互不相溶的液体,按照物理学定律,密度小的液体总是会上浮到密度大的液体之上,这一过程看起来就像是气泡从水底漂浮到水表面一样,因此参考照顾原理实现的数组排序法称为“冒泡排序法”

现在细化“密度小的液体上浮到密度大的液体之上”这一过程,应该能发现,上浮中的液体总是和它旁边的液体相比较,若是发现对方密度比自己大,就继续上浮,一直上浮到密度比自己小的液体或者最上端为止。使用C语言模拟这一过程,其实就是比对两个数组元素大小,并在合适的时候交换相邻元素的值而已,相关C语言代码很简单:

if(list[j]>list[j+1]){
    tmp = list[j];
     list[j] = list[j+1];
     list[j+1] = tmp;
}

将上述过程应用到整个数组,就能实现一次完整的冒泡排序了,相关C语言代码如下,请看:

void bubbling_sort(int *list, int len)
{
     int i, j , tmp;
     for(i=0; i<len-1; i++){
         for(j=0; j<len-1-i; j++){
             if(list[j]>list[j+1]){
                 tmp = list[j];
                 list[j] = list[j+1];
                 list[j+1] = tmp;
             }
         }// for(j=0; j<len...
     }
}


在 main() 函数中初始化乱序排列的 10 个元素的数组 list,调用 bubbling_sort() 函数测试之,发现输出与预期一致:

# gcc t.c
# ./a.out 
0 1 2 3 4 5 6 7 8 9

冒泡排序可以纳入交换排序,基本思想都是两两比较待排序的数组元素,若发现元素次序相反就立即交换之,直到没有数组中反序排列的元素为止。

快速排序法

基于交换排序思想的另一个典型排序方法是快速排序法,从方法名字就能看出这是一种比较快速的方法,的确如此,快速排序法的效率常常比冒泡排序法高很多。

快速排序法不再比较数组的相邻元素了,而是从数组中找出一个元素值作为基准值,然后将数组中的其他元素与之比较,然后将数组中小于基准值的元素全部移到基准值的左边,大于基准值的元素则全部移到右边。例如,对数组 list 排序:

int list[10] = {4, 2, 1, 5, 9, 6, 3, 8, 0, 7};


假设选取 4 作为基准值,设定两个索引指针 i 和 j,i 从数组左往右移动(i=0; j++;),j 从数组右往左移动 (j=9; j–;),如上图,快速排序可如下进行:
* 移动 j,找出小于 4 的数值并记录其位置,显然是 0(list[8]);
* 移动 i,找出大于 4 的数值并记录其位置,显然为 5(list[3]);
* 交换 list[3] 和 list[8] 的数值,此时 list 的数值为 {4, 2, 1, 0, 9, 6, 3, 8, 5, 7}。


继续上述操作,发现需要交换 3(list[6]) 和 9(list[4]),得到:

{4, 2, 1, 0, 3, 6, 9, 8, 5, 7}


继续上述操作,移动 j 发现了小于 4 的数值 3(list[4]),再移动 i 发现 i 与 j 相遇了。此时应该交换基准值和6,也即交换 list[0] 和 list[4],得到:

{3, 2, 1, 0, 4, 6, 9, 8, 5, 7}


可以看出,操作停止后,虽然 list 中小于 4 的元素都在 4 左边,大于 4 的元素都在 4 右边,但是单看左右两边的子数组却仍然是乱序的:

{3, 2, 1, 0} 
{6, 9, 8, 5, 7}

不过,只要对左右两个子数组再进行一次上述操作,一直到整个数组排序完毕就可以了。显然,利用递归非常容易解决这类问题。

关于递归,前面两节已较为详细的讨论,感到陌生的朋友可以翻回去看看。

现在知道了快速排序的基本原理了,再来看个面试题,下面这道题出自美国某著名计算机嵌入式公司:

下面这段C语言代码是实现快速排序的函数,补全最后的代码。

 void improveqsort(int *list, int m, int n)
{
     int k,t,i,j;

     if(m<n){
         i = m;
         j = n+1;
         k = list[m];
         while(i<j){
             for(i=i+1; i<n; i++)
                 if(list[i]>=k) 
                     break;
             for(j=j-1; j>m; j--)
                 if(list[j]<=k)
                     break;
             if(i<j){
                 t = list[i];
                 list[i] = list[j];
                 list[j] = t;
             }   
         }   
         t = list[m];
         list[m] = list[j];
         list[j] = t;

         improveqsort( ,  , ); /* 补全参数 */
         improveqsort( ,  , ); /* 补全参数 */
     }
}


如果理解了上文对快速排序法的分析,要解这道题就不难了,请继续往下看。

显然,improveqsort() 函数是一个递归函数。观察 improveqsort() 函数的参数,推测它应该可以完成数组 list 第 m 个到第 n 个元素的排序。

下面为了分析方便,以上图中的行号为准。

第 7 行的 if(m<n) 限定了 improveqsort() 函数只对长度大于 1 的数组排序,若输入的数组长度小于 1,则函数就直接退出了,这其实就是前面两节中提到的“递归函数退出条件”。

第 10 行选定了数组的第 m 个元素作为基准值 k,第 8 到第 23 行就是在 i 遇到 j 之前的交换处理。当 i j 相遇后, improveqsort() 函数开始执行第 24 行到第 26 行,也即交换 j 和 m 处的值。

对照前文的分析,执行完第 26 行代码后,数组 list[m~n] 中小于 list[m] 的数值全部被移到 list[m] 左边,大于 list[m] 的数值则全部被移到 list[m] 右边了。此时需要对左右两个“子数组”进一步做快速排序,因此面试题的代码给出了两次 improveqsort() 函数的调用。那么传递给它们的参数应该是什么呢?

参考上图,再结合前面两节对递归函数的讨论,应该明白基准值的左子数组的索引范围应该是 list[m, j-1],基准值的右子数组索引范围应该是 list[i, n],因此补全上述C语言代码的答案应该是:

improveqsort(list, i, n);
improveqsort(list, m, j-1);

并且两句代码不分前后。现在在 main() 函数中调用补全后的 improveqsort() 测试:

int main()
{
     int list[10] = {9, 4, 2, 1, 5, 6, 3, 8, 0, 7};
     int i;

    improveqsort(list, 0, 9);
     for(i=0; i<10; i++)
         printf("%d ", list[i]);
     printf("\n");

     return 0;
}

编译上述C语言代码并执行,发现输出与预期一致:

# gcc t.c
# ./a.out 
0 1 2 3 4 5 6 7 8 9

其实,快速排序法是基于一种叫做“二分”的思想,类似的还有归并排序法,在我之前的文章里分析过,感兴趣的可以去看看。

小结

利用C语言解决问题的方法常常不止一种,这两节介绍的几种数组排序法就是一个例子。为什么要像孔乙己那样研究“茴”字有几种写法呢?这是因为计算机的运算速度并不是无限快,存储空间也不是无限大。冒泡排序法的确非常简单,但是它的执行效率却比较低,只适合处理较短的数组排序。

按平均时间复杂度可以将数组排序法分为以下几类:
* 平方阶排序:一般称为简单排序,典型例子有插入排序、冒泡排序;
* 线性对数阶排序:如快速排序,归并排序;
* 幂阶排序:如希尔排序;
* 线性阶排序:如桶、箱等以空间换时间的排序法。

应明白,不能简单认为某种排序算法一定比其他排序法好,可能在数学上某种算法的确很具效率,但是在实际中还要考虑计算机的实际运算速度以及存储空间,很有时间效率的算法可能是牺牲了大量存储空间换来的。应在不同条件下,选用不同的排序法,例如:
* 若数组长度很短(如小于50),可采用插入排序法
* 若数组基本有序,可采取冒泡排序
* 若数组较长,选择快速排序或者归并排序则比较合适


C语言面试题详解第15节 - 刘冲的博客(https://blog.popkx.com) 原创版权所有,转载请注明出处。
点赞 (1)分享 (0)
发表我的评论
取消评论
表情     9 + 7 = ? (必填)