最小的K個數：用快排的思想去解相關問題

實作快速排序算法的關鍵在于先在數組中選擇一個數字，接下來把數組中的數字分為兩部分，比選擇的數字小的數字移到數組的左邊，比選擇的數字大的數字移到數組的右邊。

這個函數可以如下實作：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

<code>int</code> <code>Partition(</code><code>int</code> <code>data[], </code><code>int</code> <code>length, </code><code>int</code> <code>start, </code><code>int</code> <code>end)</code>

<code>{</code>

<code>    </code><code>if</code><code>(data == NULL || length &lt;= 0 || start &lt; 0 || end &gt;= length)</code>

<code>        </code><code>throw</code> <code>new</code> <code>std::exception(</code><code>"Invalid Parameters"</code><code>);</code>

<code>    </code> 

<code>    </code><code>int</code> <code>index = RandomInRange(start, end);</code>

<code>    </code><code>swap(&amp;data[index], &amp;data[end]);</code>

<code>    </code><code>int</code> <code>small = start - 1;</code>

<code>    </code><code>for</code><code>(index = start; index &lt; end; ++index)</code>

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

<code>        </code><code>if</code><code>(data[index] &lt; data[end])</code>

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

<code>            </code><code>++small;</code>

<code>            </code><code>if</code><code>(small != index)</code>

<code>                </code><code>swap(&amp;data[index], &amp;data[small]);</code>

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

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

<code>    </code><code>++small;</code>

<code>    </code><code>swap(&amp;data[small], &amp;data[end]);</code>

<code>    </code><code>return</code> <code>small;</code>

<code>}</code>

 函數RandomInRange用來生成一個在start和end之間的随機數，函數swap的作用是用來交換兩個數字。

如：輸入n個整數，找出其中最小的k個數。例如輸入4，5，1，6，2，7，3，8這8個數字，則最小的4個數字是1，2，3，4.

25

<code>void</code> <code>GetLeastNumbers(</code><code>int</code> <code>*input, </code><code>int</code> <code>n, </code><code>int</code> <code>*output, </code><code>int</code> <code>k)</code>

<code>    </code><code>if</code><code>(input == NULL || output == NULL || k &gt; n || n &lt;= 0 || k &lt;= 0)</code>

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

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

<code>    </code><code>int</code> <code>end = n - 1;</code>

<code>    </code><code>int</code> <code>index = Partition(input, n, start, end);</code>

<code>    </code><code>while</code><code>(index != k - 1)</code>

<code>        </code><code>if</code><code>(index &gt; k - 1)</code>

<code>            </code><code>end = index - 1;</code>

<code>            </code><code>index = Partition(input, n, start, end);</code>

<code>        </code><code>else</code>

<code>            </code><code>start = index + 1;</code>

<code>    </code><code>for</code><code>(</code><code>int</code> <code>i = 0; i &lt; k; ++i)</code>

<code>        </code><code>output[i] = input[i];</code>

 采用這種思路是有限制的。因為會修改輸入的數組，函數Partition會調整數組中數字的順序。

本文轉自夏雪冬日部落格園部落格，原文連結：http://www.cnblogs.com/heyonggang/p/3649048.html，如需轉載請自行聯系原作者