当前位置：首页 > news >正文

浙江大学数据结构MOOC-课后习题-第九讲-排序3 Insertion or Heap Sort

news 来源：原创 2024/7/1 6:19:29

题目汇总
浙江大学数据结构MOOC-课后习题-拼题A-代码分享-2024

题目描述

在这里插入图片描述

测试点

在这里插入图片描述

思路分析

和上一题的思路一样，每进行一次迭代，来验证当前序列是否和给定的序列相同

代码展示

#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];elsestd::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;
}