重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
7-1 快速排序
作者 朱允刚
单位 吉林大学
给定包含n个元素的整型数组a[1],a[2],…,a[n],利用快速排序算法对其进行递增排序,请输出排序过程,即每次Partition之后的数组。每次选择所处理的子数组的第一个元素作为基准元素。
输入格式:
输入为两行,第一行为一个整数n(1
输出为若干行,每行依次输出Partition后的数组,每个元素后一个空格。
输入样例:
5
4 5 3 2 1
输出样例:
2 1 3 4 5
1 2 3 4 5
1 2 3 4 5
#includeusing namespace std;
int array[1005],n;
void print(){for(int i=1;i<=n;++i){cout<int mid=a;
a=b;
b=mid;
}
int Partition(int array[],int left,int right){int location=left;
array[0]=array[left];
while(leftwhile(leftarray[0]) --right;
while(leftif(leftint position=Partition(array,left,right);
print();
quicksort(array,left,position-1);
quicksort(array,position+1,right);
}
}
int main()
{cin>>n;
for(int i=1;i<=n;++i){cin>>array[i];
}
quicksort(array,1,n);
print();
return 0;
}
7-2 堆排序
作者 严华云
单位 湖州师范学院
对n个数,要求用堆排序(大堆)对其进行排序。
输入格式:
第一行一个n(n<1000)。第二行给出n个数。
输出格式:
输出n行,每行n个数。第一行表示将n个数(将n个数看成一棵树)变成大堆后的结果,第二行表示将上次结果的根节点交换到现有节点的最后一个节点(然后将除最后一个节点的数看成一颗树),然后将该剩余节点树从新变成大堆后的结果输出(包括交换到最后的节点),依次类推。
输入样例:
6
7 1 6 4 3 5
输出样例:
7 4 6 1 3 5
6 4 5 1 3 7
5 4 3 1 6 7
4 1 3 5 6 7
3 1 4 5 6 7
1 3 4 5 6 7
#includeusing namespace std;
int n,x;
void print(vector& nums){for(int i=0;icout<& nums, int i, int len) {for (; (i<< 1) + 1<= len;) {int lson = (i<< 1) + 1;
int rson = (i<< 1) + 2;
int large;
if (lson<= len && nums[lson] >nums[i]) {large = lson;
} else {large = i;
}
if (rson<= len && nums[rson] >nums[large]) {large = rson;
}
if (large != i) {swap(nums[i], nums[large]);
i = large;
} else {break;
}
}
}
void buildMaxHeap(vector& nums, int len) {for (int i = len / 2; i >= 0; --i) {maxHeapify(nums, i, len);
}
}
void heapSort(vector& nums) {int len = (int)nums.size() - 1;
buildMaxHeap(nums, len);
print(nums);
for (int i = len; i >= 1; --i) {swap(nums[i], nums[0]);
len -= 1;
maxHeapify(nums, 0, len);
print(nums);
}
}
int main(){cin>>n;
vectornums(n);
for(int i=0;icin>>x;
nums[i]=x;
}
heapSort(nums);
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧