算法数据结构面试分享(六)数组排序问题(2)-计数排的序

数组排序问题(2)

昨天我们留了一道题目”给你一个整型数组,里面出现的数在(0 - 100)之间,能用最优化的方法帮我排序吗”。

1。确保我们理解了问题,并且尝试一个例子,确认理解无误。

这是一道排序算法题,我们学过很多排序的算法。不一样的是,它给定一个额外的条件,数组里的每个数字都在1 - 100之间。如果我们采取传统的排序算法,这个条件我们好像用不上。大家在面试的时候如果发现有条件没有用的上,基本上我们给出的算法可能不是最优的,或者我们没有解决它最原始的需求。举个例子{50岁,46岁,50岁,0,100,0}这个数组中,我们一眼就能看出0来有两个,46个有一个,50有两个,100有一个,我们再把他们拼接起来,我们就会得到{0,0,46岁、50、50100}。

2。想想你可以用什么方法解决问题,你会选择哪一种,为什么?

在上面的分析中我们能够总结出来,我们人工去排序的时候涉及到了两个重要的步骤。1:统计0 - 100之间每一个数出现的次数:2:从0 - 100的顺序按照他们出现的次数拼接出来,所以现在我们需要解决的问题如何方便计数了。申明一个数字,长度为101,假设50出现了一次,我们就把该数组中下标为50的位置加上1。全部计数完了,我们再扫描这个数字,将结果写回。
我们现在看一下它的复杂度,我们扫描了原数组一次,又扫描了计数数组一次,所以我们的复杂度是O (n)。这里大家也发现,我们这道题中体现了一个原则,用空间换时间。

3。解释你的算法和实现的方法

计数部分:扫描原数组,在索引数组中找到对应的位置h5> <代码> int [] indexArray=new int [100]; 　　foreach (var inputArray e) 　　{ 　　indexArray [e] + +; 　　} 　　

合并数组部分

 <代码> int数=0;
　　
　　for (int指数=0;指数& lt;indexArray.Length;指数+ +)
　　{
　　如果(indexArray(指数)比;0)//说明指数的数字出现过,我们需要拼接起来,出现了几次我们就加几个数
　　{
　　inputArray[数]=指数;
　　数+ +;
　　}
　　}

4。写代码的时候,记住,一定要解释你现在在干什么

 <代码>那我们就直接上代码啦。

 <代码>///& lt; summary>///给数组排序,该数组里的值在0 - 100之间///& lt;/summary>///& lt;参数name=笆椤弊４? lt;/param>
　　公共静态孔隙IndexSort (int[]数组)
　　{
　　int [] indexArray=new int [101];
　　
　　(var指数=0;指数& lt;indexArray.Length;指数+ +)
　　{
　　indexArray(指数)=0;
　　}
　　
　　foreach (var ein数组)
　　{
　　indexArray [e] + +;
　　}
　　
　　int数=0;
　　for (int指数=0;指数& lt;indexArray.Length;指数+ +)
　　{
　　如果(indexArray(指数)比;0)
　　{
　　for (int elementCount=0;elementCount & lt;indexArray(指数);elementCount + +)
　　{
　　数组(计数+ +)=指数;
　　}
　　}
　　}
　　}

大家有没有发现,上面的代码其实可以优化,会体现你的基本功哦。要装逼的话可以和面试官提出来的哦相关性的默认值是0,所以我们没有必要扫描它一遍给它赋个默认值了。所以这段代码是多余的:

 <代码> [csharp]视图复制
　　(var指数=0;指数& lt;indexArray.Length;指数+ +)
　　{
　　indexArray(指数)=0;
　　}

我们来测试一下这个方法:

 <代码> [csharp]视图复制
　　静态void Main (string [] args)
　　{
　　int[]数组=new int[]{0 0 100, 8日,7日,34个};
　　
　　IndexSort(数组);
　　
　　foreach (var ein数组)
　　{
　　控制台。写(e + " ");
　　}
　　}