C/C++ 排序算法演示程序
排序算法演示程序
灵感：B站http://www.bilibili.com/video/av1039639/
/*
** 0 = 黑色√ 8 = 灰色
** 1 = 蓝色 9 = 淡蓝色
** 2 = 绿色 10 = 淡绿色
** 3 = 浅绿色 11 = 淡浅绿色
** 4 = 红色 12 = 淡红色√
** 5 = 紫色 13 = 淡紫色
** 6 = 黄色 14 = 淡黄色√
** 7 = 白色 15 = 亮白色√
*/
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <conio.h>
#include <windows.h>
using namespace std;
const int M=1000,N=20,T=200;
void SetColor(unsigned short ForeColor,unsigned short BackGroundColor)//定义函数
{HANDLE hCon=GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hCon,(ForeColor%16)|(BackGroundColor%16*16));}
class data{
private:
int a[N];//数据
int sort;
int change;//交换次数
int compare;//比较次数
public:
data(int s);//初始化
void print(int x=-1,int y=-1,int z=-1);//打印
void bsort();//冒泡排序
void dbsort();//双向冒泡
void isort();//插入排序
void ssort();//选择排序
int qsort(int m,int n);//快速排序
void rsort();//基数排序
void shell();//希尔排序
void monkey();
};
void data::monkey()
{
int t1,t2,temp,f=0,i;
char c;
srand(time(0));
do{
t1=rand()%N;
t2=rand()%N;
f=0;
compare++;
if((t1>t2 && a[t1]<a[t2]) || (t1<t2 && a[t1]>a[t2]))
{
change++;
temp=a[t1];
a[t1]=a[t2];
a[t2]=temp;
}
print(t1,t2);
SetColor(15,0);
cout<<"按空格键结束排序。。。"<<endl;
Beep(a[t1],T);
Sleep(T);
for(i=0;i<N-1;i++)
{
if(a[i]>a[i+1])f=1;
}
if(kbhit())c=getch();
}while(f!=0 && c!=' ');
}
void data::shell()
{
int d,i,j,temp;
for(d=5;d>=1;d--)
{
for(i=0;i<N;i+=d)
{
for(j=i;j>0;j-=d)
{
print(j,i);
compare++;
if(a[j]<a[j-d])
{
change++;
temp=a[j];
a[j]=a[j-d];
a[j-d]=temp;
Beep(a[j],T);
Sleep(T);
}
else
{
Beep(a[j],T);
Sleep(T);
break;
}
}
}
}
}
void data::rsort()
{
int temp[10][N]={0},sum=0,i,j,k,l,m,n;
for(i=0;i<=N/10;i++)
{
for(j=0;j<N;j++)
{
if(j<N)
{
m=int((a[j])/pow(10,i))%10;
compare++;
temp[m][0]++;
temp[m][temp[m][0]]=a[j];
print(j);
SetColor(15,0);
cout<<"缓存数据："<<endl;
for(l=0;l<10;l++)
{
cout<<l<<"号桶："<<temp[l][0]<<"个数据\t";
for(k=1;k<=temp[l][0];k++)
{
cout<<temp[l][k]<<"\t";
}
cout<<endl;
}
Beep(a[j],T);
Sleep(T);
}
}
for(j=0;j<10;j++)
{
for(k=1;k<=temp[j][0];k++)
{
change++;
a[sum+k-1]=temp[j][k];
print(sum+k);
SetColor(15,0);
cout<<"缓存数据："<<endl;
for(l=0;l<10;l++)
{
cout<<l<<"号桶："<<temp[l][0]<<"个数据\t";
for(n=1;n<=temp[l][0];n++)
{
cout<<temp[l][n]<<"\t";
}
cout<<endl;
}
Beep(a[sum+k],T);
Sleep(T);
}
sum=sum+temp[j][0];
}
print();
SetColor(15,0);
cout<<"正在清理缓存。。。"<<endl;
Sleep(T);
for(j=0;j<N;j++)
{
for(k=0;k<10;k++)temp[k][j]=0;
}
sum=0;
}
}
data::data(int s)
{
change=0;
compare=0;
srand(time(0));
this->sort=s;
for(int i=0;i<N;i++)
{
a[i]=rand()%M;
}
}
void data::print(int x,int y,int z)
{
int i,j,f;
system("cls");
SetColor(15,0);
switch(sort)
{
case 1:cout<<"冒泡排序\t";break;
case 2:cout<<"双向冒泡\t";break;
case 3:cout<<"插入排序\t";break;
case 4:cout<<"选择排序\t";break;
case 5:cout<<"快速排序\t";break;
case 6:cout<<"基数排序\t";break;
case 7:cout<<"希尔排序\t";break;
case 8:cout<<"猴子排序\t";break;
}
cout<<N<<"个数据"<<"\t比较："<<compare<<"次\t交换："<<change<<"次"<<endl;
for(j=9;j>=0;j--)
{
for(i=0;i<N;i++)
{
if(i==x)SetColor(12,0);
else if(i==y || i==z)SetColor(10,0);
else if(x==-1)SetColor(10,0);
else SetColor(15,0);
f=(float)a[i]/M*1.0*100;
switch(int(f)-10*j)
{
case 0:printf(" ");break;
case 1:printf(" ▁ ");break;
case 2:printf(" ▂ ");break;
case 3:printf(" ▃ ");break;
case 4:printf(" ▃ ");break;
case 5:printf(" ▄ ");break;
case 6:printf(" ▅ ");break;
case 7:printf(" ▆ ");break;
case 8:printf(" ▇ ");break;
case 9:printf(" █ ");break;
default:
if(f-10*j>0)printf(" █ ");
else printf(" ");
}
}
cout<<endl;
}
for(i=0;i<N;i++)
{
if(i==x)SetColor(12,0);
else if(i==y || i==z)SetColor(10,0);
else if(x==-1)SetColor(10,0);
else SetColor(15,0);
printf(" %03d",a[i]);
}
cout<<endl;
}
int data::qsort(int m,int n)
{
int mid,i,j,temp;
if(n-m>0)
{
mid=m;
for(i=m;i<=n;i++)
{
compare++;
if(a[i]<a[mid])
{
change++;
temp=a[i];
for(j=i;j>m;j--)
{
a[j]=a[j-1];
}
a[m]=temp;
mid++;
print(mid,m,n);
Beep(a[j],T);
Sleep(T);
}
}
print(mid,m,n);
Beep(a[mid],T);
Sleep(T);
if(m!=mid)qsort(m,mid);
if(mid+1!=n)qsort(mid+1,n);
return 0;
}
else return 0;
}
void data::isort()
{
int i,j,temp;
for(i=0;i<N;i++)
{
for(j=i;j>0;j--)
{
print(j,i);
compare++;
if(a[j]<a[j-1])
{
change++;
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
Beep(a[j],T);
Sleep(T);
}
else
{
Beep(a[j],T);
Sleep(T);
break;
}
}
}
}
void data::ssort()
{
int i,j,temp,min;
for(i=0;i<N;i++)
{
min=i;
for(j=i;j<N;j++)
{
print(j,i);
compare++;
if(a[min]>a[j])
{
min=j;
}
Beep(a[j],T);
Sleep(T);
}
change++;
temp=a[min];
a[min]=a[i];
a[i]=temp;
}
}
void data::bsort()
{
int i,j,temp;
for(i=0;i<N;i++)
{
for(j=0;j<N-i-1;j++)
{
print(j,N-i);
compare++;
if(a[j]>a[j+1])
{
change++;
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
Beep(a[j],T);
Sleep(T);
}
}
}
void data::dbsort()
{
int i,j=0,temp;
for(i=0;i<N;i++)
{
for(;j<N-i-1;j++)
{
print(j,i-1,N-i);
compare++;
if(a[j]>a[j+1])
{
change++;
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
Beep(a[j],T);
Sleep(T);
}
for(;j>i;j--)
{
print(j,i-1,N-i-1);
compare++;
if(a[j]<a[j-1])
{
change++;
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
Beep(a[j],T);
Sleep(T);
}
}
}
int main()
{
char c;
while(1)
{
system("cls");
SetColor(14,0);
cout<<"排序算法演示程序：\n请选择需要演示的算法\n"<<endl;
cout<<"1、冒泡排序\n2、双向冒泡\n3、插入排序\n4、选择排序\n5、快速排序\n6、基数排序\n7、希尔排序\n8、猴子排序\n0、退出程序"<<endl;
cin>>c;
data d(c-48);
switch(c)
{
case '1':d.bsort();break;
case '2':d.dbsort();break;
case '3':d.isort();break;
case '4':d.ssort();break;
case '5':d.qsort(0,N-1);break;
case '6':d.rsort();break;
case '7':d.shell();break;
case '8':d.monkey();break;
case '0':exit(0);
}
d.print();
SetColor(14,0);
system("pause");
}
return 0;
}
