首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

归并排序兑现不了为什么?也没报错

2012-10-20 
归并排序实现不了为什么?也没报错啊#include stdafx.h#includestdlib.h#includeiostreamusingnamesp

归并排序实现不了为什么?也没报错啊
#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;
}

[解决办法]

C/C++ code
//#只完成兩段之間歸併的功能#% 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; }
[解决办法]
C# code
//归并排序(目标数组,子表的起始位置,子表的终止位置)        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;
}

程序逻辑本身没有问题,通过测试修改后的程序能够按从小到大输出。

热点排行