- 使用快速排序的思想进行实现
每次排序,会确定一个基准点,从大到小排序的话,基准点左边的数,都比基准点大,基准点右边的数,都比基准点小. 第一次确定基准点后,与 K 进行比较,如果k-1 == 基准点的位置(k减一是因为数组下标是从0开始的,第一大,就是 0 位,第二大,就是1 位), 那么,基准点的数字就是第K大的数, 否则, 如果k - 1 大于基准点,说明第K大的数,在右边的区间中, 否则说明在左边的区间中,然后继续递归,直到找到基准点.
//计算基准点
int calculate(int *q,int low,int high) {
int tmp = q[low];
while (low < high) {
while (low < high && q[high] <= tmp) {
high--;
}
q[low] = q[high];
while (low < high && q[low] > tmp) {
low++;
}
q[high] = q[low];
}
q[low] = tmp;
return low;
}
int find(int *q,int k ,int low,int high){
int position = calculate(q,low,high);
if( position == k - 1){
return position;
}
if(position > k - 1){
return find(q,k,low,position - 1);
}else {
return find(q,k,position + 1,high);
}
}
//快速排序
void sort(int *q,int low,int high){
if(low < high){
int position = calculate(q,low,high);
sort(q,low,position-1);
sort(q,position+1,high);
}
}
int kthlargest(){
//数组
int quen[] = {4,3,6,1,5,3,7,9};
//数组长度
int len = sizeof(quen)/sizeof(int);
printf("排序前:\n ");
for(int i = 0;i < len ;i++){
printf(" %d ",quen[i]);
}
printf("\n");
int k = 4;
int position = find(quen,k,0,len - 1);
printf("---第%d大的数是--%d---\n",k,quen[position]);
printf("排序后:\n");
sort(quen,0,len-1);
for(int i = 0;i < len ;i++){
printf("%d ",quen[i]);
}
printf("\n");
}
