#include <iostream>
using namespace std;
// 合并数组，排好序，然后在拷贝到原来的数组array
void MergeArray(int array[], int start, int end ,int mid, int temp[]) {
int i = start;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= end ) {
if (array[i] < array[j]) {
temp[k++] = array[i++];
}else {
temp[k++] = array[j++];
}
}
while (i <= mid) {
temp[k++] = array[i++];
}
while (j <= end) {
temp[k++] = array[j++];
}
for (int i = 0; i < k; i ++) {
array[start + i] = temp[i];
}
}
// 归并排序，将数组前半部分后半部分分成最小单元，然后在合并
void MergeSort(int array[], int start, int end, int temp[]) {
if(start < end) {
int mid = (start + end)/ 2;
MergeSort(array, start, mid, temp);
MergeSort(array, mid + 1, end, temp);
MergeArray(array, start, end, mid, temp);
}
}
// 在这里创建临时数组，节省内存开销，因为以后的temp都是在递归李使用的。
void MergeSort(int array[], int len) {
int start = 0;
int end = len - 1;
int *temp = new int[len];
MergeSort(array, start, end, temp);
}
void PrintArray(int array[], int len) {
for (int i = 0 ; i < len; ++i) {
cout << array[i] << " " ;
}
cout << endl;
}
int main(int argc, const char * argv[]) {
int array[] = {3,5,3,6,7,3,7,8,1};
MergeSort(array, 9);
PrintArray(array, 9);
return 0;
}
归并排序C++
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 选择排序 对于任何输入，时间为O(n*n)； 冒泡排序 最优（对于升序的数组，因为加入了一个跳出判断）：O(n)，...
