mfcdlg.cpp

六种排序算法的比较 冒泡排序

{
	// TODO: Add your control notification handler code here
	Rand_Biao = 0;
	m_list.DeleteAllItems();
	m_compare = _T("");
	m_change = _T("");
	m_compare1 = _T("");
	m_change1 = _T("");
	m_compare2 = _T("");
	m_change2 = _T("");
	UpdateData(false);
}

void CMFCDlg::OnSelectsort() 
{
	// TODO: Add your control notification handler code here
	int temp, kk;

	if(Rand_Biao==0)
	{
		MessageBox("请先产生随机数!");
	}
	else
		m_list.SetTextBkColor(RGB(200,255,200));
	for(kk = 0;kk < 3;kk++)
	{
		result[kk][0][2] = 0;
		result[kk][1][2] = 0;
	}
	for(kk = 0;kk < 3&&Rand_Biao!=0;kk++)
	{
		temp1 = Arrary[kk];
		arrary = new int[max];
		Copy(temp1,arrary,max);
		int i = 0;
		for(i = 0;i < max - 1;i++)
		{
			int min = i;
			int j = 0 ;
		    for(j = i;j < max;j++)
			{
			    result[kk][0][2]+=2;
			    if(arrary[min] > arrary[j])
				min = j;
			}
		    if(i!=min)
			{
		    	result[kk][1][2]++;
		    	temp = arrary[i];
		    	arrary[i] = arrary[min];
		    	arrary[min] = temp;
			}
		}
		for(i = 0 ; i < max;i++)
		{
		aa.Format("%d",arrary[i]);
		m_list.Update(i);
		m_list.SetItemText(i,2*(kk+1),aa);
		}
	}
	m_compare.Format("%d", result[0][0][2]);
	m_change.Format("%d", result[0][1][2]);
	m_compare1.Format("%d",result[1][0][2]);
	m_change1.Format("%d",result[1][1][2]);
    m_compare2.Format("%d",result[2][0][2]);
	m_change2.Format("%d",result[2][1][2]);
	UpdateData(false);
}

void CMFCDlg::OnBubblesort() 
{
	// TODO: Add your control notification handler code here
    if(Rand_Biao==0)
	{
		MessageBox("请先产生随机数!");
	}
	else
		m_list.SetTextBkColor(RGB(200,255,255));
	bool change = true;
	int temp,kk;
	for(kk = 0;kk < 3;kk++)
	{
		result[kk][0][3] = 0;
		result[kk][1][3] = 0;
	}

	for(kk = 0;kk < 3&&Rand_Biao!=0;kk++)
	{
		change = true;
		temp1 = Arrary[kk];
		arrary = new int[max];
		Copy(temp1,arrary,max);
		int i = 0;
	    for(i=max-1;i >=1 &&change;i--)
		{
			
		    result[kk][0][3]++;
		    change = false;
		    for(int j = 0;j < i;j++)
			{
		    	result[kk][0][3]+=2;
		    	if(arrary[j] > arrary[j+1])
				{
		    		result[kk][1][3]++;
			    	temp = arrary[j];
		    		arrary[j] = arrary[j+1];
			    	arrary[j+1] = temp;
		    		change = true;
				}
			}
		}
	    for(i = 0 ; i < max;i++)
		{
			m_list.Update(i);
		    aa.Format("%d",arrary[i]);
		    m_list.SetItemText(i,2*(kk+1),aa);
		}
	}
	m_compare.Format("%d", result[0][0][3]);
	m_change.Format("%d", result[0][1][3]);
	m_compare1.Format("%d",result[1][0][3]);
	m_change1.Format("%d",result[1][1][3]);
    m_compare2.Format("%d",result[2][0][3]);
	m_change2.Format("%d",result[2][1][3]);
	UpdateData(false);
	
}
void CMFCDlg::ShellInsert(int *temp,int n,int dk,int *compare)
{
	for(int i = dk + 1;i < n + 1; i++)
	{
		compare[0]+=2;
		if(temp[i] < temp[i - dk])
		{
			compare[1]++;
			temp[0] = temp[i];
		    for(int j = i - dk;j > 0&&temp[0] < temp[j];j-=dk)
			{
				compare[0]+=2;
			    temp[j+dk] = temp[j];
			    temp[j] = temp[0];
			}
		}
	
		
	}
}

void CMFCDlg::OnShellsort() 
{
	// TODO: Add your control notification handler code here
	int *temp;
	if(Rand_Biao==0)
	{
		MessageBox("请先产生随机数!");
	}
	else
		m_list.SetTextBkColor(RGB(255,200,200));
	int kk = 0;
	for(kk = 0;kk < 3;kk++)
	{
		result[kk][0][4] = 0;
		result[kk][1][4] = 0;
	}
	
	for( kk = 0; kk < 3&&Rand_Biao!=0;kk++)
	{
		compare[0] = 0;
		compare[1] = 0;
		arrary = new int[max];
		temp1 = Arrary[kk];
		Copy(temp1,arrary,max);
		temp = new int[max+1];
		temp[0] = 0;
		int i = 0;
        for(i = 1;i <= max;i++)
		{
		temp[i] = arrary[i-1];
		}
		int k = 0;
		for(k = max/2; k >= 1 ;k-=2)
		{
	    	compare[0]++;
    		ShellInsert(temp,max,k,compare);
		}
	    for(i = 0;i < max;i++)
	    	arrary[i] = temp[i+1];
		result[kk][0][4] = compare[0];
		result[kk][1][4] = compare[1];
		for(i = 0 ; i < max;i++)
		{
			m_list.Update(i);
		    aa.Format("%d",arrary[i]);
		    m_list.SetItemText(i,2*(kk+1),aa);
		}
	}
	m_compare.Format("%d", result[0][0][4]);
	m_change.Format("%d", result[0][1][4]);
	m_compare1.Format("%d",result[1][0][4]);
	m_change1.Format("%d",result[1][1][4]);
    m_compare2.Format("%d",result[2][0][4]);
	m_change2.Format("%d",result[2][1][4]);
	UpdateData(false);
}
int CMFCDlg::Partition(int *arrary,int n,int low,int high,int *compare)
{
	int pivotkey;
	arrary[0] = arrary[low];
	pivotkey = arrary[low];
	while(low < high)
	{
		compare[0]++;
		while(low < high&&arrary[high]>=pivotkey)
		{
			compare[0]+=2;
			high--;
		}
		arrary[low] = arrary[high];
		while(low < high&&arrary[low]<=pivotkey)
		{
			compare[0]+=2;
			low++;
		}
		arrary[high] = arrary[low];
		compare[1]++;
	}
    arrary[low] = arrary[0];
	return low;
}

void CMFCDlg::QSort(int *arrary,int n,int low,int high,int *compare)
{
	int pivotloc;
	if(low < high)
	{
		compare[0]++;
		pivotloc = Partition(arrary,n,low,high,compare);
		QSort(arrary,n,low,pivotloc-1,compare);
		QSort(arrary,n,pivotloc+1,high,compare);
	}
}
void CMFCDlg::OnQuicksort() 
{
	// TODO: Add your control notification handler code here
	int *temp;
	if(Rand_Biao==0)
	{
		MessageBox("请先产生随机数!");
	}
	else
		m_list.SetTextBkColor(RGB(255,200,255));
	int kk = 0;
	for(kk = 0;kk < 3;kk++)
	{
		result[kk][0][5] = 0;
		result[kk][1][5] = 0;
	}
    for( kk = 0; kk < 3&&Rand_Biao!=0;kk++)
	{
		compare[0] = 0;
		compare[1] = 0;
		arrary = new int[max];
		temp1 = Arrary[kk];
		Copy(temp1,arrary,max);
        temp = new int[max+1];
	    temp[0] = 0;
		int i = 1;
	    for(i = 1;i < max+1;i++)
		{
		    temp[i] = arrary[i-1];
		}
	    QSort(temp,max,1,max,compare);
        for(i = 0;i < max;i++)
	    	arrary[i] = temp[i+1];
	    for(i = 0 ; i < max;i++)
		{
			m_list.Update(i);
	    	aa.Format("%d",arrary[i]);
	    	m_list.SetItemText(i,2*(kk+1),aa);
		}
		result[kk][0][5] = compare[0];
		result[kk][1][5] = compare[1];
		
	}
	m_compare.Format("%d", result[0][0][5]);
	m_change.Format("%d", result[0][1][5]);
	m_compare1.Format("%d",result[1][0][5]);
	m_change1.Format("%d",result[1][1][5]);
    m_compare2.Format("%d",result[2][0][5]);
	m_change2.Format("%d",result[2][1][5]);
	UpdateData(false);
}

void CMFCDlg::HeapAdjust(int *arrary,int n,int s,int m,int *compare)
{
	int tt;
	for(int j = 2*s;j <= m;j*=2)
	{
		compare[0]+=2;
		if(j < m&&arrary[j]>arrary[j+1])j++;//j为较小记录的下标
		if(arrary[j] < arrary[s])//这里自己修改了
		{
			compare[0]++;
			compare[1]++;
			tt = arrary[j];
			arrary[j] = arrary[s];
			arrary[s] = tt;
		}
		s = j;
	}
}

void CMFCDlg::OnHeapsort() 
{
	// TODO: Add your control notification handler code here
	int *temp;
	if(Rand_Biao==0)
	{
		MessageBox("请先产生随机数!");
	}
	else
		m_list.SetTextBkColor(RGB(255,255,200));
	int kk = 0;
	for(kk = 0;kk < 3;kk++)
	{
		result[kk][0][6] = 0;
		result[kk][1][6] = 0;
	}
    for( kk = 0; kk < 3&&Rand_Biao!=0;kk++)
	{
		compare[0] = 0;
		compare[1] = 0;
		arrary = new int[max];
		temp1 = Arrary[kk];
		Copy(temp1,arrary,max);
        temp = new int[max+1];
	    temp[0] = 0;
		int i = 1;
	    for(i = 1;i < max+1;i++)
		{
		    temp[i] = arrary[i-1];
		}
		int t;
    	for(i = max/2;i > 0;i--)
		{
    		compare[0]++;
    		HeapAdjust(temp,max,i,max,compare);//建成大顶堆
		}
    	for(i = max;i > 1; i--)
		{
    		compare[0]++;
    		compare[1]++;
    	 	t = temp[1];
    		temp[1] = temp[i];
    		temp[i] = t;
    		HeapAdjust(temp,max,1,i-1,compare);
		}
    	for(i = 0;i < max;i++)//数据恢复
	    	arrary[i] = temp[i+1];
    	//把结果从大到小变为由小到大
     	for(i = 0;i < max/2;i++)
		{
	    	t = arrary[i];
    		arrary[i] = arrary[max-1-i];
    		arrary[max-1-i] = t;
		}
		for(i = 0 ; i < max;i++)
		{
	    	aa.Format("%d",arrary[i]);
			m_list.Update(i);
	    	m_list.SetItemText(i,2*(kk+1),aa);
		}
		result[kk][0][6] = compare[0];
		result[kk][1][6] = compare[1];
	}
	m_compare.Format("%d", result[0][0][6]);
	m_change.Format("%d", result[0][1][6]);
	m_compare1.Format("%d",result[1][0][6]);
	m_change1.Format("%d",result[1][1][6]);
    m_compare2.Format("%d",result[2][0][6]);
	m_change2.Format("%d",result[2][1][6]);
	UpdateData(false);
}