230问答网 > c++ 排序算法应用二（直接法、插入法、shell排序）怎么做

c++ 排序算法应用二（直接法、插入法、shell排序）怎么做

2025-02-18 16:57:19

推荐回答（6个）

回答1：

同上，不过，我曾写了个意思吧的，楼主改下吧，希尔排序没写，不过有快排，希尔排序最简单的可以看The c programming language
/*将行为抽象成属性,使用继承,使得程序的可拓展性大幅度增加
使用模板编程,使得程序的可使用范围大幅度增加
*/
#include
#include

const int START = 0;

using namespace std;

//基类，抽象类,有一个行为:交换两个对象的内容,重载()运算符,使得它的对象能模拟行为
template< class T > class Arraysort
{
public:
Arraysort(){}
void swap( T&, T& );//交换两个对象的内容
virtual void operator()( T [], int ) = 0;//重载()运算符
};

template< class T >
void Arraysort< T >::swap( T& t1, T& t2 )
{
T t;

t = t1;
t1 = t2;
t2 =t;
}

//派生类Selectsort,使用选择排序对数组进行排序
template< class T > class Selectsort:public Arraysort< T >
{
public:
Selectsort(){}
void selectsort( T [], int );//行为选择排序
virtual void operator()( T [], int );//重载()运算符
};

//派生类Bubblesort,使用选冒泡排序对数组进行排序
template< class T > class Bubblesort:public Arraysort< T >
{
public:
void bubblesort( T [], int );//行为冒泡排序
virtual void operator()( T [], int );//重载()运算符
};

//派生类Quicksort,使用选快速排序对数组进行排序
template< class T > class Quicksort:public Arraysort< T >
{
public:
void quicksort( T [], int, int );//行为快速排序
virtual void operator()( T [], int );//重载()运算符
};

template< class T >
void Selectsort< T >::selectsort( T a[], int n )
{
for( int i = 0; i < n - 1; i++ )
{
int k = i;
for( int j = i + 1; j < n; j++ )
{
if( a[ k ] > a[ j ] )
k = j;
}
if( k != i )
swap( a[ k ], a[ i ] );
}
}

template< class T >
void Selectsort< T >::operator()( T a[], int n )
{
selectsort( a, n );
}

template< class T >
void Bubblesort< T >::bubblesort( T a[], int n )
{
for( int pass = 0; pass < n - 1; pass++ )
for( int i = 0; i < n - pass - 1; i++ )
if( a[ i ] > a[ i + 1 ] )
swap( a[ i ], a[ i + 1 ] );
}

template< class T >
void Bubblesort< T >::operator()( T a[], int n )
{
bubblesort( a, n );
}

template< class T >
void Quicksort< T >::quicksort( T a[], int left, int right )
{
int last;

if( left >= right )
return;

last = left;
for( int i = left + 1; i <= right; i++ )
if( a[ left ] > a[ i ] )
swap( a[ ++last ], a[ i ] );

swap( a[ left ], a[ last ] );

quicksort( a, left, last - 1 );
quicksort( a, last + 1, right );
}

template< class T >
void Quicksort< T >::operator()( T a[], int n )
{
quicksort( a, START, n - 1 );
}

//main函数,验证了模板,以及将行为抽象为对象,不过没有验证多态
int main()
{
int i;
int n;
int* Array_integer;
double* Array_double;
string* Array_string;
Selectsort< int > S_sort;
Bubblesort< double > B_sort;
Quicksort< string > Q_sort;

cout << "Intput the size of array:" << endl;

cin >> n;

Array_integer = new int [ n ];
Array_double = new double [ n ];
Array_string = new string[ n ];

//读入数据
cout << "\nInput " << n << " integers:" << endl;
for( i = 0; i < n; i++ )
cin >> Array_integer[ i ];

cout << "\nInput " << n << " double data:" << endl;
for( i = 0; i < n; i++ )
cin >> Array_double[ i ];

cout << "\nInput " << n << " string:" << endl;
for( i = 0; i < n; i++ )
cin >> Array_string[ i ];
//读入结束

//排序,使用对象进行函数的功能
S_sort( Array_integer, n );
B_sort( Array_double, n );
Q_sort( Array_string, n );

//输出数据
cout << "\nAfter sort, the data are:" << endl;

cout << '\n' << n << " integers:" << endl;
for( i = 0; i < n; i++ )
cout << Array_integer[ i ] << ' ';

cout << '\n' << n << " double data:" << endl;
for( i = 0; i < n; i++ )
cout << Array_double[ i ] << ' ';

cout << '\n' << n << " string:" << endl;
for( i = 0; i < n; i++ )
cout << Array_string[ i ] << ' ';

cout << endl;
//输出结束

//delete动态数据成员
delete[] Array_integer;
delete[] Array_double;
delete[] Array_string;

system( "pause" );

return 0;
}
建议下次楼主多给些分吧，毕竟写程序不容易

回答2：

first.cpp
#include
void input(int a[],int n) //输入数据
{
cout<<"**********请输入 "< for(int i=0;i cin>>a[i];
}
int directsort(int a[],int n) //对数组进行直接法排序
{
int t,count=0;
for(int i=0;i {
for(int j=i+1;j {
int k=j;
if(a[j]>a[k])
{
t=a[j];
a[j]=a[k];
a[k]=t;
count++;
}
}
}
cout<<"count="< return count;
}
int insertsort(int a[],int n) //对数组进行插入法排序
{
int count=0;
for(int i=1;i {
int t=a[i];
for(int j=i-1;j>=0&&a[j]>t;j--)
{
a[j+1]=a[j];
count++;
}
a[j+1]=t;
}
cout<<"count="< return count;
}
int shellsort(int a[],int n,int k) //对数组进行shell排序
{
int t,H,count=0;
cout<<"please input a length:";
cin>>k;
if(k>0&&k {
for(H=k;H!=0;H--)
for(int i=0;i+H {
if(a[i]>a[i+H])
{
t=a[i];
a[i]=a[i+H];
a[i+H]=t;
}
count++;
}
}
cout<<"count="< return count;
}
void output(int a[],int n) //输出数据
{
for(int i=0;i cout< cout<}
main.cpp
#include
#include "file.h"
const int N=7; //定义数组长度
void main()
{
int s[N],k=1,x1,x2,x3;
input(s,N); //调用input函数为数组函数输入数据

cout<<"**************欢迎使用直接法、插入法、shell排序算法对数组进行升序排列************"<
x1=directsort(s,N); //调用direct函数进行排序
cout<<"直接排序算法：(降序排列)\n";
output(s,N);

x2=insertsort(s,N); //调用insert函数进行排序
cout<<"插入排序算法：(升序排列)\n";
output(s,N);

x3=shellsort(s,N,k); //调用shell函数进行排序
cout<<"shell排序算法：(升序排列)\n";
output(s,N);

if(x1 cout<<"直接法最优！"< if(x1==x2&&x1 cout<<"直接法、插入法优劣度相同且优于shell法！"< if(x1==x2&&x2==x3)
cout<<"直接法、插入法、shell法优劣度相同！"< if(x1==x3&&x1 cout<<"直接法、shell法优劣度相同且优于插入法！"< if(x2 cout<<"插入法最优！"< if(x2==x3&&x2 cout<<"插入法、shell法优劣度相同且优于直接法！"< if(x3 cout<<"shell法最优！"<}
file.h
void input(int a[],int n); //输入函数原型声明
int directsort(int a[],int n); //直接排序原型声明
int insertsort(int a[],int n); //插入排序原型声明
int shellsort(int a[],int n,int k); //shell排序原型声明
void output(int a[],int n); //输出函数原型声明

回答3：

#include
#include
#include
void shell_sort(int arr[],int size)
{ int i,j,k,temp;
for(i=size/2;i>0;i/=2)
{ for(j=i;j{ temp=arr[j]; for(k=j-i;k>=0&&temp{ arr[k+i]=arr[k]; } arr[k+i]=temp; }
}
/* for(i=0;i{ printf("%d ",arr[i]); }*/
}
void bubble_sort(int arr[],int size)
{ int i,j,k; for(i=size-1;i>0;i=k)
{ for(j=0,k=0;j{ if(arr[j]>arr[j+1])
{ arr[j]^=arr[j+1]^=arr[j]^=arr[j+1]; k=j; }
}
}
/* for(i=0;i{ printf("%d ",arr[i]); }*/ }
void insert_sort(int arr[],int size)
{
int i,j,temp;
for(i=1;i{
temp=arr[i];
for(j=i-1;j>=0&&temp{ arr[j+1]=arr[j]; }
arr[j+1]=temp;
}
/* for(i=0;i}
void select_sort(int arr[],int size)
{
int i,j,min;
for(i=0;i{
min=i; for(j=i+1;j{
if(arr[j]{ min=j;
}
}
if(min!=i)
{ arr[min]^=arr[i]^=arr[min]^=arr[i]; }
}
/* for(i=0;i}
void main()
{
long start_select,end_select,start_insert,end_insert,start_bubble,end_bubble,start_shell,end_shell;
int select[15000],insert[15000],bubble[15000],shell[15000];
int i,j;
srand((int)time(0));
select[0]=rand()%25000+1;
for(i=1;i<15000;i++)
{
select[i]=rand()%25000+1; for(j=0;j{
if(select[i]==select[j])
{
i--;
}
}
} //printf("随机数组：");
for(i=0;i<15000;i++)
{
shell[i]=bubble[i]=insert[i]=select[i];
}
//printf("%d ",shell[i]); } printf("\n");
printf("下面是选择排序：");
start_select=clock();
select_sort(select,15000);
end_select=clock();
printf("\n所用的时间是%ld毫秒\n",(long)(end_select-start_select));
printf("\n下面是插入排序：");
start_insert=clock();
insert_sort(insert,15000);
end_insert=clock();
printf("\n所用的时间是%ld毫秒\n",(long)(end_insert-start_insert));
printf("\n下面是冒泡排序：");
start_bubble=clock();
bubble_sort(bubble,15000);
end_bubble=clock();
printf("\n所用的时间是%ld毫秒\n",(long)(end_bubble-start_bubble));
printf("\n下面是希尔排序：");
start_shell=clock();
shell_sort(shell,15000);
end_shell=clock();
printf("\n所用的时间是%ld毫秒\n",(long)(end_shell-start_shell));
}