using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace Sort
{
/// <summary>
/// 排序算法
/// </summary>
class Program
{
static void Main(string[] args)
{
FrmSort frm = new FrmSort();
frm.ShowDialog();
}
}
class FrmSort : Form
{
private const int length = 100; //待排序集合的宽度
private const int width = 2; //绘图时每个柱子的宽度
private const int height = 2; //绘图时每个柱子的高度放大倍数
public FrmSort()
{
this.BackColor = Color.White;
this.Width = 1000;
this.Height = 600;
this.Shown += new System.EventHandler(this.Frm_Shown);
}
private void Frm_Shown(object sender, EventArgs e)
{
Insert(0);
HalfInsert(1);
SelectSort(2);
BubbleSort(3);
ShellSort(4);
MergeSort(5);
}
//获得随机数组
static List<int> GetRandomList()
{
Random rnd = new Random(1);
List<int> listOriginal = new List<int>();
for (int i = 1; i < (length + 1); i++)
{
listOriginal.Add(i);
}
List<int> list = new List<int>();
foreach (int item in listOriginal)
{
list.Insert(rnd.Next(list.Count), item);
}
return list;
}
static int[] GetRandomArray()
{
return GetRandomList().ToArray();
}
// 绘图
private void Draw(List<int> valueList, List<int> reDrawIndexList, Graphics g, int xBase, int yBase)
{
for (int i = 0; i < reDrawIndexList.Count; i++)
{
int xIndex = reDrawIndexList[i];
Pen whitePen = new Pen(Brushes.White, width);
Pen blackPen = new Pen(Brushes.Black, width);
Point point1 = new Point(xBase + xIndex * width, yBase);
Point point2 = new Point(xBase + xIndex * width, yBase + length * height);
Point point3 = new Point(xBase + xIndex * width, yBase + valueList[xIndex] * height);
g.DrawLine(whitePen, point1, point2);
g.DrawLine(blackPen, point1, point3);
}
}
// 绘图
private void Draw(int[] valueList, List<int> reDrawIndexList, Graphics g, int xBase, int yBase)
{
for (int i = 0; i < reDrawIndexList.Count; i++)
{
int xIndex = reDrawIndexList[i];
Pen whitePen = new Pen(Brushes.White, width);
Pen blackPen = new Pen(Brushes.Black, width);
Point point1 = new Point(xBase + xIndex * width, yBase);
Point point2 = new Point(xBase + xIndex * width, yBase + length * height);
Point point3 = new Point(xBase + xIndex * width, yBase + valueList[xIndex] * height);
g.DrawLine(whitePen, point1, point2);
g.DrawLine(blackPen, point1, point3);
}
}
// 绘图
private void Draw(int myValue, int myIndex, Graphics g, int xBase, int yBase)
{
Pen whitePen = new Pen(Brushes.White, width);
Pen blackPen = new Pen(Brushes.Black, width);
Point point1 = new Point(xBase + myIndex * width, yBase);
Point point2 = new Point(xBase + myIndex * width, yBase + length * height);
Point point3 = new Point(xBase + myIndex * width, yBase + myValue * height);
g.DrawLine(whitePen, point1, point2);
g.DrawLine(blackPen, point1, point3);
}
private void GetBasePoint(int index, out int xBase, out int yBase)
{
xBase = 20 + (index % 3) * width * length * 11 / 10;
yBase = 20 + (index / 3) * height * length * 11 / 10;
}
//直接插入
//每一轮都保证左侧序列已排序, 右侧序列不断的往左侧序列中插入
private void Insert(int place)
{
int xBase, yBase;
GetBasePoint(place, out xBase, out yBase);
int[] intArray = GetRandomArray();
using (Graphics g = this.CreateGraphics())
{
List<int> listIndex = new List<int>();
for (int i = 0; i < intArray.Length; i++)
{
listIndex.Add(i);
}
Draw(intArray, listIndex, g, xBase, yBase);
for (int i = 1; i < intArray.Length; i++)
{
for (int j = i - 1; (j >= 0) && (intArray[j + 1] < intArray[j]); j--)
{
int temp = intArray[j + 1];
intArray[j + 1] = intArray[j];
intArray[j] = temp;
Draw(intArray[j], j, g, xBase, yBase);
Draw(intArray[j + 1], j + 1, g, xBase, yBase);
}
}
}
}
//折半插入
//对直接插入进行优化，在左侧找到最佳的插入点后再插入，而不是按顺序逐个尝试
private void HalfInsert(int place)
{
int xBase, yBase;
GetBasePoint(place, out xBase, out yBase);
List<int> list = GetRandomList();
using (Graphics g = this.CreateGraphics())
{
List<int> listIndex = new List<int>();
for (int i = 0; i < list.Count; i++)
{
listIndex.Add(i);
}
Draw(list, listIndex, g, xBase, yBase);
for (int i = 1; i < list.Count; i++)
{
int temp = list[i];
int low = 0;
int high = i - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (temp < list[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
Draw(temp, mid, g, xBase, yBase);
Thread.Sleep(10);
Draw(list[mid], mid, g, xBase, yBase);
}
int myValue = list[i];
list.RemoveAt(i);
list.Insert(low, myValue);
listIndex.Clear();
for (int j = low; j <= i; j++)
{
listIndex.Add(j);
}
Draw(list, listIndex, g, xBase, yBase);
}
}
}
//选择排序
//找出list[0- 99]中的最小值换到list[0]上
//找出list[1- 99]中的最小值换到list[1]上
//最后一轮：找出list[98- 99]中的最小值换到list[98]上
private void SelectSort(int place)
{
int xBase, yBase;
GetBasePoint(place, out xBase, out yBase);
List<int> list = GetRandomList();
using (Graphics g = this.CreateGraphics())
{
List<int> listIndex = new List<int>();
for (int i = 0; i < list.Count; i++)
{
listIndex.Add(i);
}
Draw(list, listIndex, g, xBase, yBase);
for (int i = 0; i < list.Count; i++)
{
//找出后面的最小值
int miniIndex = i;
int miniValue = list[i];
for (int j = i; j < list.Count; j++)
{
if (list[j] < miniValue)
{
miniIndex = j;
miniValue = list[j];
}
}
//重绘
if (miniIndex > i)
{
list.RemoveAt(miniIndex);
list.Insert(i, miniValue);
for (int j = i; j < miniIndex; j++)
{
Draw(list[j], j, g, xBase, yBase);
}
}
}
}
}
//冒泡排序
//第一轮：intArray[0] > intArray[1] ? 交换 : 不变。intArray[1] > intArray[2] ..... intArray[98] > intArray[99] ?
//第二轮：intArray[0] > intArray[1] ? 交换 : 不变。intArray[1] > intArray[2] ..... intArray[97] > intArray[98] ?
//最后一轮：intArray[0] > intArray[1] ?
private void BubbleSort(int place)
{
int xBase, yBase;
GetBasePoint(place, out xBase, out yBase);
int[] intArray = GetRandomArray();
using (Graphics g = this.CreateGraphics())
{
List<int> listIndex = new List<int>();
for (int i = 0; i < intArray.Length; i++)
{
listIndex.Add(i);
}
Draw(intArray, listIndex, g, xBase, yBase);
for (int i = intArray.Length; i > 0; i--)
{
for (int j = 0; j < i - 1; j++)
{
if (intArray[j] > intArray[j + 1])
{
int temp = intArray[j];
intArray[j] = intArray[j + 1];
intArray[j + 1] = temp;
Draw(intArray[j], j, g, xBase, yBase);
Draw(intArray[j + 1], j + 1, g, xBase, yBase);
Thread.Sleep(1);
}
}
}
}
}
//希尔排序
private void ShellSort(int place)
{
int xBase, yBase;
GetBasePoint(place, out xBase, out yBase);
int[] intArray = GetRandomArray();
using (Graphics g = this.CreateGraphics())
{
List<int> listIndex = new List<int>();
for (int i = 0; i < intArray.Length; i++)
{
listIndex.Add(i);
}
Draw(intArray, listIndex, g, xBase, yBase);
for (int step = intArray.Length / 2; step >= 1; step = step / 2) //增量递减到1使完成排序
{
for (int i = step; i < intArray.Length; i++) //插入排序的一轮
{
int temp = intArray[i];
int j = 0;
for (j = i - step; (j >= 0) && (intArray[j] > temp); j = j - step)
{
intArray[j + step] = intArray[j];
Draw(intArray[j + step], j + step, g, xBase, yBase);
Thread.Sleep(10);
}
intArray[j + step] = temp;
Draw(intArray[j + step], j + step, g, xBase, yBase);
}
}
}
}
#region 归并排序
public void MergeSort(int place)
{
int xBase, yBase;
GetBasePoint(place, out xBase, out yBase);
int[] intArray = GetRandomArray();
using (Graphics g = this.CreateGraphics())
{
List<int> listIndex = new List<int>();
for (int i = 0; i < intArray.Length; i++)
{
listIndex.Add(i);
}
Draw(intArray, listIndex, g, xBase, yBase);
MergeSort(intArray, 0, intArray.Length - 1, g, xBase, yBase);
}
}
private void MergeSort(int[] array, int p, int r, Graphics g, int xBase, int yBase)
{
if (p < r)
{
int q = (p + r) / 2;
MergeSort(array, p, q, g, xBase, yBase);
MergeSort(array, q + 1, r, g, xBase, yBase);
Merge(array, p, q, r, g, xBase, yBase);
}
}
private void Merge(int[] array, int p, int q, int r, Graphics g, int xBase, int yBase)
{
int[] L = new int[q - p + 2];
int[] R = new int[r - q + 1];
L[q - p + 1] = int.MaxValue;
R[r - q] = int.MaxValue;
for (int i = 0; i < q - p + 1; i++)
{
L[i] = array[p + i];
}
for (int i = 0; i < r - q; i++)
{
R[i] = array[q + 1 + i];
}
int j = 0;
int k = 0;
for (int i = 0; i < r - p + 1; i++)
{
if (L[j] <= R[k])
{
array[p + i] = L[j];
j++;
}
else
{
array[p + i] = R[k];
k++;
}
Draw(array[p + i], p + i, g, xBase, yBase);
Thread.Sleep(10);
}
}
#endregion
}
}