面试题：一道冒泡算法笔试题的演进史

给定N个整数，请使用冒泡算法按照从大到小的顺序排序

1.可对N个整数的某一段(连续的M整数)排序

2.要求具有一定的可测试性

3.C#语言

——————--

思路：

1.冒泡算法

2.针对部分排序

3.可测试性

先上一段最简单的代码实现冒泡算法--这里错误的使用了选择排序,请参看改进版本的修正

int[] list= new int[] {1, 2, 3, 4, 5};
 for (int i=0;i<list.Length;i++)
 for (int j=i+1;j<list.Length;j++)
 {
 if (list[i]<list[j])
 {
 int tmp=list[i];
 list[i]=list[j];
 list[j]=tmp;
 }
 }
 for (int i=0;i<list.Length;i++)
 System.Console.Write("{0}\t",list[i]);
 System.Console.WriteLine("");

观看上述代码，有如下发现

1)行1，主要进行数据的初始化工作，准备数据

2)行2-11，主要实现冒泡排序算法

3)行12-14，主要是显示结果

4)行1-14，包含算法实现，调用，实现和使用糅合在一起

第一次改进：

1)数据初始化部分，其实属于调用部分，此时用的是数组，扩展性较差，这里改成List<int>，并将此步重构成函数

//初始化N个数据
void Init(List<int> list,int count)
{
 System.Random a=new Random();
 for (int i=0;i<count;i++)
 list.Add(a.Next(100));
}

这里初始化数据，主要是减少人工干预，自动产生测试数据，实际生产过程中，是需要按照实际情况，选取一些比较特殊的数据作为测试数据的.

2)冒泡排序算法实现过程部分，也可以重构成函数

//实现冒泡算法——这里错误的使用了选择排序
 void Bubble(List<int> list)
 {
 for (int i=0;i<list.Count;i++)
 for (int j=i+1;j<list.Count;j++)
 {
 if (list[i]<list[j])
 {
 int tmp=list[i];
 list[i]=list[j];
 list[j]=tmp;
 }
 }
 }

正确的冒泡排序为

void Bubble(List<int> list)
 {
 bool bFlag=false;
 for (int i=0;i<list.Count;i++)
 {
 bFlag=false;
 for(int j=list.Count-1-1 ;j>i-1;j--)
 {
 if (list[j]<list[j+1])
 {
 int tmp=list[j+1];
 list[j+1]=list[j];
 list[j]=tmp;
 bFlag=true;
 }
 }
 if (!bFlag) break;
 }
 }

将排序的代码，重构成函数，使得算法可以非常容易进行测试，只需要将精心设计的测试数据传给函数，就可以了

3)显示结果，也是重构成函数

//显示结果
void Print(List<int> list)
{
 for (int i=0;i<list.Count;i++)
 System.Console.Write("{0}\t",list[i]);
 System.Console.WriteLine("");
}

4)最终调用过程

public static void Main()
{
 List<int> list=new List<int>();
 //产生测试数据
 Init(list,8);
 //打印测试数据
 Print(list);
 //按照从大到小的顺序排序
 Bubble(list);
 //打印排序后的结果
 Print(list);
}

第二次改进：

第一次改进中，基本解决冒泡算法和可测试性的问题，但是还有一个重要问题没有解决，就是针对N个整数中的某一段连续M个数据进行排序，所以这次的改进主要集中在<冒泡排序算法实现>函数的改进

很明显，要实现这个功能，只需要，在 Bubble这个函数增加两个参数，标识出M的上下限，Bubble变成如下形式

1	<span style="color:#0000FF;">void</span> Bubble(List<<span style="color:#0000FF;">int</span>> list,<span style="color:#0000FF;">int</span> low,<span style="color:#0000FF;">int</span> high)

新的实现(注意，这里我的冒泡算法的实现是不对的，我用的是选择排序，经过一个园子里的兄弟提醒，我查过资料，发现的确用错了)

选择排序(Selection sort)

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

void Bubble(List<int> list,int low,int high)
{
 int iHigh= list.Count<high+1? list.Count : high+1 ;
 int iLow=low<0? 0 :low ;
 //System.Console.WriteLine("{0}\t{1}",iLow,iHigh);
 for (int i=iLow;i<iHigh;i++)
 for (int j=i+1;j<iHigh;j++)
 {
 if (list[i]<list[j])//比较不一定相邻
 {
 int tmp=list[i];
 list[i]=list[j];
 list[j]=tmp;
 }
 }
}

下面是更正后的冒泡排序代码

冒泡排序（BubbleSort）

依次比较相邻的两个数，将小数放在前面，大数放在后面。

static void Bubble(List<int> list,int low,int high)
 {
 int iHigh= list.Count<high+1? list.Count : high+1 ;
 int iLow=low<0? 0 :low ;

 bool bFlag=false;
 for (int i=iLow;i<iHigh;i++)
 {
 bFlag=false;
 for(int j=iHigh-1-1 ;j>i-1;j--)
 {
 if (list[j]<list[j+1])//比较相邻
 {
 int tmp=list[j+1];
 list[j+1]=list[j];
 list[j]=tmp;
 bFlag=true;
 }
 }
 if (!bFlag) break;
 }
 }

并提供一个重载函数

void Bubble(List<int> list) {             Bubble(list,0,list.Count-1); }

调用：

public static void Main()
{
 List<int> list=new List<int>();
 //产生测试数据
 Init(list,8);
 //打印测试数据
 Print(list);
 //按照从大到小的顺序排序，针对序号2-5的之间的数据
 Bubble(list,2,5);
 //打印排序后的结果
 Print(list);
}

至此，题目要求的目的全部达到，不过还是少了点什么，下面进行第三次改进

第三次改进：

第一次改进和第二次改进的结果，还是采用面向过程的方法，第三次改进侧重与面向对象的方法，就是封装

三个主要函数中都有List<int> list参数,这个是主要数据，我们用类来封装它，如下给出完整代码

public class BubbleSort
{
 List<int> _list;
 public BubbleSort()
 {
 _list=new List<int>();
 }
 public BubbleSort(List<int> list)
 {
 _list=list;
 }

 public void Sort()
 {
 Sort( _list,0,_list.Count-1);
 }
 public void Sort(int low,int high)
 {
 Sort( _list,low,high);
 }
 //实现冒泡算法--这里错误使用选择排序，请替换为第二次改进中的正确实现
 public void Sort(List<int> list,int low,int high)
 {
 //int iHigh= list.Count<low+count? list.Count : high ;
 int iHigh= list.Count<high+1? list.Count : high+1 ;
 int iLow=low<0? 0 :low ;
 //System.Console.WriteLine("{0}\t{1}",iLow,iHigh);
 for (int i=iLow;i<iHigh;i++)
 for (int j=i+1;j<iHigh;j++)
 {
 if (list[i]<list[j])
 {
 int tmp=list[i];
 list[i]=list[j];
 list[j]=tmp;
 }
 }
 }

 //初始化N个数据
 public void Init(int count)
 {
 _list.Clear();
 System.Random a=new Random();
 for (int i=0;i<count;i++)
 _list.Add(a.Next(100));
 }
 //显示结果
 public void Print(List<int> list)
 {
 Print(list,0,list.Count-1,true);
 }
 public void Print(List<int> list,int low,int high,bool IsNewLine)
 {
 int iHigh= list.Count<high+1? list.Count : high+1 ;
 int iLow=low<0? 0 :low ;

 for (int i=iLow;i<iHigh;i++)
 System.Console.Write("{0}\t",list[i]);
 if (IsNewLine)
 System.Console.WriteLine("");
 }
 public void Print(int low,int high,bool IsNewLine)
 {
 Print(_list,low,high,IsNewLine);
 }
 //将排序的M个数据用红色显示
 public void Print(int low,int high)
 {
 Print(0,low-1,false);
 System.Console.ForegroundColor=ConsoleColor.Red;
 Print(low,high,false);
 System.Console.ResetColor();
 Print(high+1,_list.Count,true);
 }

 public void Print()
 {
 Print(_list);
 }
 //for test
 public void Test()
 {
 //产生测试数据
 Init(10);
 //打印测试数据
 Print();
 //按照从大到小的顺序排序
 int[] iLowHigh=new int[]{4,7};
 Sort(iLowHigh[0],iLowHigh[1]);
 //Sort(-1,8);
 //Sort(0,18);
 //Sort(-1,18);
 //打印排序后的结果
 //Print();
 Print(iLowHigh[0],iLowHigh[1]);

 }
}

调用代码：

1	<span style="color:#008080;">1</span> BubbleSort bs=<span style="color:#0000FF;">new</span><span style="color:#000000;"> BubbleSort();<br /></span><span style="color:#008080;">2</span> bs.Test();

M	T	W	T	F	S	S
« Mar
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30