gth];
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;//返回结果数组
}
注：此算法由周利华提供（http://www.cnblogs.com/architect/archive/2009/05/06/1450489.html
）
基数排序
基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。
//基数排序
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;
}
计数排序
数排序, 基数排序, 桶排序等非比较排序算法,平均时间复杂度都是O(n). 这些排序因为其待排序元素本身就含有了定位特征,因而不需要比较就可以确定其前后位置,从而可以突破比较排序算法时间复杂度O(nlgn)的理论下限.
计数排序是最简单的特例,它要 求待排序元素是位于0到k之间的正整数 , 因而它是很特殊的情况,基本上没有特别的应用价值; 但是另一方面, 它又是基数排序的基础,或者说是一部分,所以简单的描述一下:
输入数组 A : 元素特征是 0-k的正整数,可以有重复值;
输出数组 B : 输出A的一个非减序列
中间数组 C : 大小是k, 它的i( 0<= i <= k)索引位置存储的是A元素集合中值是k的元素的个数有关.
算法的基本思想是:
统计A中元素的值的集合, 以A中元素的值为索引, 将值的个数填写到中间数组C的对应处.
对C从头开始自累加, 这样C中存储的就是, 当输入数组A中的值为当前索引时, 它前面的元素数量(包含重复元素).
将C依次输出到输出数组B中.
///
/// input array /// the value arrange in input array ///
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;
}
根堆排序
堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
堆排序是不稳定的。算法时间复杂度O(nlog n)。
///
/// /// ///
private void HeapSort(ref double[] dblArray)
{
for (int i = dblArray.Length – 1; i >= 0; i–)
{
if (2 * i + 1 < dblArray.Length)
{
int MinChildrenIndex = 2 * i + 1;
//比较左子树和右子树，记录最小值的Index
if (2 * i + 2 < dblArray.Length)
{
if (dblArray[2 * i + 1] > dblArray[2 * i + 2])
MinChildrenIndex = 2 * i + 2;
}
if (dblArray[i] > dblArray[MinChildrenIndex])
{
Exchageva lue(ref dblArray[i], ref dblArray[MinChildrenIndex]);
NodeSort(ref dblArray, MinChildrenIndex);
}
}
}
}
///
/// ///
private void NodeSort(ref double[] dblArray, int StartIndex)
{
while (2 * StartIndex + 1 < dblArray.Length)
{
int MinChildrenIndex = 2 * StartIndex + 1;
if (2 * StartIndex + 2 < dblArray.Length)
{
if (dblArray[2 * StartIndex + 1] > d