刚才写了个插入排序和合并排序的结合排序法, 但是很奇怪.
Q1: 我定义了MAXSIZE为50, 但是当输入完24个数据后,会自动退出输入...接着我把50改成99, 当输入完72个数据后,又
自动退出输入...(初步怀疑是编译器问题)
Q2: 在Insert_Sort程序块中, 在while里面的条件判定中,如果使用a[i]<a[j]&&...,会导致排序失败(当需要排序的个数小时,排序成功.但当个数大时,排序失败). 如果改成tmp<a[i]&&...就不会出现排序失败.为什么呢?
贴出源程序(没加入输入数据为数字的判定...忽略吧~)
#include <cstdlib>
#include <iostream>
#define MAXSIZE 50
using namespace std;
void Put_In( int[], int& );
void Sort( int[], int, int );
int main(int argc, char *argv[])
{
int a[MAXSIZE], k, i = 0;
Put_In( a, i ); //Put_In
if(i)
{
cout << "\n请输入分段段数! (即把数据分成多少段进行排序,最后合并!)\n" << endl;
do{
cout << "分段段数为: ";
cin >> k;
if( k <= 0 || k > i )
cout << "输入错误!请重新输入!" << endl; //end if
}while( k <= 0 || k > i ); //end do-while
Sort( a, i, k ); //Sort
for(int j = 0; j < i; j++ )
cout << a[j] << " "; //end for
} //end if
cout << endl;
system("PAUSE");
return EXIT_SUCCESS;
} //main
void Put_In( int a[], int& i )
{
cout << "请输入非负整数据进行排序(数据个数不大于50,输入-1结束!)\n" << endl;
do{
cout << "第" << i+1 << "个数据为: ";
cin >> a[i];
if( a[i] < 0 && a[i] != -1 )
cout << "输入错误!请重新输入!" << endl;
else if( a[i] != -1 )
i++; //end if
//end if-else
} while( i < MAXSIZE && a[i] != -1 ); //end do-while
} //Put_In
void Insert_Sort( int a[], int p, int q )
{
int i, j, tmp;
for( i = p + 1; i <= q; i++ )
{
j = i-1;
tmp = a[i];
while( tmp < a[j] && j >= p )
{
a[j+1] = a[j];
j--;
} //end while
a[j+1] = tmp;
} //end for
} //Insert_Sort
void Merge( int a[], int p, int q, int r )
{
int tmp[r-p+1], i = 0, k = p, t = q+1;
while( p <= q && t <= r )
{
if( a[p] <= a[t] )
tmp[i++] = a[p++];
else
tmp[i++] = a[t++]; //end if-else
} //end while
while( p <= q )
tmp[i++] = a[p++]; //end while
while( t <= r )
tmp[i++] = a[t++]; //end while
for( int j = 0 ; k <= r ; k++ )
a[k] = tmp[j++]; //end for
} //Merge
void Sort( int a[], int i, int k )
{
int p, j, t[k+1];
if(i%2)
p = (i+1)/k;
else
p = i/k;
for( j = 0; j < k; j++ )
t[j] = j*p; //end if-else
t[j] = i;
for( int j = 0; j < k; j++ ){
Insert_Sort( a, t[j], t[j+1]-1 ); //end for
for( int w = t[j]; w <= t[j+1]-1; w++ )
cout << a[w] << " || "; //end for, test Insert_Sort, ignore...
cout << endl;
} //end for
for( int j = 0; j < k; j++ )
Merge( a, 0, t[j]-1,t[j+1]-1 ); //end for
} //Sort
[此贴子已经被作者于2007-7-13 16:56:10编辑过]
