Created
February 16, 2020 15:02
-
-
Save imsjz/040cc0a14aa30f949bde95e231915c45 to your computer and use it in GitHub Desktop.
更正了新的版本
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
/* Copyright sanjay 2020 */ | |
// 本程序使用两种方式实现归并排序,一种是c方式,一种是stl库方式 | |
// 两者差异不大,仅传参类型不一样 | |
namespace c_style { | |
void Merge(int a[], int left, int mid , int right) { | |
// 需要求得每一半的长度,以便申请空间 | |
int left_length = mid - left + 1; | |
int right_length = right - mid; | |
int* p_left = new int[left_length](); | |
int* p_right = new int[right_length](); | |
for(int i = 0; i < left_length; ++i) { | |
p_left[i] = a[i + left]; | |
} | |
for(int j = 0; j < right_length; ++j) { | |
p_right[j] = a[j + mid + 1]; | |
} | |
int i = 0, j = 0, k = left; | |
while(i < left_length && j < right_length) { | |
if (p_left[i] < p_right[j]) { | |
a[k++] = p_left[i++]; | |
} | |
else { | |
a[k++] = p_right[j++]; | |
} | |
} | |
while(i < left_length) { | |
a[k++] = p_left[i++]; | |
} | |
while (j < right_length) { | |
a[k++] = p_right[j++]; | |
} | |
// 不要忘了删掉内存 | |
delete [] p_left; | |
delete [] p_right; | |
} | |
void MergeSort(int a[], int left, int right) { | |
if (left < right) { // 这个判断条件很重要,这是递归结束的条件 | |
int mid = (left + right) / 2; | |
MergeSort(a, left, mid); | |
MergeSort(a, mid + 1, right); | |
Merge(a, left, mid, right); | |
} | |
} | |
void TestMergeSort() { | |
int array[] = {9, 3, 7, 5, 6, 4, 8, 2}; | |
for(auto ele : array){ | |
std::cout << ele << " "; | |
} | |
std::cout << std::endl; | |
MergeSort(array, 0, sizeof(array) / sizeof(int) -1); | |
for(auto ele : array){ | |
std::cout << ele << " "; | |
} | |
std::cout << std::endl; | |
} | |
} | |
namespace cpp_style { | |
// 直接传入迭代器即可 | |
void Merge( | |
std::vector<int>::iterator begin, | |
std::vector<int>::iterator mid, | |
std::vector<int>::iterator end) { | |
int left_length = (mid - begin) + 1; | |
int right_length = end - mid; | |
int* left = new int[left_length](); | |
int* right = new int[right_length](); | |
for(int i = 0; i < left_length; ++i) { | |
left[i] = *(begin + i); | |
} | |
for(int j = 0; j < right_length; ++j) { | |
right[j] = *(j + mid + 1); | |
} | |
int i = 0, j = 0; | |
while(i < left_length && j < right_length) { | |
if(left[i] < right[j]) { | |
*(begin++) = left[i++]; | |
} | |
else { | |
*(begin++) = right[j++]; | |
} | |
} | |
while(i < left_length) { | |
*(begin++) = left[i++]; | |
} | |
while(j < right_length) { | |
*(begin++) = right[j++]; | |
} | |
delete [] left; | |
delete [] right; | |
// 尝试了用vector进行保存,效果不行,个人猜测是内存的不连续问题 | |
// std::vector<int> left(begin, mid + 1); | |
// std::vector<int> right(mid + 1, end); | |
// std::vector<int>::iterator p_left = left.begin(); | |
// std::vector<int>::iterator p_right = right.begin(); | |
// while(p_left != left.end() && p_right != right.end()) { | |
// if (*p_left < *p_right) { | |
// *(begin++) = *(p_left++); | |
// } | |
// else { | |
// *(begin++) = *(p_right++); | |
// } | |
// } | |
// while(p_left != left.end()) { | |
// *(begin++) = *(p_left++); | |
// } | |
// while(p_right != right.end()) { | |
// *(begin++) = *(p_right++); | |
// } | |
} | |
void MergeSort(std::vector<int>::iterator left, std::vector<int>::iterator right) { | |
if(left != right) { | |
std::vector<int>::iterator mid = left + (right - left) / 2; // 这里不可以加 1, 比如right = 1, left = 0, 加1之后mid永远是1,死循环了 | |
MergeSort(left, mid); | |
MergeSort(mid + 1, right); | |
Merge(left, mid, right); | |
} | |
} | |
void TestMergeSort() { | |
std::vector<int> vec{9, 3, 7, 5, 6, 4, 8, 2}; | |
MergeSort(vec.begin(), vec.end() - 1); | |
for(auto e : vec) { | |
std::cout << e << " "; | |
} | |
std::cout << std::endl; | |
} | |
} | |
int main() { | |
// c_style::TestMergeSort(); | |
// int a[5] = {1,2,3,4,5}; | |
// std::vector<int> b(a, a + 5); // 这个是最后元素最后一位 | |
// for(auto e : b){ | |
// std::cout << e << " "; | |
// } | |
cpp_style::TestMergeSort(); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment