一.堆排序
我们知道冒泡算法的时间复杂度是O（N^2），在数据量很多的时候，N^2是个很可怕的数字，二分算法的时间复杂度是O(logn)，但是二分算法有限制条件，实用性并不高，那怎样才能高效实用的排序呢？
堆排序就能很好解决上述问题，堆排序的时间复杂度是O(logn)，也没啥限制条件，可以实现高效排序。
这里要注意，排升序要建大堆，排降序要建小堆;
1.假设排升序，所以建大堆；
2.堆建好后，定义一个 end 变量，令其 =n-1（数组最后一个元素的下标是n-1） ；
3.堆建好后，数组第一个元素就是最大的，将其与最后一个数据交换，然后这个数据就不需要动了，为了保持它是个大堆，让它的前 end-1 个元素向下调整，然后end--，当 end<=0 时就结束循环。
堆排序不需要手搓个堆，只需要用到向下调整这个函数，所以使用堆排序时，只需写个向下调整就行了。
1. void Swap(int* p1, int* p2) 2. { 3. int tmp = *p1; 4. *p1 = *p2; 5. *p2 = tmp; 6. } 7. void AdjustDown(int* arr, int parent, int n) 8. { 9. assert(arr); 10. int child = 2 * parent + 1; 11. while (child < n) 12. { 13. if ((child + 1) < n&& arr[child + 1] > arr[child]) 14. { 15. child++; 16. } 17. 18. if (arr[child] > arr[parent]) 19. { 20. Swap(&arr[child], &arr[parent]); 21. parent = child; 22. child = 2 * parent + 1; 23. } 24. else 25. break; 26. } 27. } 28. void Heapsort(int* arr, int n) 29. { 30. assert(arr); 31. int i = 0; 32. for (i = (n - 2) / 2; i >= 0; i--) //建堆 33. { 34. AdjustDown(arr, i, n); 35. } 36. int end = n - 1; 37. while (end) 38. { 39. Swap(&arr[0], &arr[end]); 40. 41. AdjustDown(arr, 0, end); 42. 43. end--; 44. } 45. for (i = 0; i < n; i++) 46. { 47. printf("%d ", arr[i]); 48. } 49. printf("\n"); 50. }
二.topk问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
基本思路如下：
1. 用数据集合中前K个元素来建堆，注意：
前k个最大的元素，则建小堆；
前k个最小的元素，则建大堆；
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素；
3.将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
我们可以从文件中读取数据，这样的实用性更高些；
假设找的是最大的前k个数据，所以建小堆；
具体：
1.创建一个k个元素的数组，模拟建堆，从文件中读取k个数据存入数组中；
2.从文件中取数据与数组的第一个元素比较，也就是堆顶的数据，因为是小堆，如果该数据比堆顶数据大，则将值赋给堆顶，成为新的堆顶，不用担心会出什么问题，因为是小堆，所以那些大的数据会往下沉，如果不大于堆顶的数据，则继续从文件中取数据出来比较；
3.当读取文件结束时就结束循环。
如果对文件操作不太熟悉的话，可参考->文件的基础操作
如要想检验你写的代码是否能解决topk问题时，可以在数据创建完成后，手动修改文件中的k个数据，如果是找最大的k个数据，那么只需要修改k个数据，且每个都大于原来文件的最大值，这样在测试代码时，输出的就是你修改的k个数据。
1. void Createdata(const char file,int n) //创建数据 2. { 3. int i = 0; 4. int x = 0; 5. FILE* fin = fopen("file", "w"); //打开文件 6. if (fin == NULL) 7. { 8. perror("fopen fail"); 9. exit(-1); 10. } 11. for (i = 0; i < n; i++) 12. { 13. x = rand() % 100 + 1; //利用随机数生成函数，创建k个范围在1~100之间的数据 14. fprintf(fin, "%d\n", x); //将数据写入文件中 15. } 16. fclose(fin); //关闭文件 17. fin = NULL; 18. } 19. 20. void topk(const char file, int k) 21. { 22. FILE* fout = fopen("file", "r"); 23. if (fout == NULL) 24. { 25. perror("fopen fail"); 26. exit(-1); 27. } 28. HPdatatype* arr = (HPdatatype*)malloc(sizeof(HPdatatype) * k); 29. if (arr == NULL) 30. { 31. perror("malloc fail"); 32. exit(-1); 33. } 34. int i = 0; 35. for (i = 0; i < k; i++) 36. { 37. fscanf(fout, "%d", &arr[i]); //从文件中写入k个数据到数组中，模拟堆的创建 38. } 39. 40. int val = 0, ret = 0; 41. ret = fscanf(fout, "%d", &val); //从文件中取数据 42. while (ret != EOF) 43. { 44. if (val > arr[0]) //将取出的数据与堆顶数据比较，若大于，则其成为新的堆顶 45. { 46. arr[0] = val; 47. AdjustDown(arr, 0, k); //向下调整，保持小堆或是大堆 48. } 49. 50. ret = fscanf(fout, "%d", &val); //从文件中取数据 51. } 52. free(arr); 53. fclose(fout); 54. arr = NULL; 55. fout = NULL; 56. 57. } 58. 59. int main() 60. { 61. srand((unsigned int)time(NULL)); 62. const char file = "data.txt"; 63. int n = 1000; 64. int k = 10; 65. //Createdata(file,n); 66. topk(file, k); 67. return 0; 68. }
🐬🤖本篇文章到此就结束了，若有错我或是建议的话，欢迎小伙伴们指出；🕊️👻
😄😆希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；🥰🤩
😍😁谢谢你的阅读。😸😼
