摄影网站建设内容,大连市城乡建设局网站,打电话来说做网站 然后答应了,wordpress谷歌广告目录 题目
Description
Input
Output
思路#xff08;归并排序#xff09;
具体步骤如下
C整体代码#xff08;含详细注释#xff09;
归并排序总结
核心步骤
代码模板 题目
Description
小张在暑假时间来到工地搬砖挣钱。包工头交给他一项艰巨的任务#xff0…目录 题目
Description
Input
Output
思路归并排序
具体步骤如下
C整体代码含详细注释
归并排序总结
核心步骤
代码模板 题目
Description
小张在暑假时间来到工地搬砖挣钱。包工头交给他一项艰巨的任务将一排砖头按照从低到高的顺序排好。可是小张的力量有限每次只能交换相邻的两块砖头请问他最少交换几次能够完成任务
Input
第一行一个整数 表示砖头数量。 第二行 个整数 表示砖头的高度。
Output
一个整数表示最少交换几次能够完成任务。
测试输入期待的输出时间限制内存限制额外进程测试用例 1以文本方式显示 5↵4 1 3 2 5↵以文本方式显示 4↵1秒64M0 思路归并排序
冒泡排序的时间复杂度是On^2归并排序的时间复杂度是Onlogn 本题使用冒泡排序TLE(超时,因此考虑归并排序。
归并排序的思路是将数组划分为越来越小的子数组然后不断将子数组合并成有序的数组。在合并的过程中统计交换次数即每次将右半区的元素插入到左半区时左半区剩余的元素个数即逆序数为交换次数。 通过归并排序的思路可以保证最终的数组是有序的并且交换次数是最少的。 具体步骤如下
1.首先定义了一个merge函数用于将两个有序的子数组合并成一个有序的数组。在合并的过程中记录交换次数count用来统计交换的次数。
//归并两个有序数组
void merge(vectorlong long h, int left, int mid, int right, long long count) {vectorlong long tempArr(right - left 1);//分配一个临时数组int l_pos left;int r_pos mid 1;int pos 0;while (l_pos mid r_pos right) {if (h[l_pos] h[r_pos]) {//左半区第一个剩余元素更小tempArr[pos] h[l_pos];}else {//右半区第一个剩余元素更小tempArr[pos] h[r_pos];count mid - l_pos 1; // 更新交换次数}}//合并左半区剩余元素while (l_pos mid)tempArr[pos] h[l_pos];//合并右半区剩余元素while (r_pos right)tempArr[pos] h[r_pos];//把临时数组中合并后的元素复制回原来的数组for (int i 0; i pos; i) {h[left i] tempArr[i];}
} 2.然后定义了一个mergeSort函数用于对数组进行归并排序。在归并排序的过程中将数组不断划分为两个子数组然后分别对子数组进行递归排序最后再将两个有序的子数组合并成一个有序的数组。
//归并排序
void mergeSort(vectorlong long h, int left, int right, long long count) {if (left right) {//如果左区间大于右区间或者只有一个元素时就不需要继续划分//如果只有一个元素本生就是有序的只需要被归并即可return;}//找中间点int mid (left right) / 2;//递归划分左半区mergeSort(h, left, mid, count);//递归划分右半区mergeSort(h, mid 1, right, count);//合并已经排序的部分merge(h, left, mid, right, count);
}
3.在主函数中首先读取输入的砖头数量n和砖头的高度数组h。然后定义一个变量count来记录交换次数。接着调用mergeSort函数对数组h进行归并排序并将交换次数保存在count中。
最后输出count即为完成任务所需的最少交换次数。
int main() {int n;cin n;vectorlong long h(n);for (int i 0; i n; i) {cin h[i];}long long count 0;mergeSort(h, 0, h.size() - 1, count);cout count endl;return 0;
}C整体代码含详细注释
#include iostream
#include algorithm
#include vector using namespace std;//归并两个有序数组
void merge(vectorlong long h, int left, int mid, int right, long long count) {vectorlong long tempArr(right - left 1);//分配一个临时数组int l_pos left;int r_pos mid 1;int pos 0;while (l_pos mid r_pos right) {if (h[l_pos] h[r_pos]) {//左半区第一个剩余元素更小tempArr[pos] h[l_pos];}else {//右半区第一个剩余元素更小tempArr[pos] h[r_pos];count mid - l_pos 1; // 更新交换次数}}//合并左半区剩余元素while (l_pos mid)tempArr[pos] h[l_pos];//合并右半区剩余元素while (r_pos right)tempArr[pos] h[r_pos];//把临时数组中合并后的元素复制回原来的数组for (int i 0; i pos; i) {h[left i] tempArr[i];}
}//归并排序
void mergeSort(vectorlong long h, int left, int right, long long count) {if (left right) {//如果左区间大于右区间或者只有一个元素时就不需要继续划分//如果只有一个元素本生就是有序的只需要被归并即可return;}//找中间点int mid (left right) / 2;//递归划分左半区mergeSort(h, left, mid, count);//递归划分右半区mergeSort(h, mid 1, right, count);//合并已经排序的部分merge(h, left, mid, right, count);
}int main() {int n;cin n;vectorlong long h(n);for (int i 0; i n; i) {cin h[i];}long long count 0;mergeSort(h, 0, h.size() - 1, count);cout count endl;return 0;
}归并排序总结
归并排序的核心是将一个未排序的数组逐步划分为越来越小的子数组然后将这些子数组合并成一个有序的数组。
核心步骤 分割将未排序的数组划分为两个子数组分别对左右两个子数组进行递归地分割直到每个子数组只包含一个元素或为空。 合并将两个有序的子数组合并成一个有序的数组。在合并的过程中比较左右两个子数组的元素将较小或较大的元素放入临时数组中直到其中一个子数组的元素全部放入临时数组中。然后将剩余的另一个子数组的元素依次放入临时数组中。 复制将临时数组中的元素复制回原来的数组。
通过不断地递归分割和合并最终可以得到一个完全有序的数组。
归并排序的核心思想是分治法将一个大问题拆分为若干个小问题然后分别解决这些小问题最后将解决好的小问题合并成一个整体解决方案。在归并排序中每次合并两个有序的子数组时都能保证合并后的数组仍然是有序的通过不断地合并最终可以得到一个完全有序的数组。
代码模板
#include iostream
#include vectorusing namespace std;// 合并两个有序的子数组
void merge(vectorint nums, int left, int mid, int right) {int n1 mid - left 1; // 左子数组的长度int n2 right - mid; // 右子数组的长度// 创建临时数组来存储合并后的结果vectorint temp(n1 n2);int i left; // 左子数组的起始索引int j mid 1; // 右子数组的起始索引int k 0; // 临时数组的索引// 将两个子数组中的元素按照从小到大的顺序放入临时数组中while (i mid j right) {if (nums[i] nums[j]) {temp[k] nums[i];} else {temp[k] nums[j];}}// 将左子数组中剩余的元素放入临时数组中while (i mid) {temp[k] nums[i];}// 将右子数组中剩余的元素放入临时数组中while (j right) {temp[k] nums[j];}// 将临时数组中的元素复制回原数组for (int p 0; p n1 n2; p) {nums[left p] temp[p];}
}// 归并排序
void mergeSort(vectorint nums, int left, int right) {if (left right) {return;}int mid left (right - left) / 2; // 找到数组的中间位置// 递归地对左右两个子数组进行归并排序mergeSort(nums, left, mid);mergeSort(nums, mid 1, right);// 合并两个有序的子数组merge(nums, left, mid, right);
}int main() {int n;cin n;vectorint nums(n);for (int i 0; i n; i) {cin nums[i];}mergeSort(nums, 0, n - 1);// 输出排序后的数组for (int i 0; i n; i) {cout nums[i] ;}cout endl;return 0;
}
