sortdlg.cpp

各种排序算法

// SortDlg.cpp : implementation file
//

#include "stdafx.h"
#include "Sort.h"
#include "SortDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

using namespace std;		//vector的所在的命名空间

/////////////////////////////////////////////////////////////////////////////
// CSortDlg dialog

CSortDlg::CSortDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CSortDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CSortDlg)
	m_Count = 0;
	m_Array = _T("");
	m_Result = _T("");
	m_ResultInsertSort = _T("");
	m_ResultBubbleSort = _T("");
	m_ResultBinaryInsertSort = _T("");
	m_ResultSelectSort = _T("");
	m_ResultShellSort = _T("");
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CSortDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CSortDlg)
	DDX_Control(pDX, IDC_CHECK_SHELL_SORT, m_ShellSortCheck);
	DDX_Control(pDX, IDC_CHECK_SELECT_SORT, m_SelectSortCheck);
	DDX_Control(pDX, IDC_CHECK_BINARY_INSERT_SORT, m_BinaryInsertSortCheck);
	DDX_Control(pDX, IDC_CHECK_BUBBLE_SORT, m_BubbleSortCheck);
	DDX_Control(pDX, IDC_CHECK_INSERT_SORT, m_InsertSortCheck);
	DDX_Text(pDX, IDC_EDIT_COUNT, m_Count);
	DDX_Text(pDX, IDC_EDIT_ARRAY, m_Array);
	DDX_Text(pDX, IDC_EDIT_RESULT, m_Result);
	DDX_Text(pDX, IDC_EDIT_INSERT_SORT, m_ResultInsertSort);
	DDX_Text(pDX, IDC_EDIT_BUBBLE_SORT, m_ResultBubbleSort);
	DDX_Text(pDX, IDC_EDIT_BINARY_INSERT_SORT, m_ResultBinaryInsertSort);
	DDX_Text(pDX, IDC_EDIT_SELECT_SORT, m_ResultSelectSort);
	DDX_Text(pDX, IDC_EDIT_SHELL_SORT, m_ResultShellSort);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CSortDlg, CDialog)
	//{{AFX_MSG_MAP(CSortDlg)
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BUTTON_START, OnButtonStart)
	ON_BN_CLICKED(IDC_CHECK_INSERT_SORT, OnCheckInsertSort)
	ON_BN_CLICKED(IDC_CHECK_BUBBLE_SORT, OnCheckBubbleSort)
	ON_BN_CLICKED(IDC_CHECK_BINARY_INSERT_SORT, OnCheckBinaryInsertSort)
	ON_BN_CLICKED(IDC_CHECK_SELECT_SORT, OnCheckSelectSort)
	ON_BN_CLICKED(IDC_CHECK_SHELL_SORT, OnCheckShellSort)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CSortDlg message handlers

BOOL CSortDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon

	UpdateData(FALSE);			//将类成员变量中的数据传送到窗口中去
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CSortDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CSortDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CSortDlg::clear()
{
	//将各个check box置为未选中
	m_InsertSortCheck.SetCheck(0);
	m_ShellSortCheck.SetCheck(0);
	m_SelectSortCheck.SetCheck(0);
	m_BinaryInsertSortCheck.SetCheck(0);
	m_BubbleSortCheck.SetCheck(0);
	//将各个排序输出置为空
	m_ResultInsertSort.Empty();
	m_ResultShellSort.Empty();
	m_ResultSelectSort.Empty();
	m_ResultBinaryInsertSort.Empty();
	m_ResultBubbleSort.Empty();
}

void CSortDlg::OnButtonStart() 
{
	clear();
	UpdateData(TRUE);		//将窗口中的数据传送到的类成员变量中去
	
	if (m_Array.IsEmpty())//如果没有输入
	{
		AfxMessageBox(_T("请输入需要排序的数组元素"), MB_ICONINFORMATION|MB_OK);
		clear();
		UpdateData(FALSE);
	}
	else if(!isNum(m_Array))//输入非法字符
	{
		AfxMessageBox(_T("请输入合法数字"), MB_ICONINFORMATION|MB_OK);
		clear();
		UpdateData(FALSE);
	}
	else
	{
		m_Vector = stringToVector(m_Array, m_Count);
		vector<int> v = m_Vector;
		m_Result = vectorToString(v);
		UpdateData(FALSE);
	}
	
}

vector<int> CSortDlg::selectSort(vector<int> a)//选择排序
{
	int i,j,min;
	int len = a.size();
	for(i=0;i<len-1;i++) //要选择的次数:n-1次
	{
		min=i; //假设当前下标为i的数最小，比较后再调整
		for(j=i+1;j<len;j++)//循环找出最小的数的下标是哪个
		{
			if (a.at(j)<a.at(min))
			{   
				min=j; //如果后面的数比前面的小，则记下它的下标
			}
		}  
  
		if(min!=i) //如果min在循环中改变了，就需要交换数据
		{
			int temp;
			temp=a.at(i);
			a.at(i)=a.at(min);
			a.at(min)=temp;
		}
	}
	return a;
}

vector<int> CSortDlg::binaryInsertSort(vector<int> a)//折半插入排序
{	
	int len = a.size();
	for(int i=1;i<len;i++)
	{
		int temp=a.at(i);
		int low=0,high=i-1;
		while(low<=high)//折半查找
		{
		int mid=(low + high)/2;
		if(temp<a.at(mid)) 
			high=mid-1; 
		else 
			low=mid+1;
		}
		for(int j=i-1;j>=low;j--) 
		{
			a.at(j+1)=a.at(j);//记录后移
		}
		a.at(low)=temp;//插入	 
	}
	return a;
}

vector<int> CSortDlg::bubbleSort(vector<int> a)//冒泡排序
{
    int j,k,h;
	int len = a.size();
    for(h=len-1;h>0;h=k) /*循环到没有比较范围*/
	{
        for(j=0,k=0;j<h;j++) /*每次预置k=0，循环扫描后更新k*/
		{
           if (a.at(j)>a.at(j+1)) /*大的放在后面，小的放到前面*/
		   {
			   int t;
               t=a.at(j);
               a.at(j)=a.at(j+1);
               a.at(j+1)=t; /*完成交换*/
               k=j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/
		   }
		}
	}
	return a;
}

vector<int> CSortDlg::insertSort(vector<int> a)//直接插入排序
{
	int i,j,t;
	int len = a.size();
	for(i=1;i<len;i++) //要选择的次数：1~n-1共n-1次
	{ 
		t=a.at(i);//暂存下标为i的数.下标从1开始
		for(j=i-1;j>=0&&t<a.at(j);j--)//注意:j=i-1,j--,这里就是下标为i的数,在它前面有序列中找插入位置。
		{
			a.at(j+1)=a.at(j); //如果满足条件就往后挪
		}
		a.at(j+1)=t; //找到下标为i的数的放置位置
	}
	return a;
}

vector<int> CSortDlg::shellSort(vector<int> arr)
{
	int i,j,k,t;
	int len = arr.size();
	for(i = len/2; i > 0; i = i/2) //控制增量
	{
		for(j = i; j < len; j++) //这个实际上就是上面的直接插入排序
		{
			t = arr.at(j);
			for(k = j - i;( k >= 0 && t < arr.at(k)); k -= i)
			{
				arr.at(k + i) = arr.at(k);
			}
			arr.at(k + i) = t;
		}
	}
	return arr;
}

bool CSortDlg::isNum(CString s)
{
	int i, len = s.GetLength();
	char c;
	for(i = 0; i < len; i++)
	{
		c = s.GetAt(i);
		if((c < 48 || c > 57) && (c != 32 ) && ( c != 44))
			return false;
	}
	return true;
}

vector<int> CSortDlg::stringToVector(CString s, int size)
{
	vector<int> v;
	int len = s.GetLength();
	int i, m = 10, t = 0, count = 0;
	char c;
	for(i = 0; i < len; i++)
	{
		c = s.GetAt(i);
		if(c >= 48 && c <= 57)//是0-9
		{
			t *= m;
			t += (c - 48);
		}
		else if(c == 32 || c == 44)//32空格 44逗号
		{
			if(s.GetAt(i - 1) != 32 && s.GetAt(i - 1) != 44)//并且前面一个字符也不是空格和逗号
				v.push_back(t);//将所取得的数字加入vector中去
				t = 0;
				count++;		//元素个数加1
		}
		if(i == len - 1 && (c >= 48 && c <= 57))//如果是最后一个字符,并且该字符是一个数字
		{
			v.push_back(t);
			count++;		//元素个数加1
		}
	}

	m_Count = count;
	UpdateData(FALSE);	//将类成员变量中的数据传送到窗口中去
	return v;
}

CString CSortDlg::vectorToString(vector<int> v)
{
	CString s = "";
	int i, len = v.size(), value;
	for(i = 0; i < len; i++)
	{
		value = v.at(i);
		s += intToString(value);
		if(i != len - 1)
			s += " ";
	}
	return s;
}

CString CSortDlg::intToString(int t)
{
	CString s = "";
	int i = 0, m = t, n = 1, r;
	char c;
	while(m)
	{
		i++;
		m /= 10;
		n *= 10;
	}
	m = t;
	n /= 10;
	while(i--)
	{
		r = m % n;
		m /= n;
		c = m + 48;
		s += c;
		m = r;
		n /= 10;
	}
	return s;
}

void CSortDlg::OnCheckInsertSort() 
{
	m_Vector = stringToVector(m_Array, m_Count);
	vector<int> v = m_Vector;
	if(m_InsertSortCheck.GetCheck())//插入排序
	{
		m_ResultInsertSort = vectorToString(insertSort(v));
	}
	else
	{
		m_ResultInsertSort = "";
	}
	UpdateData(FALSE);	//将类成员变量中的数据传送到窗口中去
}

void CSortDlg::OnCheckBubbleSort() 
{
	m_Vector = stringToVector(m_Array, m_Count);
	vector<int> v = m_Vector;
	if(m_BubbleSortCheck.GetCheck())//冒泡排序
	{
		m_ResultBubbleSort = vectorToString(bubbleSort(v));
	}
	else
	{
		m_ResultBubbleSort = "";
	}
	UpdateData(FALSE);	//将类成员变量中的数据传送到窗口中去
}

void CSortDlg::OnCheckBinaryInsertSort() 
{
	m_Vector = stringToVector(m_Array, m_Count);
	vector<int> v = m_Vector;
	if(m_BinaryInsertSortCheck.GetCheck())//折半插入排序
	{
		m_ResultBinaryInsertSort = vectorToString(binaryInsertSort(v));
	}
	else
	{
		m_ResultBinaryInsertSort = "";
	}
	UpdateData(FALSE);	//将类成员变量中的数据传送到窗口中去
}

void CSortDlg::OnCheckSelectSort() 
{
	m_Vector = stringToVector(m_Array, m_Count);
	vector<int> v = m_Vector;
	if(m_SelectSortCheck.GetCheck())//选择排序
	{
		m_ResultSelectSort = vectorToString(binaryInsertSort(v));
	}
	else
	{
		m_ResultSelectSort = "";
	}
	UpdateData(FALSE);	//将类成员变量中的数据传送到窗口中去
}

void CSortDlg::OnCheckShellSort() 
{
	m_Vector = stringToVector(m_Array, m_Count);
	vector<int> v = m_Vector;
	if(m_ShellSortCheck.GetCheck())//希尔排序
	{
		m_ResultShellSort = vectorToString(shellSort(v));
	}
	else
	{
		m_ResultShellSort = "";
	}
	UpdateData(FALSE);	//将类成员变量中的数据传送到窗口中去
}