排序和时间复杂度—软件测试工程师面试秘籍(5)

发表于:2014-11-13 13:30

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:G.li    来源:51Testing软件测试网原创

  2.1.5  排序[3]
  各种排序算法以及它们的时间复杂度。
  排序算法有很多,包括插入排序、冒泡排序、堆排序、归并排序、选择排序、计数排序、基数排序、桶排序、快速排序等。插入排序、堆排序、选择排序、归并排序、快速排序和冒泡排序都是比较排序,堆排序属于选择排序,插入排序、希尔排序属于插入排序。下面复习几种常考的排序算法。
  1.冒泡排序(BubbleSort)
  最简单的一个冒泡排序算法如下。
public void bubbleSort()
{
int out, in;
for(out=nElems-1; out>0; out--)   // outer loop (backward)
for(in=0; in<out; in++)        // inner loop (forward)
if( a[in] > a[in+1] )       // out of order?
swap(in, in+1);          // swap them
}  // end bubbleSort()
  上面冒泡排序算法的效率为:O(N2)
  2.选择排序(SelectSort)
public void selectionSort()
{
int out, in, min;
for(out=0; out<nElems-1; out++)   // outer loop
{
min = out;                     // minimum
for(in=out+1; in<nElems; in++) // inner loop
if(a[in] < a[min] )         // if min greater,
min = in;               // we have a new min
swap(out, min);                // swap them
}  // end for(out)
}  // end selectionSort()
  上述排序算法的效率为:O(N2)
  3.插入排序(InsertSort)
  在插入排序中,一组数据在某个时刻是局部有序的,而在冒泡和选择排序中是完全有序的。
public void insertionSort()
{
int in, out;
for(out=1; out<nElems; out++)     // out is dividing line
{
long temp = a[out];            // remove marked item
in = out;                      // start shifts at out
while(in>0 && a[in-1] >= temp) // until one is smaller,
{
a[in] = a[in-1];            // shift item to right
--in;                       // go left one position
}
a[in] = temp;                  // insert marked item
}  // end for
}  // end insertionSort()
  上述排序算法的效率比冒泡排序快一倍,比选择排序略快,但也是O(N2)。如果数据基本有序,几乎需要O(N)的时间。
本文选自《软件测试工程师面试秘籍》,本站经作者的授权。
版权声明:51Testing软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。
21/212>
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号