算法是程序的灵魂
算法的重要性是不言而喻的，尽管.Net类库封装了丰富的算法库，帮助我们去完成各类工作，但我们不能不去了解它们，唯有理解了它，我们才会走得更远。接下来我会抽时间陆续的学习各类算法，并尽可能的和各位博友分享，由于我算是初探算法家族，各种不足与浅显，大家多多提宝贵意见，谢谢。
排序算法
算法定义
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。
算法比较
根据算法的空间复杂度和时间复杂度来进行比较。
算法分类
根据排序方法，大致可以分为插入、交换、选择、合并等类别。
常见的排序算法
排序的算法有很多，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。插入排序、冒泡排序、选择排序、快速排序、堆排序、归并排序、基数排序与希尔排序。下面就不给出各类排序算法的定义以及基本思想了，百科都有，还是直接上代码：
插入排序
public static void InsertSort(int[] arr)
{
int i, j, temp;
int length = arr.Length;
for (i = 1; i < length; i++)
{
temp = arr[i];
for (j = i; j > 0 && arr[j-1] >temp; j--)
{
arr[j] = arr[j - 1];
}
arr[j] = temp;
}
}
冒泡排序
public static void BubbleSort(int[] arr)
{
int i, j, temp;
for (i=0; i <= arr.Length - 2; i++)
{
for (j = i+1; j <= arr.Length - 1; j++)
{
if (arr[i] > arr[j])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
选择排序
public static void SelectSort(int[] arr)
{
int i, j, temp, min;
for (i = 0; i <= arr.Length - 2; i++)
{
min = i;
for (j = i + 1; j <= arr.Length - 1; j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
if (i != min)
{
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
快速排序
public static void QuickSort(int[] arr,int low,int high)
{
int i = low;
int j = high;
int temp = arr[low];
while (low < high)
{
while ((low < high) && arr[high] >= temp)
{
--high;
}
arr[low] = arr[high];
while ((low < high) && arr[low] <= temp)
{
++low;
}
arr[high] = arr[low];
}
arr[low] = temp;
if (i < low - 1)
{
QuickSort(arr, i, low - 1);
}
if (j > low + 1)
{
QuickSort(arr, low + 1, j);
}
}
先就实现这四种排序算法，后面几种放在下一个文章中去，实现了这几个方法，接下来就是测试对比下了
随机生成数组方法
public static int[] RandomArray(int length,int minSize,int maxSize)
{
Random rand = new Random();
int[] arr = new int[length];
for (int i = 0; i <= length - 1; i++)
{
arr[i] = rand.Next(minSize, maxSize);
}
return arr;
}
测试代码
class Program
{
public static void Main()
{
Console.WriteLine("首先产生随机整数数组:");
int[] array = RookieBen.Algorithm.Sort.RandomArray(10000, 0, 50);
Sort("Bubble", (int[])array.Clone());
Sort("Select", (int[])array.Clone());
Sort("Insert", (int[])array.Clone());
Sort("Quick", (int[])array.Clone());
Sort("System",(int[])array.Clone());
Console.ReadKey();
}
public static void Sort(string info,int[] array)
{
Console.WriteLine("下面开始测试RookeBen库里的{0}排序算法",info);
//Console.WriteLine("排序前数据：");
//foreach (int num in array)
//{
// Console.Write(num + " ");
//}
//Console.WriteLine();
DateTime start, end;
Console.WriteLine("下面开始排序....");
start = DateTime.Now;
switch (info)
{
case "Bubble":
RookieBen.Algorithm.Sort.BubbleSort(array);
break;
case "Select":
RookieBen.Algorithm.Sort.SelectSort(array);
break;
case "Insert":
RookieBen.Algorithm.Sort.InsertSort(array);
break;
case "Quick":
RookieBen.Algorithm.Sort.QuickSort(array);
break;
case "System":
array.ToList().Sort();
break;
}
end = DateTime.Now;
Console.WriteLine("排序结束");
//Console.WriteLine("排序后的数据：");
//foreach (int num in array)
//{
// Console.Write(num + " ");
//}
//Console.WriteLine();
Console.WriteLine("排序耗时：{0}", end - start);
Console.WriteLine();
Console.WriteLine();
}
}
上面在控制台上进行了一次简单的测试，横向的比较了各个方法的执行效率，最后还有使用系统库里的Sort()方法。看看对比效果：
先是执行结果（附图：执行了三次）：
分析：
从执行结果来看，我们写得最多的冒泡排序其实是最慢的一种排序算法了，和直接选择排序（比冒泡要稍快一点）在一个层次上，四个算法里面执行时间最快的当属快速排序了（别人就叫这个，当然要快了），冒泡排序以及直接选择排序和它比有十倍以上的差距（执行时间上）也比插入排序要快很多，很理想的一种排序方法。最后就是都有调用库里自带的排序方法，结果很是理想，它的指向时间都比我们自己写的要快，不清楚它采用了何种排序，起码我们现在知道，它执行很快，我们应该使用它。