归并排序实现不了为什么?也没报错啊
#include "stdafx.h"
#include<stdlib.h>
#include <iostream>
using namespace std;
int* MergeSort(int array[], int start, int end);
int _tmain(int argc, _TCHAR* argv[])
{
int array[8]={12,25,10,8,3,89,49,20};
int* arr=MergeSort(array,0,7);
cout<<arr<<endl;
system("pause");
return 0;
}
void Merge(int array[], int start, int mid, int end)
{
int temp1[10], temp2[10];
int n1, n2;
n1 = mid - start + 1;
n2 = end - mid;
for (int i = 0; i < n1; i++)
{
temp1[i] = array[start + i];
}
for (int i = 0; i < n2; i++)
{
temp2[i] = array[mid + i + 1];
}
temp1[n1] = temp2[n2] = 1000;
for (int k = start, i = 0, j = 0; k <= end; k++)
{
if (temp1[i] <= temp2[j])
{
array[k] = temp1[i];
i++;
}
else
{
array[k] = temp2[j];
j++;
}
}
}
int* MergeSort(int array[], int start, int end)
{
if (start < end)
{
int i;
i = (end + start) / 2;
MergeSort(array, start, i);
MergeSort(array, i + 1, end);
Merge(array, start, i, end);
}
return array;
}
[解决办法]
//#只完成兩段之間歸併的功能#% void Merge(int a[], int b[], int low, int mid, int high) { int k = low; int begin1 = low; int end1 = mid; int begin2 = mid + 1; int end2 = high; while(k <= high ) { if(begin1 > end1) b[k++] = a[begin2++]; else if(begin2 > end2) b[k++] = a[begin1++]; else { if(a[begin1] <= a[begin2]) b[k++] = a[begin1++]; else b[k++] = a[begin2++]; } } } void MergePass(int a[], int b[], int seg, int size) { int seg_start_ind = 0; while(seg_start_ind <= size - 2 * seg) //#size - 2 * seg的意思是滿足可兩兩歸併的最低臨界值#% { Merge(a, b, seg_start_ind, seg_start_ind + seg - 1, seg_start_ind + seg * 2 - 1); seg_start_ind += 2 * seg; } //#如果一段是正好可歸併的數量而另一段則少於正好可歸併的數量#% if(seg_start_ind + seg < size) Merge(a, b, seg_start_ind, seg_start_ind + seg - 1, size - 1); else for(int j = seg_start_ind; j < size; j++) //#如果只剩下一段或者更少的數量#% b[j] = a[j]; } void MergeSort(int a[], int size) { int* temp = new int[size]; int seg = 1; while(seg < size) { MergePass(a, temp, seg, size); seg += seg; MergePass(temp, a, seg, size); seg += seg; } } int main() { int a[] = {3, 5, 3, 6, 4, 7, 5, 7, 4}; //#QQ#% MergeSort(a, sizeof(a) / sizeof(*a)); //#輸出#% for(int i = 0; i < sizeof(a) / sizeof(*a); i++) cout << a[i] << ' '; cout << endl; return 0; }
[解决办法]
//归并排序(目标数组,子表的起始位置,子表的终止位置) private static void MergeSortFunction(int[] array, int first, int last) { try { if (first < last) //子表的长度大于1,则进入下面的递归处理 { int mid = (first + last) / 2; //子表划分的位置 MergeSortFunction(array, first, mid); //对划分出来的左侧子表进行递归划分 MergeSortFunction(array, mid + 1, last); //对划分出来的右侧子表进行递归划分 MergeSortCore(array, first, mid, last); //对左右子表进行有序的整合(归并排序的核心部分) } } catch (Exception ex) { } } //归并排序的核心部分:将两个有序的左右子表(以mid区分),合并成一个有序的表 private static void MergeSortCore(int[] array, int first, int mid, int last) { try { int indexA = first; //左侧子表的起始位置 int indexB = mid + 1; //右侧子表的起始位置 int[] temp = new int[last + 1]; //声明数组(暂存左右子表的所有有序数列):长度等于左右子表的长度之和。 int tempIndex = 0; while (indexA <= mid && indexB <= last) //进行左右子表的遍历,如果其中有一个子表遍历完,则跳出循环 { if (array[indexA] <= array[indexB]) //此时左子表的数 <= 右子表的数 { temp[tempIndex++] = array[indexA++]; //将左子表的数放入暂存数组中,遍历左子表下标++ } else//此时左子表的数 > 右子表的数 { temp[tempIndex++] = array[indexB++]; //将右子表的数放入暂存数组中,遍历右子表下标++ } } //有一侧子表遍历完后,跳出循环,将另外一侧子表剩下的数一次放入暂存数组中(有序) while (indexA <= mid) { temp[tempIndex++] = array[indexA++]; } while (indexB <= last) { temp[tempIndex++] = array[indexB++]; } //将暂存数组中有序的数列写入目标数组的制定位置,使进行归并的数组段有序 tempIndex = 0; for (int i = first; i <= last; i++) { array[i] = temp[tempIndex++]; } } catch (Exception ex) { } }
[解决办法]
#include "stdafx.h"
#include<stdlib.h>
#include <iostream>
using namespace std;
void MergeSort(int array[], int start, int end);
int _tmain(int argc, _TCHAR* argv[])
{
int array[8]={12,25,10,8,3,89,49,20};
MergeSort(array,0,7);
for (int i = 0; i < 8; i++)//数组需要通过循环逐个输出,不能像char类型或者string类型的数据那样一次输出。
cout<<array[i]<<endl;
system("pause");
return 0;
}
void Merge(int array[], int start, int mid, int end)
{
int temp1[10], temp2[10];
int n1, n2;
n1 = mid - start + 1;
n2 = end - mid;
for (int i = 0; i < n1; i++)
{
temp1[i] = array[start + i];
}
for (int i = 0; i < n2; i++)
{
temp2[i] = array[mid + i + 1];
}
temp1[n1] = temp2[n2] = 1000;
for (int k = start, i = 0, j = 0; k <= end; k++)
{
if (temp1[i] <= temp2[j])
{
array[k] = temp1[i];
i++;
}
else
{
array[k] = temp2[j];
j++;
}
}
}
void MergeSort(int array[], int start, int end) //此处不需要返回值,array本身就可以返回
{
if (start < end)
{
int i;
i = (end + start) / 2;
MergeSort(array, start, i);
MergeSort(array, i + 1, end);
Merge(array, start, i, end);
}
//return array;
}
程序逻辑本身没有问题,通过测试修改后的程序能够按从小到大输出。