深圳品牌学校网站建设,济南做外贸网站的公司,深圳十大网站建设,一般网站维护费用模板在文末#xff0c;以下步骤方便理解记忆。
先贴一张快速排序模板步骤#xff0c;用于对比记忆 归并排序步骤#xff1a;
#xff08;0#xff09;如果数组左边界L ≥ 数组右边界#xff0c;则不需要排序#xff0c;直接return。
#xff08;1#xff09;直接取…模板在文末以下步骤方便理解记忆。
先贴一张快速排序模板步骤用于对比记忆 归并排序步骤
0如果数组左边界L ≥ 数组右边界则不需要排序直接return。
1直接取数组正中间的数即 mid (LR) / 2为边界。
2先递归对 L~mid mid1 ~ R 这两个区间的数组调用归并排序函数。
3对于每次归并它的面前有两个排好序的数组即 [ L, mid ] 和 [ mid1, R ]接下来需要把这两个数组合为另一个有序的数组。
具体操作是采用双下标指针首先令 i Lj mid 1即两个数组的左边界
接着让q[ i ]和q[ j ]中更小的那个先放进 temp 数组里然后 i 或 j以此类推。
当其中一个下标指针到达末端时直接将另一个数组原封不动的拷贝进 temp 数组里。
4最后把 temp 数组拷贝到 q 数组中。这一步容易写错 #includeiostream
using namespace std;const int N 100010;int n;
int q[N], temp[N];void merge_sort(int q[], int l, int r)
{if(l r) return;int mid (lr) 1;merge_sort(q, l, mid), merge_sort(q, mid1, r);int i l, j mid1, k 0;while(i mid j r) //对应步骤(3),而且当两个数组的指针都没有越界时才这么做{if(q[i] q[j]) temp[k] q[i];else temp[k] q[j];}while(i mid) temp[k] q[i]; //如果i没有越界,则将i后面的原封不动地拷贝进去while(j r) temp[k] q[j]; //如果j没有越界,则将j后面拷贝进去//q和temp数组的范围不同因此需要两个变量i,j// 注意不是i nfor(int il, j0; i r; i, j) q[i] temp[j]; //步骤(4),注意写法
}int main()
{scanf(%d, n);for(int i0;in;i) scanf(%d, q[i]);merge_sort(q, 0, n-1);for(int i0;in;i) printf(%d , q[i]);return 0;
}
