最小的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，如需转载请自行联系原作者