桶排序

桶排序思想：

假如數組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，如需轉載請自行聯系原作者