题目 OJ平台题目大意有很多题目实际不需要看懂题目，只需要看懂输入和输出，比如这题。 此题虽然题目较为学术，且比较长，实际总结下来就是，通过给你一个原数组序列，还有一个用插入排序或者是堆排序排了几轮的数组序列，你要根据这个序列判断所使用的排序方式，并且再以该排序方式往下排一轮。解题代码拆解 这次由于我使用的接口化函数设计，也就是传入指针进行操作，没有采用全局变量，所以直接input操作写在main函数里面，省空间。关键的判断函数 isInsert() 设计思路：假设为插入排序后的序列，通过一次循环，找到下一个要被排序的元素位置，按理来说，没有被排序的位置应该和原数组的序列情况一致，如果不一致，则不是插入排序。//用于确定是否为插入排序，顺便返回此时待插入处理的位置 int isInsert(int* nums, int len) { int i = 1; for (; i < len; i++) { if (nums[i - 1] > nums[i]) break; } for (int j = i; j < len; j++) { if (original[j] != nums[j]) return -1; } return i; } 堆排序和插入排序插入排序 插入排序很简单，我这里直接写插入排序的每一轮处理函数来代替。//插入排序的单步处理 void InsertSort(int* nums, int numSize, int i) { int j = i; int temp = nums[i]; for (; j > 0 && nums[j - 1] > temp; j--) { nums[j] = nums[j - 1]; } nums[j] = temp; } 堆排序 堆排序的原理： 对于一个完整的堆排序，分为两个过程：堆化+维持堆化。 建立大根堆，每次堆化找到最大值，为了维持堆的结构和排序，将堆顶与最后一个元素交换，然后更新堆的范围到 0~i-1 再次堆化，又能找到这个堆中的最大值，长此以往，便完成了排序。对于堆排序中的每一轮：堆排中的每一轮都是缩小堆的范围，并继续维持大根堆，在堆范围以外的元素就是被排好的元素。所以重点在于从后往前找到已经排到了哪个位置，再进行一次交换和堆化便可完成一轮排序。 堆排的过程： 向下堆化的函数：sift_down()//堆化，得到大根堆 //对于从0开始编号的二叉堆: /* iparent = (i-1)/2, ilchild = i*2+1, irchild = i*2+2 */ void sift_down(int arr[], int start, int end) { // 计算父结点和子结点的下标 int parent = start; int child = parent * 2 + 1; while (child <= end) { // 子结点下标在范围内才做比较 // 先比较两个子结点大小，选择最大的 if (child + 1 <= end && arr[child] < arr[child + 1]) child++; // 如果父结点比子结点大，代表调整完毕，直接跳出函数 if (arr[parent] >= arr[child]) return; else { // 否则交换父子内容，子结点再和孙结点比较 swap(arr[parent], arr[child]); parent = child; child = parent * 2 + 1; } } } 先完全堆化，再利用它挑选最大值维持堆化的过程：heap_sort()void heap_sort(int arr[], int len) { // 从最后一个节点的父节点开始 sift down 以完成堆化 (heapify) for (int i = (len - 1 - 1) / 2; i >= 0; i--) sift_down(arr, i, len - 1); // 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕 for (int i = len - 1; i > 0; i--) { swap(arr[0], arr[i]); sift_down(arr, 0, i - 1); } } 方便更新下一轮堆排的工具： 确定堆排序到哪个位置的函数：findP//由于堆排是从后往前先得出最大值，所以直接从后往前判断最大值位置即可得出堆排排到了哪一轮 int findP(int* nums, int len) { int i = 0; for (; i < len; i++) { int val = *max_element(nums, nums + len…