本文主要是介绍算法篇：分治法求线性表中第k小的数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//第k小的数
/*算法思想：先进行一次快速排序，根据快速排序作为基准的那个数字排序后的位置，来确定我们要找的第k小的那个数
在当前位置的左边还是右边，如果在左边就往左递归，在右边同理。直到作为基准的那个数的位置的下标刚好是（k-1）
（默认下标从零开始），证明已经找到了第k小的数，返回它就ok。*/
#include "tou.h"
using namespace std;
int n = 0, k = 0;
int sort1(int a, int b,std::vector<int> & num1) {//快速排序，具体过程不再注释
int i, j, t, temp;
if (a > b) return 0;
temp = num1[a];
i = a; j = b;
while (i < j) {
while (num1[j] > temp&&i < j)
j--;
while (num1[i] < temp&&i < j)
i++;
if (i < j) {
swap(num1[i], num1[j]);
}
}
return i;//返回的是作为基准的那个数的下标
}
int fenzhi( int left,int right, std::vector<int> &num2) {
int pos = sort1(left, right,num2);//先进行一遍快速排序，并将返回的基准的下标赋值给pos
if (pos + 1 == k)//如果当前基准刚好是第k小的数，就返回
return num2[pos];
if (pos + 1 < k) {//如果当前基准的位置比k小，则向右递归着找
fenzhi(pos+1, right,num2);
}
if (pos + 1 > k) {//如果当前基准的位置比k大，则向左递归着找
fenzhi(left,pos-1,num2);
}
}
int main() {
cout << "输入n：";
cin >>n;
cout << "输入k： ";
cin >> k;
vector<int>num(n);
for (int i = 0; i < n; i++) {
cin >> num[i];
}
int res=fenzhi(0, n - 1,num);
cout << "第"<<k<<"小的数是:" << res << endl;
}
//总结：1.虽然用vector定义的是数组，但是传参数时必须是vector类型的参数，不能是普通数组int c[]，不然会报错类型不匹配。
//2.必须对vector数组初始化其大小，才能对数组赋值。
这篇关于算法篇：分治法求线性表中第k小的数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
