最小的K个数：用快排的思想去解相关问题

实现快速排序算法的关键在于先在数组中选择一个数字，接下来把数组中的数字分为两部分，比选择的数字小的数字移到数组的左边，比选择的数字大的数字移到数组的右边。

这个函数可以如下实现：

int Partition(int data[], int length, int start, int end)

{

    if(data == NULL || length <= 0 || start < 0 || end >= length)

        throw new std::exception("Invalid Parameters");

    int index = RandomInRange(start, end);

    swap(&data[index], &data[end]);

    int small = start - 1;

    for(index = start; index < end; ++index)

    {

        if(data[index] < data[end])

        {

            ++small;

            if(small != index)

                swap(&data[index], &data[small]);

        }

    }

    ++small;

    swap(&data[small], &data[end]);

    return small;

}

函数RandomInRange用来生成一个在start和end之间的随机数，函数swap的作用是用来交换两个数字。

如：输入n个整数，找出其中最小的k个数。例如输入4，5，1，6，2，7，3，8这8个数字，则最小的4个数字是1，2，3，4.

void GetLeastNumbers(int *input, int n, int *output, int k)

{

    if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)

        return;

    int start = 0;

    int end = n - 1;

    int index = Partition(input, n, start, end);

    while(index != k - 1)

    {

        if(index > k - 1)

        {

            end = index - 1;

            index = Partition(input, n, start, end);

        }

        else

        {

            start = index + 1;

            index = Partition(input, n, start, end);

        }

    }

    for(int i = 0; i < k; ++i)

        output[i] = input[i];

}

采用这种思路是有限制的。因为会修改输入的数组，函数Partition会调整数组中数字的顺序。

巴特西

最小的K个数：用快排的思想去解相关问题

最新文章

热门文章