// heap sort函数和down adjust函数 需要多多练习
/* 题目总结： 本题主要考插入排序和堆排序，其中堆排序是难点 1）插入排序：插入排序比较简单，每次从原始序列中选未排序的第一个元素，加入到一个vector容器中 用sort函数进行排序，这里需要注意的是，sort是对容器元素排序，一开始用的数组不行 这里insertion写的比较乱，下次先想好思路，在动手写 2）堆排序：一般分为大根堆和小根堆，这里是大根堆 需要注意的是，这里的数组元素要从下标1开始，才能满足相关的性质，如节点i的左孩子是2*i 1.heap sort函数： 首先需要建堆，for循环n/2次，调用down adjust函数 从后往前调整非终端节点 number/2 即最后一个非终端节点,初始i即为number/2 2.down adjust(int low,int high)函数： i=low，j=2*i；j存储的是i的左孩子下标，i是树根， while（i有孩子节点，即j<=high） 然后，比较孩子节点，如果j+1下标元素的值更大，让j=j+1; 比较父节点i和孩子节点j的值那个更大， 如果j的大，swap两个元素，然后令i=j，j=2*1 继续循环 如果j更小，说明该节点已经无需继续下坠，退出循环 */
#pragma warning(disable:4996) #include<vector> #include<iostream> #include<algorithm> using namespace std; int heap[100]; int number; int ini_seq[100]; int mid_seq[100]; vector<int> insert; bool isSame(int A[], int B[]) { for (int i = 1; i < number+1; i++) { if (A[i] != B[i])return false; } return true; } bool insertion() { for (int i = 0; i < number; i++) { insert.push_back(ini_seq[i]); } bool flag = false; for (int i = 1; i < number; i++) { sort(insert.begin(), insert.begin()+i+1); for (int j = 0; j < number; j++) { if (insert[j] == mid_seq[j]) { if (j == number - 1) { if (i != number - 1) { sort(insert.begin(), insert.begin()+i+2); } return true; } } else { flag = false; break; }; } if (i == number - 1) { return false; } } } void down_adjust(int low, int high) { int i = low, j = i * 2; // 存在孩子结点 while (j <= high) { // 选取孩子节点中最大的节点 if (j + 1 <= high && heap[j + 1] > heap[j]) { j = j + 1; // j存储右孩子结点 } // 孩子结点中最大值大于父亲节点值 进行调整 if (heap[j] > heap[i]) { swap(heap[i], heap[j]); i = j; j = i * 2; } // 若此时父亲节点值更大 调整结束 else break; } } bool heap_sort() { int heap_ini[101]; // 误区，注意堆序列是从1开始的 才满足相关性质 for (int i = 0; i < number; i++) { heap[i+1]=ini_seq[i]; heap_ini[i + 1] = mid_seq[i]; } bool flag = false; // 从后往前调整非终端节点 number/2 即最后一个非终端节点 for (int i = number / 2; i > 0; i--) { down_adjust(i, number); //建堆 } for (int i = number; i > 1; i--) { // 比较heap数组和ini_seq数组 if (i != number && isSame(heap, heap_ini)) { flag = true; } // 堆顶堆底元素互换 swap(heap[1], heap[i]); down_adjust(1, i - 1); if (flag) { return true; } } } int main() { cin >> number; for (int i = 0; i < number; i++) { cin >> ini_seq[i]; } for (int i = 0; i < number; i++) { cin >> mid_seq[i]; } if (insertion()) { printf("Insertion Sort\n"); for (int i = 0; i < number; i++) { printf("%d ", insert[i]); } } else { heap_sort(); printf("Heap Sort\n"); for (int i = 1; i < number+1; i++) { printf("%d ", heap[i]); } } system("pause"); return 0; }
