1.简介
插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
2.算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
1.从第一个元素开始，该元素可以认为已经被排序
2.取出下一个元素，在已经排序的元素序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一位置
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到该位置后
6.重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。
4.C#实现

/// <summary>
/// 插入排序
/// </summary>
public void InsertSort(int[] list)
{
for (int i = 1; i < list.Length; ++i)
{
int t = list[i];
int j = i;
while ((j > 0) && (list[j - 1] > t))
{
list[j] = list[j - 1];
--j;
}
list[j] = t;
}
}

二 希尔排序
1.简介
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
2.算法实现
原始的算法实现在最坏的情况下需要进行O(n2)的比较和交换。V. Pratt的书[1] 对算法进行了少量修改，可以使得性能提升至O(n log2 n)。这比最好的比较算法的O(n log n)要差一些。
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。
一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。

4.C#实现

/// <summary>
/// 希尔排序
/// </summary>
public void ShellSorter(int[] list)
{
int inc;
for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
for (; inc > 0; inc /= 3)
{
for (int i = inc + 1; i <= list.Length; i += inc)
{
int t = list[i - 1];
int j = i;
while ((j > inc) && (list[j - inc - 1] > t))
{
list[j - 1] = list[j - inc - 1];
j -= inc;
}
list[j - 1] = t;
}
}
}

三 选择排序

1.简介
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

4.C#实现

/// <summary>
/// 选择排序
/// </summary>
private int min;
// private int m=0;
public void SelectionSorter(int[] list)
{
for (int i = 0; i < list.Length - 1; ++i)
{
min = i;
for (int j = i + 1; j < list.Length; ++j)
{
if (list[j] < list[min])
min = j;
}
int t = list[min];
list[min] = list[i];
list[i] = t;
}
}

四 冒泡排序

1.简介
冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序对n个项目需要O(n^{2})的比较次数，且可以原地排序。尽管这个算法是最简单了解和实作的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。
冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要O(n^{{2})次交换，而插入排序只要最多O(n)交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行（O(n}{2})），而插入排序在这个例子只需要O(n)个运算。因此很多现代的算法教科书避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时，使用一个旗标来表示有无需要交换的可能，也有可能把最好的复杂度降低到O(n)。在这个情况，在已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序和比较大小反过来，也可以稍微地改进效率。有时候称为往返排序，因为算法会从数列的一端到另一端之间穿梭往返。
2.算法实现
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

C#实现

/// <summary>
/// 冒泡排序
/// </summary>
public void BubbleSort(int[] R)
{
int i, j, temp; //交换标志
bool exchange;
for (i = 0; i < R.Length; i++) //最多做R.Length-1趟排序
{
exchange = false; //本趟排序开始前，交换标志应为假
for (j = R.Length - 2; j >= i; j--)
{
if (R[j + 1] < R[j]) //交换条件
{
temp = R[j + 1];
R[j + 1] = R[j];
R[j] = temp;
exchange = true; //发生了交换，故将交换标志置为真
}
}
if (!exchange) //本趟排序未发生交换，提前终止算法
{
break;
}
}
}

五 归并 排序

/// <summary>
/// 归并排序之归：归并排序入口
/// </summary>
/// <param name="data">无序的数组</param>
/// <returns>有序数组</returns>
/// <author>Lihua(www.zivsoft.com)</author>
int[] MergeSort(int[] data)
{
//取数组中间下标
int middle = data.Length / 2;
//初始化临时数组let,right，并定义result作为最终有序数组
int[] left = new int[middle], right = new int[middle], result = new int[data.Length];
if (data.Length % 2 != 0)//若数组元素奇数个，重新初始化右临时数组
{
right = new int[middle + 1];
}
if (data.Length <= 1)//只剩下1 or 0个元数，返回，不排序
{
return data;
}
int i = 0, j = 0;
foreach (int x in data)//开始排序
{
if (i < middle)//填充左数组
{
left[i] = x;
i++;
}
else//填充右数组
{
right[j] = x;
j++;
}
}
left = MergeSort(left);//递归左数组
right = MergeSort(right);//递归右数组
result = Merge(left, right);//开始排序
return result;
}
/// <summary>
/// 归并排序之并:排序在这一步
/// </summary>
/// <param name="a">左数组</param>
/// <param name="b">右数组</param>
/// <returns>合并左右数组排序后返回</returns>
int[] Merge(int[] a, int[] b)
{
//定义结果数组，用来存储最终结果
int[] result = new int[a.Length + b.Length];
int i = 0, j = 0, k = 0;
while (i < a.Length && j < b.Length)
{
if (a[i] < b[j])//左数组中元素小于右数组中元素
{
result[k++] = a[i++];//将小的那个放到结果数组
}
else//左数组中元素大于右数组中元素
{
result[k++] = b[j++];//将小的那个放到结果数组
}
}
while (i < a.Length)//这里其实是还有左元素，但没有右元素
{
result[k++] = a[i++];
}
while (j < b.Length)//右右元素，无左元素
{
result[k++] = b[j++];
}
return result;//返回结果数组
}

六 基数排序

//基数排序
public int[] RadixSort(int[] ArrayToSort, int digit)
{
//low to high digit
for (int k = 1; k <= digit; k++)
{
//temp array to store the sort result inside digit
int[] tmpArray = new int[ArrayToSort.Length];
//temp array for countingsort
int[] tmpCountingSortArray = new int[10] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
//CountingSort
for (int i = 0; i < ArrayToSort.Length; i++)
{
//split the specified digit from the element
int tmpSplitDigit = ArrayToSort[i] / (int) Math.Pow(10, k - 1) - (ArrayToSort[i] / (int) Math.Pow(10, k)) * 10;
tmpCountingSortArray[tmpSplitDigit] += 1;
}
for (int m = 1; m < 10; m++)
{
tmpCountingSortArray[m] += tmpCountingSortArray[m - 1];
}
//output the value to result
for (int n = ArrayToSort.Length - 1; n >= 0; n--)
{
int tmpSplitDigit = ArrayToSort[n] / (int) Math.Pow(10, k - 1) - (ArrayToSort[n] / (int) Math.Pow(10, k)) * 10;
tmpArray[tmpCountingSortArray[tmpSplitDigit] - 1] = ArrayToSort[n];
tmpCountingSortArray[tmpSplitDigit] -= 1;
}
//copy the digit-inside sort result to source array
for (int p = 0; p < ArrayToSort.Length; p++)
{
ArrayToSort[p] = tmpArray[p];
}
}
return ArrayToSort;
}

七 计数排序

//计数排序
/// <summary>
/// counting sort
/// </summary>
/// <param name="arrayA">input array</param>
/// <param name="arrange">the value arrange in input array</param>
/// <returns></returns>
public int[] CountingSort(int[] arrayA, int arrange)
{
//array to store the sorted result,
//size is the same with input array.
int[] arrayResult = new int[arrayA.Length];
//array to store the direct value in sorting process
//include index 0;
//size is arrange+1;
int[] arrayTemp = new int[arrange + 1];
//clear up the temp array
for (int i = 0; i <= arrange; i++)
{
arrayTemp[i] = 0;
}
//now temp array stores the count of value equal
for (int j = 0; j < arrayA.Length; j++)
{
arrayTemp[arrayA[j]] += 1;
}
//now temp array stores the count of value lower and equal
for (int k = 1; k <= arrange; k++)
{
arrayTemp[k] += arrayTemp[k - 1];
}
//output the value to result
for (int m = arrayA.Length - 1; m >= 0; m--)
{
arrayResult[arrayTemp[arrayA[m]] - 1] = arrayA[m];
arrayTemp[arrayA[m]] -= 1;
}
return arrayResult;
}

九 堆排序

一种是数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。
另一种是垃圾收集存储区，是软件系统可以编程的内存区域。
本文所说的堆指的是前者，另外，这篇文章中堆中元素的值均以整形为例
堆排序的时间复杂度是O(nlog2n),与快速排序达到相同的时间复杂度. 但是在实际应用中,我们往往采用快速排序而不是堆排序. 这是因为快速排序的一个好的实现,往往比堆排序具有更好的表现. 堆排序的主要用途,是在形成和处理优先级队列方面. 另外, 如果计算要求是类优先级队列(比如, 只要返回最大或者最小元素, 只有有限的插入要求等), 堆同样是很适合的数据结构.

堆排序
堆排序是一种选择排序。是不稳定的排序方法。时间复杂度为O(nlog2n)。
堆排序的特点是：在排序过程中，将排序数组看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。

基本思想
1.将要排序的数组创建为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置例入有序区，然后将新的无序区调整为大根堆。
重复操作，无序区在递减，有序区在递增。
初始时，整个数组为无序区，第一次交换后无序区减一，有序区增一。
每一次交换，都是大根堆的堆顶元素插入有序区，所以有序区保持是有序的。

C#实现

//堆排序算法（传递待排数组名，即：数组的地址。故形参数组的各种操作反应到实参数组上）
private void HeapSortFunction(int[] array)
{
try
{
BuildMaxHeap(array); //创建大顶推（初始状态看做：整体无序）
for (int i = array.Length -1; i >0; i--)
{
Swap(ref array[0], ref array[i]); //将堆顶元素依次与无序区的最后一位交换（使堆顶元素进入有序区）
MaxHeapify(array, 0, i); //重新将无序区调整为大顶堆
}
}
catch (Exception ex)
{ }
}

    ///<summary>
    /// 创建大顶推（根节点大于左右子节点）
    ///</summary>
    ///<param name="array">待排数组</param>
 private void BuildMaxHeap(int[] array)
    {
        try
        {
            //根据大顶堆的性质可知：数组的前半段的元素为根节点，其余元素都为叶节点
            for (int i = array.Length /2-1; i >=0; i--) //从最底层的最后一个根节点开始进行大顶推的调整
            {
                MaxHeapify(array, i, array.Length); //调整大顶堆
            }
        }
        catch (Exception ex)
        { }
    }

    ///<summary>
    /// 大顶推的调整过程
    ///</summary>
    ///<param name="array">待调整的数组</param>
    ///<param name="currentIndex">待调整元素在数组中的位置（即：根节点）</param>
    ///<param name="heapSize">堆中所有元素的个数</param>
 private void MaxHeapify(int[] array, int currentIndex, int heapSize)
    {
        try
        {
           int left =2* currentIndex +1;    //左子节点在数组中的位置
     int right =2* currentIndex +2;   //右子节点在数组中的位置
     int large = currentIndex;   //记录此根节点、左子节点、右子节点 三者中最大值的位置
            if (left < heapSize && array[left] > array[large])  //与左子节点进行比较
            {
                large = left;
            }
            if (right < heapSize && array[right] > array[large])    //与右子节点进行比较
            {
                large = right;
            }
            if (currentIndex != large)  //如果 currentIndex != large 则表明 large 发生变化（即：左右子节点中有大于根节点的情况）
            {
                Swap(ref array[currentIndex], ref array[large]);    //将左右节点中的大者与根节点进行交换（即：实现局部大顶堆）
                MaxHeapify(array, large, heapSize); //以上次调整动作的large位置（为此次调整的根节点位置），进行递归调整
            }
        }
        catch (Exception ex)
        { }
    }

    ///<summary>
    /// 交换函数
    ///</summary>
    ///<param name="a">元素a</param>
    ///<param name="b">元素b</param>
 private void Swap(refint a, refint b)
    {
        int temp =0;
        temp = a;
        a = b;
        b = temp;
    }