归并排序
标签：push 元素 code lse nbsp void 就是 数组 int
归并排序的步骤如下：
思想：将数组分成两部分，两部分都是有序的时候，把两个数组合并。合并的方法就是双指针，i 指向左边的数组，j 指向右边的数组，比较 L[i] 和 R[j] 的大小，将其填入原数组，并且将 i 或 j 往后移。
步骤：
1.将数组分成两部分，直到其中只包含一个元素
2.当数组只包含一个元素的时候，递归返回上一层，此时数组包含两个元素，左数组一个，右数组一个，将左右数组合并。
#include
#include using namespace std;
void merge(vectorint>& arr, int l, int m, int r){
int n1 = m-l+1;
int n2 = r-m;
vectorint> L;
vectorint> R;
for(int i = 0; i i]);
for(int j = 0; j 1+j]);
int i = 0;
int j = 0;
int k = l;
while(i n2){
if(L[i] ];
else arr[k++] = R[j++];
}
while(i ];
while(j ];
}
void mergeSort(vectorint>& arr, int l, int r){
if(l r){
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
int main(){
vectorint> arr = {38};
mergeSort(arr, 0, arr.size()-1);
return 0;
}
归并排序
标签：push 元素 code lse nbsp void 就是 数组 int
原文地址：https://www.cnblogs.com/olajennings/p/12769692.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
归并排序
文章链接：http://soscw.com/index.php/essay/52805.html
评论