C/C++ 排序算法演示程序
排序算法演示程序
靈感：B站http://www.bilibili.com/video/av1039639/
?/*
** ? ?0 = 黑色√ ? ? 8 = 灰色
** ? ?1 = 藍(lán)色 ? ? ? 9 = 淡藍(lán)色
** ? ?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)//定義函數(shù)
{HANDLE hCon=GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hCon,(ForeColor%16)|(BackGroundColor%16*16));}
class data{
private:
? ? int a[N];//數(shù)據(jù)
int sort;
int change;//交換次數(shù)
int compare;//比較次數(shù)
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();//基數(shù)排序
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<<"按空格鍵結(jié)束排序。。。"<<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<<"緩存數(shù)據(jù)："<<endl;
for(l=0;l<10;l++)
{
cout<<l<<"號桶："<<temp[l][0]<<"個(gè)數(shù)據(jù)\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<<"緩存數(shù)據(jù)："<<endl;
for(l=0;l<10;l++)
{
cout<<l<<"號桶："<<temp[l][0]<<"個(gè)數(shù)據(jù)\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<<"基數(shù)排序\t";break;
case 7:cout<<"希爾排序\t";break;
case 8:cout<<"猴子排序\t";break;
? ? }
cout<<N<<"個(gè)數(shù)據(jù)"<<"\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、基數(shù)排序\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;
}
