快速排序及其应用 (二)
rray[j];
while (i < j && array[i] <= pivotKey)
{
i++;
}
array[j] = array[i];
}
array[i] = pivotKey;
return i;
}
/*
函数名： GetKLeastestNumbers
函数功能： 获取数组中最小的k个数字
函数参数： int *array 数组指针
int length 长度
int k 数组中最小的k个数字
*/
void GetKLeastestNumbers(int *array, int length, int k)
{
/* 判断参数的合法性 */
if (array == NULL || length < 0)
{
gInputInvalid = true;
return;
}
int middle = k;
int start = 0;
int end = length - 1;
while (start <= end)
{
int index = Partion(array, start, end);
if (index == middle)
{
break;
}
else if (index > middle)
{
end = index - 1;
}
else
{
start = index + 1;
}
}
}
void Test(const char *testName, int *array, int length, int k)
{
cout << testName << " : " << endl;
cout << "原数组：";
for (int i = 0; i < length; i++)
{
cout << array[i] << " ";
}
cout << endl;
GetKLeastestNumbers(array, length, k);
cout << "最小的k个数：";
for (int i = 0; i < k; i++)
{
cout << array[i] << " ";
}
cout << endl;
}
int main()
{
int array1[] = {4, 5, 1, 6, 2, 7, 3, 8};
Test("Test1", array1, sizeof(array1) / sizeof(int), 4);
int array2[] = {4, 5, 1, 6, 2, 7, 3, 8};
Test("Test2", array2, sizeof(array2) / sizeof(int), 8);
int array3[] = {4, 5, 1, 6, 2, 7, 3, 8};
Test("Test3", array3, sizeof(array3) / sizeof(int), 1);
return 0;
}