桶排序

桶排序思想：

假如数组bucketArr[9] = {0};初始化为0；如下：

下标：0      1         2       3        4        5        6         7       8        9

假如要排序的数为：3 2 2 8 9 9，最大的数不能超过定义桶数组的最大下标。

则将出现的数放到桶中，相应下标的桶加1。则结果为：

2

1

现在只要输出：下标为2则输出两个2，下标为3这输出1个三，依次类推，0不输出。

例子：代码实现如下：

<code>#include &lt;stdio.h&gt;</code>

<code>#include &lt;stdlib.h&gt;</code>

<code>int</code> <code>main()</code>

<code>{</code>

<code>    </code><code>int</code> <code>i = 0;</code>

<code>    </code><code>int</code> <code>j = 0;</code>

<code>    </code><code>int</code> <code>temp = 0;</code>

<code>    </code><code>/*假如是5个数排序，且数都小于10。举例说明桶排序*/</code>

<code>    </code><code>int</code> <code>bucketArr[11] = {0};</code><code>//11个桶</code>

<code>    </code><code>printf</code><code>(</code><code>"请输入要输入的5个数，小于等于10："</code><code>);</code>

<code>    </code><code>for</code><code>(;i&lt;5;i++)</code>

<code>    </code><code>{</code>

<code>        </code><code>scanf</code><code>(</code><code>"%d"</code><code>,&amp;temp);</code>

<code>        </code><code>bucketArr[temp]++;</code>

<code>    </code><code>}</code>

<code>    </code><code>//从小到大，从大到小则i = 10即可</code>

<code>    </code><code>for</code><code>(i = 0;i &lt; 11;i++)</code><code>//桶数</code>

<code>        </code><code>for</code><code>(j = 0;j &lt; bucketArr[i];j++)</code>

<code>        </code><code>{</code>

<code>            </code><code>printf</code><code>(</code><code>"%d"</code><code>,i);</code>

<code>        </code><code>}</code>

<code>    </code><code>printf</code><code>(</code><code>"\n"</code><code>);</code>

<code>    </code><code>system</code><code>(</code><code>"pause"</code><code>);</code>

<code>    </code><code>return</code> <code>0;</code>

<code>}</code>

桶排序的时间复杂度为O（m+n）。桶数m+输入个数n。

本文转自 8yi少女的夢 51CTO博客，原文链接：http://blog.51cto.com/zhaoxiaohu/1758177，如需转载请自行联系原作者