这是一道很经典的题目，有太多方法了，今天写了两种方法，分别是快排和堆排序
#include <iostream>
using namespace std;
#define N 25 //初始化数组
//int a[] = {6, 2, 3, 9, 4, 3, 1, 2, 4, 4};
//int a[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
int a[] = {, , , , , };
int n = ;
int K = ; //快速排序，o(nlogn)，最应该想到的思路，排好序要多大数就输出多大数
/*
partition就是挖第一个洞，从后往前找，找到，挖起来，把前面的洞埋上，再从前往后找，找到，挖起来，把后面的洞埋上，直到最后，high=low了，把这个洞补上
*/
int partition(int* p, int low, int high)
{
int i;
int pivot;
//把第一个数拿出来，挖个洞
pivot = p[low];
while (low < high)
{
//从后往前找，找到比pivot小的值
while (low < high && p[high] >= pivot)
high--;
//然后后面的数埋上前面的洞
//Note这里无须再加个if，因为即使相同了，那我再做一步也无妨，而且也无须把low指针往上移，因为，到时候我可以再判断一次，还是可以移动的
p[low] = p[high]; //从前往后找，找到比pivot大的值，然后把前面的数埋上
while (low < high && p[low] <= pivot)
low++;
p[high] = p[low];
}
//这里low和high已经相同了，所以也可以写成p[high]=pivot，这一步就是把洞埋上
p[low] = pivot;
return low;
}
/*
其实，两个可以写一起，但是，分开写更清楚
quickSort函数就是当low<high时，进行一次partition，然后再对分开的两块进行quickSort
*/
void quickSort(int* p, int low, int high)
{
if(low < high)
{
int breakpoint = partition(p, low, high);
quickSort(p, low, breakpoint - );
quickSort(p, breakpoint + , high);
}
} //堆排序, o(nlogk)，考虑到只需取K大的数，那就无须对n个数都排序，只需记录下k个即可
int heap[N];
/*
//这里有点疑问哦，考虑到heap数组可能比较大，所以想定义成全局变量，可是这样就不必传递参数勒，定义成局部变量，参数又太多
目前定义成全局变量
input: lastIndex指heap数组要插入的value的位置（是要插入的位置哦）; value指要插入的数字
function: heap数组是从index=0开始储存的，就是把value储存heap数组内，并进行相应的调整，符合最大堆的性质
*/
void MaxHeapPush(int lastIndex, int value)
{
//把value放在堆的末尾
heap[lastIndex] = value;
//记录下末尾的index
int index = lastIndex;
// 不断向上调整
while (index)
{
//若比上面的大，就交换
if (heap[index] > heap[(index - ) / ])
{
int temp = heap[index];
heap[index] = heap[(index - ) / ];
heap[(index - ) / ] = temp;
}
//否则，说明已经调整好了，立即停止
else
break;
//若没有break出来，就要一直调整了，所以index要变动
index = (index - ) / ;
}
}
/*
input：
p数组要初始化数组，提供数据的
n表示该数组的长度，c就是麻烦，连长度都要传入
heapSize表示要维护的堆的大小，Note，一定要大于K哦
*/
void MaxHeapInit(int *p, int n, int heapSize)
{
int i, lastIndex;
lastIndex = ;
for (i = ; i < n; i++)
{
//依次插入
MaxHeapPush(lastIndex, p[i]);
// 若比预定好的堆的大小小的话，最后一个value的值就要增加了
if (lastIndex < heapSize)
lastIndex++;
}
} /*
input: lastIndex是要删除的value的位置（这里千万要注意，其实，跟前面的lastIndex有点不一样）
*/
int MaxHeapPop(int lastIndex)
{
// 交换头尾value
int temp, i;
temp = heap[];
heap[] = heap[lastIndex];
heap[lastIndex] = temp;
// 向下调整
i = ;
int child = * i + ;
while (child < lastIndex)
{
//若有右孩子节点，且右节点比左节点大，那要只需要比较右节点即可
if (child + < lastIndex && heap[ * i + ] > heap[ * i + ])
{
child = child + ;
}
//若孩子节点比父节点大，两个节点交换
if (heap[child] > heap[i])
{
temp = heap[child];
heap[child] = heap[i];
heap[i] = temp;
}
//否则说明已经有序，停止
else
break;
// 变化孩子节点的index
child = * i + ;
}
// 返回末尾value
return heap[lastIndex];
} int main()
{
int i, j;
for (i = ; i < n; i++)
cout<<a[i]<<" ";
cout<<endl;
/*
//快排，若取前K大的数，只需从末尾到前输出K个数即可
quickSort(a, 0, n - 1);
for (i = 0; i < n; i++)
cout<<a[i]<<" ";
cout<<endl;
*/ //注意这里之所以乘以2，是因为只维护K个数字的堆，不能得到前K个大的数！！
MaxHeapInit(a, n, K * - );
for (i = ; i < n; i++)
cout<<heap[i]<<" ";
cout<<endl; // 输出，这里的lastIndex是变化的哦，因为之前维护的2 * K - 1的堆，所以这里也应该是2 * K - 1
for (i = ; i < K; i++)
cout<<MaxHeapPop( * K - - i)<<" ";
cout<<endl; system("pause");
return ;
}