接着昨天的写，里面的代码包含昨天的

1 #include 
     
        2 using namespace std;  3 #define N 50  4   5 //初始化数组  6 int a[] = {
   6, 2, 3, 4, 4, 3, 1, 2, 4, 4};  7 //int a[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};  8 //int a[] = {1, 2, 3, 4, 5, 6};  9 //int a[] = {6, 2, 3, 9, 4, 10, 1, 20, 40, 5}; 10 int n = 10; 11 int K = 4; 12  13 //快速排序，o(nlogn)，最应该想到的思路，排好序要多大数就输出多大数 14 /* 15     partition就是挖第一个洞，从后往前找，找到，挖起来，把前面的洞埋上，再从前往后找，找到，挖起来，把后面的洞埋上，直到最后，high=low了，把这个洞补上 16 */ 17 int partition(int* p, int low, int high) 18 { 19     int i; 20     int pivot; 21     //把第一个数拿出来，挖个洞 22     pivot = p[low]; 23     while (low < high) 24     { 25         //从后往前找，找到比pivot小的值 26         while (low < high && p[high] <= pivot) 27             high--; 28         //然后后面的数埋上前面的洞 29         //Note这里无须再加个if，因为即使相同了，那我再做一步也无妨，而且也无须把low指针往上移，因为，到时候我可以再判断一次，还是可以移动的 30         p[low] = p[high]; 31          32         //从前往后找，找到比pivot大的值，然后把前面的数埋上 33         while (low < high && p[low] >= pivot) 34             low++; 35         p[high] = p[low]; 36     } 37     //这里low和high已经相同了，所以也可以写成p[high]=pivot，这一步就是把洞埋上 38     p[low] = pivot; 39     return low; 40 } 41 /* 42     其实，两个可以写一起，但是，分开写更清楚 43     quickSort函数就是当low
      
        heap[(index - 1) / 2]) 74         { 75             int temp = heap[index]; 76             heap[index] = heap[(index - 1) / 2]; 77             heap[(index - 1) / 2] = temp; 78         } 79         //否则，说明已经调整好了，立即停止 80         else 81             break; 82         //若没有break出来，就要一直调整了，所以index要变动 83         index = (index - 1) / 2; 84     } 85 } 86 /* 87     input： 88         p数组要初始化数组，提供数据的 89         n表示该数组的长度，c就是麻烦，连长度都要传入 90         heapSize表示要维护的堆的大小，Note，一定要大于K哦 91 */ 92 void MaxHeapInit(int *p, int n, int heapSize) 93 { 94     int i, lastIndex; 95     lastIndex = 0; 96     for (i = 0; i < n; i++) 97     { 98         //依次插入 99         MaxHeapPush(lastIndex, p[i]);100         // 若比预定好的堆的大小小的话，最后一个value的值就要增加了101         if (lastIndex < heapSize)102             lastIndex++;103     }104 }105 /*106     input: lastIndex是要删除的value的位置（这里千万要注意，其实，跟前面的lastIndex有点不一样）107 */108 int MaxHeapPop(int lastIndex)109 {110     // 交换头尾value111     int temp, i;112     temp = heap[0];113     heap[0] = heap[lastIndex];114     heap[lastIndex] = temp;115     // 向下调整116     i = 0;117     int child = 2 * i + 1;118     while (child < lastIndex)119     {120         //若有右孩子节点，且右节点比左节点大，那要只需要比较右节点即可121         if (child + 1 < lastIndex && heap[2 * i + 2] > heap[2 * i + 1])122         {123             child = child + 1;124         }125         //若孩子节点比父节点大，两个节点交换126         if (heap[child] > heap[i])127         {128             temp = heap[child];129             heap[child] = heap[i];130             heap[i] = temp;131         }132         //否则说明已经有序，停止133         else134             break;135         // 变化孩子节点的index136         child = 2 * i + 1;137     }138     // 返回末尾value139     return heap[lastIndex];140 }141 142 //快排的优化，时间复杂度还是o(nlogn)，但是时间会大大减少143 /*144     由于只需要知道前K大数，没必要把所有的数都进行排序，而快排的思想就是找到一个值一分为二，所以，我们正好利用这一点145     有了之前写好的partition函数，实现起来就就是方便！！146 */147 void optQuickSort(int* p, int low, int high, int k)148 {149     int cur = partition(p, low, high);150     if (cur - low > k)151         optQuickSort(p, low, cur - 1, k);152     else if (cur - low < k - 1)153         optQuickSort(p, cur + 1, high, k - (cur - low + 1));154 }155 156 //部分排序，o(nK)157 /*158     这本应该最新想到的呀，若K=1，其实就只需找最大值就好了159     当K
       
         p[maxI])170                 maxI = j;171         }172         if (i != maxI)173         {174             temp = p[maxI];175             p[maxI] = p[i];176             p[i] = temp;177         }178     }179 }180 181 //时间换空间的办法，o(n)182 /*183     适用于整数，且范围不是很大的情况184     如果没有重复的话，还可以用bit数组185 */186 void findCount(int*p, int n, int k)187 {188     int count[N] = {
   0};189     int i, j, sumCount;190     //首先先对输入的元素进行计数191     for (i = 0; i < n; i++)192     {193         count[p[i]] += 1;194     }195     sumCount = 0;196     for (i = N - 1; i > 0; i--)197     {198         sumCount += count[i];199         //若累计最大的数大于k了，就把多余的部分去掉，把最大的k个数输出200         if (sumCount > k)201         {202             for (j = 0; j < count[i] - (sumCount - k); j++)203                 cout<
        <<" ";204             break;205         }206         //若累计的没有到达K，那就直接输出啦207         else208         {209             for (j = 0; j < count[i]; j++)210                 cout<<<" ";211         }212     }213 }214 215 int main()216 {217     int i, j;218     for (i = 0; i < n; i++)219         cout<
          
           <<" ";220 cout<