赞
踩
和上一题的思路一样,每进行一次迭代,来验证当前序列是否和给定的序列相同
#include <cstdlib> #include <iostream> #define MAXSIZE 100 typedef int ElementType; void swap(int A[], int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } void print(int A[], int N) { for (int i = 0; i < N; i++) { if (i == 0) std::cout << A[i]; else std::cout << ' ' << A[i]; } } bool isSame(int A[], int input[], int N) { for (int i = 0; i < N; i++) { if (A[i] != input[i]) return false; } return true; } bool insertion_Sort(int A[], int input[], int N) { /* 算法 */ int i, j, temp; bool flag = false; for (i = 1; i < N; i++) { temp = A[i]; /* 摸牌 */ for (j = i; j > 0 && A[j - 1] > temp; j--) A[j] = A[j - 1]; A[j] = temp; if (flag == true) { print(A, N); return true;; } if (isSame(A, input, N)) { std::cout << "Insertion Sort" << std::endl; flag = true; } } return false; } void percDown(int A[], int p, int N) { /* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */ int parent, child; int temp = A[p]; for (parent = p; (parent * 2 + 1) < N; parent = child) { child = parent * 2 + 1; /* child指向左右孩子中较大者 */ if (child != N - 1 && A[child] < A[child + 1]) child++; if (temp > A[child]) break; else A[parent] = A[child]; } A[parent] = temp; } void heap_Sort(int A[], int input[], int N) { bool flag = false; /* 建立大根堆 */ for (int i = N - 1; i >= 0; i--) percDown(A, i, N); /* 删除最大值 */ for (int i = N - 1; i >= 0; i--) { swap(A, 0, i); percDown(A, 0, i); if (flag == true) { print(A, N); return; } if (isSame(A, input, N)) { std::cout << "Heap Sort" << std::endl; flag = true; } } } void check(int A[], int input[], int N) { int copyA[MAXSIZE]; for (int i = 0; i < N; i++) copyA[i] = A[i]; if (insertion_Sort(copyA, input, N)) return; else { for (int i = 0; i < N; i++) copyA[i] = A[i]; heap_Sort(copyA, input, N); return; } } int main() { int A[MAXSIZE]; int input[MAXSIZE]; int N; std::cin >> N; for (int i = 0; i < N; i++) std::cin >> A[i]; for (int i = 0; i < N; i++) std::cin >> input[i]; check(A, input, N); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。