实践证明快速排序效率最高，数量大时，堆排序与快速排序都很快，堆排序会略微快一点，冒泡效率经常是最差的。
.net自带的排序非常非常非常强大，大数量时比堆快很多。
下面是10W个数字排序的结果：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Sort
{
class Program
{
static int radLen = new Random().Next(5, 20);
private delegate int[] SortMethod(int[] arr);
static void Main(string[] args)
{
int[] array = new int[radLen];
Console.WriteLine("未排序数组：");
for (int i = 0; i < radLen; i++)
{
int n = new Random(DateTime.Now.Millisecond).Next(50);
array[i] = n;
Console.Write(n);
if (i < radLen - 1)
{
Console.Write(", ");
}
System.Threading.Thread.Sleep(10);
}
Console.WriteLine();
Console.WriteLine();
//array = new int[] { 1,12,49,10,48,35 };
Sort s = new Sort();
TestMethod("插入排序：", s.InsertSort, array);
TestMethod("折半查找插入排序：", s.BIInsert, array);
TestMethod("希尔插入排序：", s.ShellSort, array);
TestMethod("冒泡排序：", s.BubbleSort, array);
TestMethod("快速排序：", s.QuickSort, array);
TestMethod("选择排序：", s.SimpleSelectSort, array);
TestMethod("堆排序：", s.HeapSort, array);
Console.ReadLine();
}
static void TestMethod(string methodTip, SortMethod method, int[] arr)
{
Console.WriteLine(methodTip);
DateTime dtStart = DateTime.Now;
int[] ar = method(arr);
Console.ForegroundColor = ConsoleColor.Yellow;
Console.WriteLine("耗时：{0}", DateTime.Now - dtStart);
Console.ResetColor();
PrintArray(ar);
}
static void PrintArray(int[] array)
{
for (int i = 0; i < radLen; i++)
{
Console.Write(array[i]);
if (i < radLen - 1)
{
Console.Write(", ");
}
}
Console.WriteLine();
}
}
//所有算法都是升序
public class Sort
{
private int[] array;
private void CopyArray(int[] arr)
{
array = new int[arr.Length];
Array.Copy(arr, this.array, arr.Length);
}
#region 插入排序
//插入排序，插入到有序数组里，先取出第一个数值，其为有序，插入时先和有序数组最后一个比，如果小则从后向前遍历
//插入排序需要向后移动元素
public int[] InsertSort(int[] arr)
{
CopyArray(arr);
if (array != null)
{
//int t = array[0];
for (int i = 1; i < array.Length; i++)
{
//如果当前值比有序序列最后一个小，要从后向前找到一元素
//该元素是有序序列中（从后向前）第一个比当前值小的
if (array[i] < array[i - 1])
{
int t = array[i];
//在有序数组中从后向前找第一个比当前小的
//并且找的过程中，把大于当前值的元素后移
int j = i - 1;
while (j >= 0 && array[j] > t)
{
array[j + 1] = array[j];
j--;
}
//由于j--，j指向的是有序序列中（从后向前）第一个比当前值小的前一位
array[j + 1] = t;
}
}
}
return array;
}
//折半插入排序，插入排序的变形，用折半查找到应插入的位置
public int[] BIInsert(int[] arr)
{
CopyArray(arr);
if (array != null)
{
int t = array[0];
for (int i = 1; i < array.Length; i++)
{
if (array[i] < array[i - 1])
{
t = array[i];
//二分查找，找第一个比
int low = 0;
int high = i - 1;
int mid = 0;
while (low <= high)
{
mid = (low + high) / 2;
if (array[mid] < t)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
//向后移动
int j = i - 1;
while (j > high)
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = t;
}
}
}
return array;
}
//和插入排序算法类似，只是原算法每次加1，这里的每次加dk，
//可以认为原算法就是步长为1的shell排序
private void ShellInsert(int[] arr, int dk)
{
int t = arr[0];
for (int i = dk; i < arr.Length; i += dk)
{
if (arr[i] < arr[i - dk])
{
t = arr[i];
int j = i - dk;
while (j >= 0 && arr[j] > t)
{
arr[j + dk] = arr[j];
j -= dk;
}
arr[j + dk] = t;
}
}
}
//数组基本有序时，插入排序比较有效，shell思想是根据步长分组，
//步子能踏到的分为一组，然后每组进行插入排序，
//步长是个int数组，从大到小，最后一个值必须是1，
//直到步长为1的执行完
public int[] ShellSort(int[] arr)
{
CopyArray(arr);
int[] dkArray = new int[] { 5, 3, 1 };//步长，步长的设计影响着排序的效率
if (array != null)
{
for (int i = 0; i < dkArray.Length; i++)
{
ShellInsert(array, dkArray[i]);
}
}
return array;
}
#endregion
#region 冒泡
//冒泡，交换相邻，大者向上冒
//存在交换次数过多的问题，可以说实验果是效率最差的一种排序算法
public int[] BubbleSort(int[] arr)
{
CopyArray(arr);
if (array != null)
{
//如果在冒的过程中没有交换发生，说明已经有序
bool exchange = true;
//外层循环定位已经排序过的值
for (int i = array.Length - 1; i > 0 && exchange; i--)
{
exchange = false;
for (int j = 0; j < i; j++)
{
if (array[j] > array[j + 1])
{
array[j] ^= array[j + 1];
array[j + 1] ^= array[j];
array[j] ^= array[j + 1];
exchange = true;
}
}
}
}
return array;
}
#endregion
#region 快速排序
//pivot设置在第一位
private int Partition(int[] arr, int low, int high)
{
int t = arr[low];//中轴
while (low < high)
{
//因为中轴设置在第一位，必须先从后向前遍历
//从右边找从中轴小的
while (arr[high] >= t && low < high)
{
high--;
}
//把high值赋到low上
//这就是为什么中轴在第一位，要从后往前遍历的原因
//如果从前往后，把low值赋给high，逻辑上就错了，因为第一次high还没参与比，不能被赋值
//该算法用t保存中轴，也就是第一位，所以中轴位置上的值可以赋值
//找到中轴在数组中应该放的位置后，再把t赋给该位置
//很巧妙
arr[low] = arr[high];
//low的值已经是high值了，上个步骤是比中轴大才会换到low上
//不用再次比较low上的值，让low向后移一步
if (low < high)
{
low++;
}
//从前向后找比中轴大的元素
while (arr[low] <= t && low < high)
{
low++;
}
//找到后把low值放在high上，
//在从后往前找时，high值放在low上了，也就是说数组中存在两个high对应的值
//要知道最后一个是无效的，现在把low放到high上，没有问题，
//low放在high上后，low的值在数组又出现两次，第一个值是无效的
//下次从后往前循环时又会把high赋给low，这是个交替的过程
//最后low位置与high位置相同时，这就是中轴应该的位置，
//可以想像一下，在交替过程中，有一个无效的指针忽左忽右，最后小的都移到指针左边了，大的都移到指针右边
arr[high] = arr[low];
//与上面low++一样，避免下次从后到前时的比较
if (low < high)
{
high--;
}
}
//low == high时，就是中轴的位置
arr[low] = t;
return low;
}
//pivot设置在最后一位
private int PartitionV2(int[] arr, int low, int high)
{
int pivot = arr[high];
while (low < high)
{
while (low < high && arr[low] <= pivot)
{
low++;
}
arr[high] = arr[low];
while (low < high && arr[high] >= pivot)
{
high--;
}
arr[low] = arr[high];
}
arr[low] = pivot;
return low;
}
//使用交换，原始作法，不用变量保存中轴，高低交换
//不像上面，数组中有一个无效元素
private int PartitionV3(int[] arr, int low, int high)
{
//中轴只作判断依据
int pivot = arr[low];
while (low < high)
{
while (low < high && arr[high] >= pivot)
{
high--;
}
if (arr[low] != arr[high])
{
arr[low] ^= arr[high];
arr[high] ^= arr[low];
arr[low] ^= arr[high];
}
while(low< high && arr[low] <= pivot)
{
low++;
}
if (arr[low] != arr[high])
{
arr[low] ^= arr[high];
arr[high] ^= arr[low];
arr[low] ^= arr[high];
}
}
return low;
}
//快速排序，以一个元素做中轴（可以是第一个，最后一个，或者中间某元素）
//其他元素，小的放在中轴左边，大的放在中轴右边
//再利用递归思想，把左右两边使用快速排序
//实验证明，快速排序果然够快
private void QSort(int[] arr, int low, int high)
{
if (low < high)
{
int pivot = Partition(arr, low, high);
//左边快速排序
QSort(arr, low, pivot - 1);
//右边快速排序
QSort(arr, pivot + 1, high);
}
}
public int[] QuickSort(int[] arr)
{
CopyArray(arr);
if (array != null)
{
QSort(array, 0, array.Length - 1);
}
return array;
}
#endregion
#region 选择排序
//简单选择排序，找第一个最小的放在前面，再从其他中找最小的放在其后，如此反复
public int[] SimpleSelectSort(int[] arr)
{
CopyArray(arr);
if (array != null)
{
for (int i = 0; i < array.Length - 1; i++)
{
int min = array[i];
int minPos = i;
//在后面的元素中选择出最小的
for (int j = i + 1; j < array.Length; j++)
{
if (min > array[j])
{
min = array[j];
minPos = j;
}
}
if (i != minPos)
{
array[minPos] ^= array[i];
array[i] ^= array[minPos];
array[minPos] ^= array[i];
}
}
}
return array;
}
#endregion
#region 堆排序
//调整数组指定范围的元素成大顶堆
private void HeapAdjust(int[] arr, int startPos, int endPos)
{
//因为数组下标从0开始，所以最后非叶结点计算方式与书上不同，书上为lastPos/2
//同理，叶结点的确定也相应变化
//保存父结点
int parent = arr[startPos];
//对父结点的左右孩子进行比较调整
for (int i = startPos * 2 + 1; i <= endPos; i = i * 2 + 1)//i值初始是左孩子，左孩子一定会有，但是不一定有右孩子
{
//判断是否有右孩子，如果有而且右孩子比左孩子大，则应比较右孩子和父结点
if(i + 1 <= endPos && (arr[i] < arr[i+1]))
{
i++;//i换成右孩子
}
//