闲来无事，放分 ＋ 算法（CListCtrl的排序算法）。
加班了两个月，好不容易轻松下来。来和大家讨论一下今天用CListCtrl的小发现：
对列表控件中的项目进行排序。10条记录用“冒泡”的话要做45次比较；但CListCtrl只做了22次（根据我的数据测试），疑似“二分”法快排！ 正在分析它的算法细节。有兴趣或知情的朋友能否说说你们的看法？
呵呵，祝大家周末愉快。
[解决办法]
jf ding
[解决办法]
周末愉快，请上分
[解决办法]
不清楚windows用的什么算法，但不是冒泡就是了。。。
[解决办法]
应该是二分法吧，VCL也是二分法啊。M$那么多人，写个二分法不会有问题吧。
以上纯属瞎猜。
[解决办法]
用高低2叉树的结构,高的值永远在左边,低的值永远在右,这样放的话查找起来很节省
[解决办法]
还真没研究过，晚上看看它的代码
[解决办法]
它可能直接使用qsort函数了
[解决办法]
嗯，学习了
[解决办法]
up!
[解决办法]
这个……泄漏代码和盗版还是有区别的吧？不过微软已经公开了2k3 server的kernel source（仅限于kernel）。我也去不了MRA，不是搞理论的。我们宿舍有俩哥们一个在MS一个在Google，人家那是做图形算法和文本挖掘的……
[解决办法]
呵呵，大家七夕愉快哦
[解决办法]
作为产品嘛，还是成熟，稳定最重要。何况一个简单的列表控件排序，用得着搞什么特别复杂的算法吗？log级别的足够了。新概念基本上都在微软研究院里面。
-----------------------
无论上面哪种排序算法，都不可能达到O(logN)级别，事实上，不采取分段选择不同算法的策略，单一排序算法的话，极限时间级别也就O(NlogN），而且暂时没有算法能稳定的达到这个时间。
[解决办法]
学习，接分
[解决办法]
顶上去..
[解决办法]
UP
[解决办法]
MARK
[解决办法]
mark too!
[解决办法]
我自己封装的个类,发给你哈.
CSortList::CSortList(CImageRetrievalView* pv)
{
m_bAsc= TRUE;
//this-> m_nSortedCol = -1;
CreateSortIcons();
//GetHeaderCtrl()-> SetImageList(&m_imglstSortIcons);
pView = pv;
}
CSortList::~CSortList(void)
{
m_imglstSortIcons.DeleteImageList();
m_bmpUpArrow.DeleteObject();
m_bmpDownArrow.DeleteObject();
}
//IMPLEMENT_DYNCREATE(CsercurityView, CFormView)
BEGIN_MESSAGE_MAP(CSortList, CListCtrl)
ON_NOTIFY_REFLECT(LVN_COLUMNCLICK, OnLvnColumnclick)
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CSortList message handlers
void CSortList::OnLvnColumnclick(NMHDR *pNMHDR, LRESULT *pResult)
{
LPNMLISTVIEW pNMListView = reinterpret_cast <LPNMLISTVIEW> (pNMHDR);
// TODO: Add your control notification handler code here
//NM_LISTVIEW* pNMListView = (NM_LISTVIEW*)pNMHDR;
if( pNMListView-> iSubItem == m_nSortedCol )
m_bAsc = !m_bAsc;
else
{
m_bAsc = FALSE;
m_nSortedCol = pNMListView-> iSubItem;
}
SortItems( ListCompare, (DWORD)this );
SetSortIcon();
for (int i=0;i <this-> GetItemCount();i++)
this-> SetItemData(i, i);
pView-> Invalidate();
*pResult = 0;
}
void CSortList::CreateSortIcons()
{
if (!m_imglstSortIcons.m_hImageList)
{
COLORMAP cm = {RGB(0, 0, 0), GetSysColor(COLOR_GRAYTEXT)};
m_imglstSortIcons.Create (9, 5, ILC_COLOR24 | ILC_MASK, 2, 0);
m_bmpUpArrow.LoadMappedBitmap(IDB_HDRUP, 0, &cm, 1);
m_nUpArrow = m_imglstSortIcons.Add(&m_bmpUpArrow, RGB(255, 255, 255));
m_bmpDownArrow.LoadMappedBitmap(IDB_HDRDOWN, 0, &cm, 1);
m_nDownArrow = m_imglstSortIcons.Add(&m_bmpDownArrow, RGB(255, 255, 255));
}
}
void CSortList::SetSortIcon()
{
CHeaderCtrl* pHeaderCtrl = this-> GetHeaderCtrl();
ASSERT(pHeaderCtrl);
pHeaderCtrl-> SetImageList(&m_imglstSortIcons);
for( int col = 0; col < GetHeaderCtrl()-> GetItemCount(); col++ )
{
HDITEM hdrItem = { 0,};
hdrItem.mask = HDI_FORMAT | HDI_IMAGE;
BOOL ret = pHeaderCtrl-> GetItem(col-1, &hdrItem);
ret = pHeaderCtrl-> GetItem(col+1, &hdrItem);
ret = pHeaderCtrl-> GetItem(col, &hdrItem);
if ( m_nSortedCol == col)
{
hdrItem.fmt = hdrItem.fmt & HDF_JUSTIFYMASK | HDF_IMAGE | HDF_STRING | HDF_BITMAP_ON_RIGHT;
if( m_bAsc )
hdrItem.iImage = m_nUpArrow;
else
hdrItem.iImage = m_nDownArrow;
}
else
{
hdrItem.fmt = hdrItem.fmt & HDF_JUSTIFYMASK | HDF_STRING;
}
pHeaderCtrl-> SetItem(col, &hdrItem);
}
}
bool CSortList::GetFullRowSelect()
{
return ( GetExtendedStyle()&LVS_EX_FULLROWSELECT) == LVS_EX_FULLROWSELECT;
}
void CSortList::SetFullRowSelect( bool bFullRowSelect )
{
if( bFullRowSelect )
SetExtendedStyle( GetExtendedStyle()|LVS_EX_FULLROWSELECT );
else
SetExtendedStyle( GetExtendedStyle()&(~LVS_EX_FULLROWSELECT) );
}
bool CSortList::GetGridLines()
{
return ( GetExtendedStyle() & LVS_EX_GRIDLINES ) == LVS_EX_GRIDLINES;
}
void CSortList::SetGridLines( bool bGridLines )
{
if( bGridLines )
SetExtendedStyle( GetExtendedStyle()|LVS_EX_GRIDLINES );
else
SetExtendedStyle( GetExtendedStyle()&(~LVS_EX_GRIDLINES) );
}
int CALLBACK CSortList::ListCompare(LPARAM lParam1, LPARAM lParam2, LPARAM lParamSort)
{
CSortList* pList=(CSortList*)lParamSort;
int nItem1, nItem2;
LVFINDINFO FindInfo;
FindInfo.flags = LVFI_PARAM; // 指定查找方式
FindInfo.lParam = lParam1;
nItem1 = pList-> FindItem(&FindInfo, -1); // 得到对应Item索引
FindInfo.lParam = lParam2;
nItem2 = pList-> FindItem(&FindInfo, -1);
if((nItem1 == -1) || (nItem2 == -1))
{
TRACE( "无法找到!\n ");
return 0;
}
CString Str1,Str2;
Str1 = pList-> GetItemText(nItem1, pList-> m_nSortedCol); // 得到排序列的Text
Str2 = pList-> GetItemText(nItem2, pList-> m_nSortedCol);
int iCompRes = 0;
if(Str1 > Str2)
iCompRes = 1;
else if(Str1 == Str2)
iCompRes = 0;
else
iCompRes = -1;
if(pList-> m_bAsc)
return iCompRes;
else
return iCompRes*-1;
return 0;
}
[解决办法]
有好的排序算法为什么还要用冒泡呢
[解决办法]
接分
------解决方案--------------------
接分愉快..
[解决办法]
一般都用二分法。。。
.Net平台上很多排序都是用二分法（参见msdn）
[解决办法]
有必要在用户界面层讲究排序性能么？数据量大的话我都是直接上数据库取排好了的数据
[解决办法]
mark.sorry.
[解决办法]
mark
[解决办法]
mark
[解决办法]
mark
[解决办法]
JF
GOOD LUCK!
[解决办法]
路过，学习
[解决办法]
学学学，接接接
