|
一、引言
排序是计算机数据处理中的一项重要操作，通过排序可以提高查找的效率。在一般情况下，排序问题的输入是输入n个数a1，a2，a3，……，an的一个序列，要设计一个有效的排序算法，产生输入序列的一个重新排列：a11， a21， a31， ……，an1，使得a11< a21< a31<……< an1。输入序列通常是一个有n个元素的数组。随着近十年来数据处理规模的迅速增长，计算机用于处理排序所花的总时间越来越多，熟练的掌握一些典型的排序算法，对于程序设计人员来说是非常重要的。
二、选择法排序
初始序列： 9 0 5 3 7 8 4 2 10 1
第一遍排序： 【0】 9 5 3 7 8 4 2 10 1
第二遍排序： 【0 1】 5 3 7 8 4 2 10 9
第三遍排序： 【0 1 2】 3 7 8 4 5 10 9
第四遍排序： 【0 1 2 3】 7 8 4 5 10 9
第五遍排序： 【0 1 2 3 4】 8 7 5 10 9
第六遍排序： 【0 1 2 3 4 5】 7 8 10 9
第七遍排序： 【0 1 2 3 4 5 7】 8 10 9
第八遍排序： 【0 1 2 3 4 5 7 8】 10 9
第九遍排序： 【0 1 2 3 4 5 7 8 9】 10
排序结果： 【0 1 2 3 4 5 7 8 9 10】 |
假设要处理的数据存放在数组A[]中。选择法排序的基本思想是：对待排序的数组序列进行n-1遍的处理，第i遍处理是将A[i]，A[i+1]，……，A[n]中值最小者与A[i]交换位置。这样，经过i遍处理后，前i个数据的位置就已经是正确的了。下面通过一个具体的实例来理解选择排序的排序过程。
从上述选择法排序的基本思想及排序过程可以看出，要实现选择法排序，共需要两层循环：第一层循环用来控制排序需要进行几遍，第二层循环用于控制在第i遍排序时在未排序的数据中查找值最小的，用来和待定位置上的数据进行交换。实现选择法排序的算法描述如下：
void SelectSort(int[] a)
{ //共需要.a.Length - 1遍循环，a.Length为元素个数
for (int i = 0; i < a.Length - 1; i++)
{ //i指示下一个最小的数据待确定的位置
int k = i; //k用来记录剩余元素中值最小的位置
for (int j = i; j < a.Length; j++)
{ //在未排序的数据中查找值最小的数据的位置，并记录在变量k中
if (a[j] < a[k])
k = j;
}
if (k != i) //如果第i个数据不是最小的，则和最小的进行交换
{ int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
}
三、动态演示程序
在窗体的界面上放置一个面板控件Panel，作为展示动态排序过程的窗口，在窗体上设置两个定时器控件Timer，一个用来控制排序的外层循环，另一个用来控制排序的内层循环，即用两个Timer控件实现上面算法中的两层循环，从而达到动态显示排序过程的目的，设置两个Timer控件的Interval属性的值可以控制排序的速度。程序中的关键代码如下：
1、在类中定义如下变量：
private const int MAXNUMBERS = 60;//数组最大元素个数
private int[] numbers; //存放数据的数组
//动态显示排序过程的Label控件数组
private System.Windows.Forms.Label[] lblNumbers = new Label[MAXNUMBERS];
private int iOuter; //控制外层循环
private int jInner; //控制内层循环
private int k; //记录最小数据的位置
2、生成初始界面和数据由窗体上的命令按钮“生成数据”完成，其实现代码如下：
private void btnCreateNumber_Click(object sender, EventArgs e)
{
btnClear_Click(null, null);//清除面板中的标签
this.txtResult.Clear(); //清除文本框的内容
iOuter = 0; //设置新一次排序
Random random = new Random();//获取数据个数
int nDataNumbers = int.Parse(this.num_DataNumbers.Value.ToString());
numbers = new int[nDataNumbers];
for (int i = 0, k = 0, j = 0; i < nDataNumbers; i++, k++)
{
if (i % 9 == i / 9)
{
k = 0;
j = i % 9;
}
//随机产生数据
int temp = -256 + random.Next(512);
numbers[i] = temp;
//在面板中安排标签并设置标签的相关属性
lblNumbers[i] = new Label();
lblNumbers[i].Location = new Point(k * 50 + 20, j * 50 + 20);
lblNumbers[i].Size = new Size(40, 30);
lblNumbers[i].BackColor = Color.Red;
lblNumbers[i].ForeColor = Color.Yellow;
lblNumbers[i].Text = temp.ToString();
lblNumbers[i].Font = new Font("宋体", 12);
lblNumbers[i].TextAlign = ContentAlignment.MiddleCenter;
this.panNumber.Controls.Add(lblNumbers[i]);
}
string rr = "";
for (int jj = 0; jj <= numbers.Length - 2; jj++)
{
rr = rr + numbers[jj].ToString() + " ";
}
rr = rr + numbers[numbers.Length - 1].ToString();
txtResult.Text = "初始数据序列：" + rr;
}
3、使用Timer控件tmrOuter控制排序的外层循环的实现，具体实现代码如下：
private void tmrOuter_Tick(object sender, EventArgs e)
{
if (iOuter < numbers.Length - 1)
{ //每趟排序时假设初始的数据为最小值，设置当前最小值颜色
lblNumbers[iOuter].ForeColor = Color.Red;
lblNumbers[iOuter].BackColor = Color.Yellow;
k = iOuter;
jInner = iOuter + 1;
//设置搜索标签的颜色
lblNumbers[jInner].ForeColor = Color.Blue;
lblNumbers[jInner].BackColor = SystemColors.Control;
tmrOuter.Enabled = false;
tmrInner.Enabled = true;
}
else //排序结束处理
{
lblNumbers[iOuter].ForeColor = Color.Black;
lblNumbers[iOuter].BackColor = SystemColors.Control;
tmrOuter.Enabled = false;
tmrInner.Enabled = false;
MessageBox.Show("排序结束！", "消息", MessageBoxButtons.OK, MessageBoxIcon.Information);
iOuter = 0;//为下一次排序重新设置
}
}
4、使用Timer控件tmrInner控制排序内层循环的实现，具体实现代码如下：
private void tmrInner_Tick(object sender, EventArgs e)
{
if (jInner < numbers.Length)
{ //确定最小值的位置
if (numbers[jInner] < numbers[k])
{ //恢复原最小值标签的颜色
lblNumbers[k].ForeColor = Color.Yellow;
lblNumbers[k].BackColor = Color.Red;
k = jInner;
//重新设置新的最小值标签的颜色
lblNumbers[k].ForeColor = Color.Red;
lblNumbers[k].BackColor = Color.Yellow;
}
else
{ //恢复已经搜索过的标签的颜色
lblNumbers[jInner].ForeColor = Color.Yellow;
lblNumbers[jInner].BackColor = Color.Red;
}
jInner = jInner + 1;
if (jInner < numbers.Length)
{
//设置搜索标签的颜色
lblNumbers[jInner].ForeColor = Color.Blue;
lblNumbers[jInner].BackColor = SystemColors.Control;
}
}
else
{ if (k != iOuter)
{//当前位置的数据和剩余数据中最小的交换位置
int temp = numbers[iOuter];
numbers[iOuter] = numbers[k];
lblNumbers[iOuter].Text = numbers[iOuter].ToString();
lblNumbers[iOuter].ForeColor = Color.Black;
lblNumbers[iOuter].BackColor = SystemColors.Control;
numbers[k] = temp;
lblNumbers[k].ForeColor = Color.Yellow;
lblNumbers[k].BackColor = Color.Red;
lblNumbers[k].Text = numbers[k].ToString();
}
else
{
lblNumbers[k].ForeColor = Color.Black;
lblNumbers[k].BackColor = SystemColors.Control;
}
iOuter = iOuter + 1;
string rr = "";
for (int jj = 0; jj <= numbers.Length - 2; jj++)
{
rr = rr + numbers[jj].ToString() + " ";
}
rr = rr + numbers[numbers.Length - 1].ToString();
{ //每趟排序的结果显示在文本框中
txtResult.Text = txtResult.Text + (char)13 + (char)10 + "第" + iOuter.ToString() + " 遍排序结果：" + rr;
}
tmrOuter.Enabled = true;
tmrInner.Enabled = false;
}
}
5、“重置”命令按钮，停止当前的排序，清空原有的信息，实现代码如下：
private void btnClear_Click(object sender, EventArgs e)
{ //停止排序
tmrOuter.Stop();
tmrInner.Stop();
this.txtResult.Clear(); //清除文本框的内容
numbers=new int[1];
this.panNumber.Controls.Clear();
}
6、“开始排序”命令按钮，启动排序过程，代码如下：
private void btnSort_Click(object sender, EventArgs e)
{
if (numbers.Length < 10)
{
MessageBox.Show("没有生成数据！", "错误提示");
return;
}
//启动定时器，开始排序过程
tmrOuter.Enabled = true;
}
四、程序运行界面
程序运行的界面如下所示，运行时，先确定要排序的数据个数，然后单击“生成数据”命令按钮，可以重新设定排序的数据，单击“开始排序”命令按钮，开始排序过程。在排序过程中，已经排好序的数据序列、当前的最小值、以及动态的搜索过程等环节都能够清楚、直观的看到。
五、结语
程序中使用基本的控件设计出效果良好的程序，希望此程序能起到抛砖引玉的作用，大家可以据此将其他的一些典型的计算机算法编程实现直观化，让抽象的东西不再那么难于理解。
|
