Question

关于c++中利用MFC做相关排序，优先等问题！

关于c++中利用MFC做相关排序，优先等问题！
能提供相关代码吗？

Answer 1

我做的课程设计部分代码
能算数据移动的次数
和
花费的时间
冒泡排序，插入排序，快速排序，选择排序，希尔排序，堆排序
/*******
MySortDlg.h
******对话框头文件**/
struct
SORTMSG
//排序信息结构体
{
int
dfTime;
//排序运行时间
int
nMov;
//数据移动次数
};
class
CMySortDlg
:
public
CDialog
{
public:
CMySortDlg(CWnd*
pParent
=
NULL);
//
standard
constructor
private:
void
ShowData(int
*copydata);
//显示数据
void
ShowMsg();
//显示信息
void
CopyData(int
*data,int
*copydata);
//复制数据
int
*data;
//所要排序的数据
int
pos;
//位置标志
SORTMSG
iMsg[6];
//排序信息结构体
……………
}
/******
MySortDlg.cpp
*****对话框源文件*****/
………….
void
CMySortDlg::OnBtnSort()
//排序功能
{
Sort
s;
//排序类对象实例化
int
*copydata=new
int[N];
pos=0;
m_ListNum.DeleteAllItems();//清空列表框
CopyData(data,copydata);
//复制数据
m_ListNum.InsertItem(pos++,"=====原始数据===");
ShowData(copydata);
//显示数据
m_ListNum.InsertItem(pos++,"====冒泡====");
CopyData(data,copydata);
iMsg[0]=s.BubbleSort(copydata,N);
ShowData(copydata);
m_ListNum.InsertItem(pos++,"====插入====");
CopyData(data,copydata);
iMsg[1]=s.InsertSort(copydata,N);
ShowData(copydata);
m_ListNum.InsertItem(pos++,"====快速====");
CopyData(data,copydata);
iMsg[2]=s.QuickSort(copydata,N);
ShowData(copydata);
m_ListNum.InsertItem(pos++,"=====选择====");
CopyData(data,copydata);
iMsg[3]=s.SelectSort(copydata,N);
ShowData(copydata);
m_ListNum.InsertItem(pos++,"====希尔====");
CopyData(data,copydata);
iMsg[4]=s.ShellSort(copydata,N);
ShowData(copydata);
m_ListNum.InsertItem(pos++,"====堆====");
CopyData(data,copydata);
iMsg[5]=s.HeapSort(copydata,N);
ShowData(copydata);
delete
[]copydata;
}
void
CMySortDlg::OnBtnCreatenum()
//产生最坏情况数据
{
m_ListNum.DeleteAllItems();//清空列表框
int
i;
CString
strNum;
for(i=0;i<N;i++)
{
data[i]=N-i;
//一次递减产生数据
strNum.Format("%d",data[i]);
m_ListNum.InsertItem(i,strNum);
//放入列表框
}
}
void
CMySortDlg::OnCancelMode()
{
CDialog::OnCancelMode();
delete
[]data;
//释放内存
}
void
CMySortDlg::CopyData(int
*data,
int
*copydata)//复制数据
{
for(int
i=0;i<N;i++)
{
copydata[i]=data[i];
}
}
void
CMySortDlg::ShowData(int
*copydata)//显示数据
{
CString
strNum;
for(int
i=0;i<N;i++)
{
strNum.Format("%d",copydata[i]);
m_ListNum.InsertItem(pos,strNum);
pos++;
}
}
void
CMySortDlg::OnBtnMsg()
//信息显示
{
CString
str;
GetDlgItem(IDC_BTN_MSG)->GetWindowText(str);//得到控件显示的字符
if(str=="排序信息")
{
GetDlgItem(IDC_LIST_NUM)->ShowWindow(SW_HIDE);
//显示数据，隐藏列表框
GetDlgItem(IDC_BTN_MSG)->SetWindowText("显示数据");
GetDlgItem(IDC_STATIC_STA)->SetWindowText("信息");
GetDlgItem(IDC_STATIC_MSG)->ShowWindow(SW_SHOWNA);
ShowMsg();
}
else
{
GetDlgItem(IDC_LIST_NUM)->ShowWindow(SW_SHOWNA);
//隐藏数据，显示列表框
GetDlgItem(IDC_BTN_MSG)->SetWindowText("排序信息");
GetDlgItem(IDC_STATIC_STA)->SetWindowText("数据");
GetDlgItem(IDC_STATIC_MSG)->ShowWindow(SW_HIDE);
}
}
void
CMySortDlg::OnBtnCrenum()
//产生随机数据
{
m_ListNum.DeleteAllItems();//清空列表框
CString
strNum;
srand((unsigned)time(NULL));//种子
for(int
i=0;i<N;i++)
{
data[i]=rand()%N;
strNum.Format("%d",data[i]);
m_ListNum.InsertItem(i,strNum);
}
}
void
CMySortDlg::ShowMsg()//显示排序信息
{
CString
SortMsg;
CString
strTime;
CString
strMov;
SortMsg+="\t\n";
char
*p1="冒泡",*p2="插入",*p3="快速",*p4="选择",*p5="希尔",*p6="
堆
";
char
*p[]={p1,p2,p3,p4,p5,p6};
for(int
i=0;i<6;i++)
{
SortMsg+=p[i];
strTime.Format("%d",iMsg[i].dfTime);
strMov.Format("%d",iMsg[i].nMov);
SortMsg=SortMsg+"排序花费时间:"+strTime+"微秒
,"
+"数据移动次数
:"
+strMov;
SortMsg+="\t\n";
}
GetDlgItem(IDC_STATIC_MSG)->SetWindowText(SortMsg);
UpdateData(false);
}
/*******
Sort.h
*****排序类头文件***/
const
int
N=
100;//排列大小
class
Sort
{
public:
Sort();
virtual
~Sort();
SORTMSG
InsertSort(int
*pData,int
Count);
//直接插入排序
SORTMSG
BubbleSort(int
*pData,int
Count);
//冒泡排序
SORTMSG
SelectSort(int
*pData,int
Count);
//选择排序
SORTMSG
QuickSort
(int
*pData,int
Count);
//快速排序
SORTMSG
ShellSort
(int
*pData,int
Count);
//希尔排序
SORTMSG
HeapSort
(int
*pData,int
Count);
//堆排序
private:
void
InitMsg();//初始化信息结构体
void
run(int*
pData,int
left,int
right);
void
HeapAdjust(int
*pData,int
s,
int
m);
LARGE_INTEGER
litmp;
//用来计算运行时间
LONGLONG
QPart1,Qpart2;
double
dfMinus,dfFreq;//
SORTMSG
SortMsg;
void
StartTime();//开始计时
void
EndTime();
//结束计时
};
/******
Sort.cpp
****排序类源文件***/
#include
"stdafx.h"
#include
"MySort.h"
#include
"Sort.h"
#include
<ctime>
……….
SORTMSG
Sort::InsertSort(int*
pData,int
Count)
//直接插入排序
{
int
iTemp;
int
iPos;
InitMsg();
StartTime();
for(int
i=1;i<Count;i++)
{
iTemp
=
pData[i];
//改排第i个元素
iPos
=
i-1;
while((iPos>=0)
&&
(iTemp<pData[iPos]))
//如果前面有大于第i个元素的移动
{
pData[iPos+1]
=
pData[iPos];
iPos--;
SortMsg.nMov++;
}
pData[iPos+1]
=
iTemp;
//插入第i个元素
SortMsg.nMov+=2;
}
EndTime();
return
SortMsg;
}
SORTMSG
Sort::BubbleSort(int*
pData,int
Count)
//冒泡排序
{
int
iTemp;
InitMsg();
StartTime();
for(int
i=1;i<Count;i++)
{
for(int
j=Count-1;j>=i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp
=
pData[j-1];
pData[j-1]
=
pData[j];
pData[j]
=
iTemp;
//加一个条件
少循环
SortMsg.nMov+=3;
}
}
}
EndTime();
return
SortMsg;
}
SORTMSG
Sort::SelectSort(int*
pData,int
Count)//选择排序
{
int
iTemp;
int
iPos;
InitMsg();
StartTime();
for(int
i=0;i<Count-1;i++)
{
iTemp
=
pData[i];
iPos
=
i;
for(int
j=i+1;j<Count;j++)//找最小的
{
if(pData[j]<iTemp)
{
iTemp
=
pData[j];
iPos
=
j;
SortMsg.nMov++;
}
}
pData[iPos]
=
pData[i];//交换
pData[i]
=
iTemp;
SortMsg.nMov+=3;
}
EndTime();
return
SortMsg;
}
void
Sort::run(int*
pData,int
left,int
right)
{
int
i,j;
int
middle,iTemp;
i
=
left;
j
=
right;
middle
=
pData[(left+right)/2];
//求中间值
do{
while((pData[i]<middle)
&&
(i<right))//从左扫描大于中值的数
i++;
while((pData[j]>middle)
&&
(j>left))//从右扫描大于中值的数
j--;
if(i<=j)//找到了一对值
{
//交换
iTemp
=
pData[i];
pData[i]
=
pData[j];
pData[j]
=
iTemp;
i++;
j--;
SortMsg.nMov+=3;
}
}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left<j)，递归左半边
if(left<j)
run(pData,left,j);
//当右边部分有值(right>i)，递归右半边
if(right>i)
run(pData,i,right);
}
SORTMSG
Sort::QuickSort(int*
pData,int
Count)//快速排序
{
InitMsg();
StartTime();
run(pData,0,Count-1);
EndTime();
return
SortMsg;
}
SORTMSG
Sort::ShellSort(int*
pData,int
Count)//希尔排序
{
int
step[4]={9,5,3,1};
int
k,s,w,iTemp;
InitMsg();
StartTime();
for(int
i=0;i<4;i++)
{
k
=
step[i];
s
=
-k;
for(int
j=k;j<Count;j++)
{
iTemp
=
pData[j];
w
=
j-k;//求上step个元素的下标
if(s
==0)
{
s
=
-k;
s++;
pData[s]
=
iTemp;
SortMsg.nMov++;
}
while((iTemp<pData[w])
&&
(w>=0)
&&
(w<=Count))
{
pData[w+k]
=
pData[w];
w
=
w-k;
SortMsg.nMov++;
}
pData[w+k]
=
iTemp;
SortMsg.nMov+=2;
}
}
EndTime();
return
SortMsg;
}
void
Sort::HeapAdjust(int
*pData,int
s,
int
m)
{
int
rc;
int
j;
rc=pData[s];
for(j=2*s;j<=m;j*=2)
{
/*
沿key较大的孩子结点向下筛选
*/
if(j<m&&(pData[j]<(pData[j+1])))
++j;
/*
j为key较大的记录的下标
*/
if(!(rc<pData[j]))
break;
/*
rc应插入在位置s上
*/
pData[s]=pData[j];
s=j;
SortMsg.nMov++;
}
pData[s]=rc;
/*
插入
*/
SortMsg.nMov+=2;
}
SORTMSG
Sort::HeapSort(int
*pData,int
Count)//堆排序
{
int
t;
int
i;
InitMsg();
StartTime();
for(i=(Count-1)/2;i>=0;--i)
/*
把H.r[1..H.length]建成大顶堆
*/
HeapAdjust(pData,i,Count-1);
for(i=Count-1;i>0;--i)
{
/*
将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换
*/
t=pData[0];
pData[0]=pData[i];
pData[i]=t;
HeapAdjust(pData,0,i-1);
/*
将H.r[1..i-1]重新调整为大顶堆
*/
SortMsg.nMov+=3;
}
EndTime();
return
SortMsg;
}
void
Sort::StartTime()
//开始计时
{
//获得计时器的时钟频率
QueryPerformanceFrequency(&litmp);
dfFreq
=
(double)litmp.QuadPart;
QueryPerformanceCounter(&litmp);
QPart1
=
litmp.QuadPart;
//开始计时
};
void
Sort::EndTime()//结束计时
{
double
dETime;
QueryPerformanceCounter(&litmp);
Qpart2
=
litmp.QuadPart;
//终止计时
dfMinus
=
(double)(Qpart2
-
QPart1);//计算计数器值
dETime=
dfMinus
/
dfFreq;//获得对应时间，单位为秒
SortMsg.dfTime=dETime*1000000;
};