一、技术总结
- 这一题是关于堆排序和插入排序的问题,首先是要理解这两个排序的原理,对于插入排序,是对于序列的前一部分默认为有序,然后从后面开始依次往前进行比较,插入到合适的位置上,排序过程中,序列的特征是,前面的是从小到大的,但是后面的部分,与原来的序列应该是相同的;
void insertSort{
for(int i = 2; i <= n; i++){
int temp = A[i], j = i;
while(j >= 1 && A[j] < A[j - 1]){
A[j] = A[j - 1];
j--;
}
A[j] = temp;
}
- 关于堆排序,每次排序是将堆顶元素放置到序列末尾,然后进行一次向下调整,所以序列特征是,末尾的元素是从小到大的,堆顶一定是没有排序的中元素最大值;
二、参考代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXV = 105;
int origin[MAXV], sor[MAXV];
void downAjust(int low, int high){
int i = low, j = 2 * i;
while(j <= high){
if(j + 1 <= high && sor[j] < sor[j + 1]){
j = j + 1;
}
if(sor[i] < sor[j]){
swap(sor[i], sor[j]);
i = j;
j = 2 * i;
}else{
break;
}
}
}
int main(){
int n, p = 2;
cin >> n;
for(int i = 1; i <= n; i++){
scanf("%d", &origin[i]);
}
for(int i = 1; i <= n; i++){
scanf("%d", &sor[i]);
}
while(p <= n && sor[p - 1] <= sor[p]) p++;
int index = p;
while(p <= n && origin[p] == sor[p]) p++;
if(p == n + 1){
printf("Insertion Sort
");
sort(sor + 1, sor + index + 1);
}else{
printf("Heap Sort
");
p = n;
while(p > 2 && sor[p] >= sor[1]) p--;
swap(sor[1], sor[p]);
downAjust(1, p - 1);
}
printf("%d", sor[1]);
for(int i = 2; i <= n; i++){
printf(" %d", sor[i]);
}
return 0;
}