主要作了如下改进：
1、非递归实现，防止数据量大时栈溢出。
2、对于数据是全部相等时候的改进。
3、如果数据小于一定的数目，采用插入排序。
4、中间值的选择。
测试结果：
1、1000万个随机数据，各不相同。
List类的Sort()方法：1.3秒
List类的Sort(Comparison comparison)方法：6.2秒
自己写的算法：3.7秒
2、1000万个随机数据，有少量相同的元素。
List类的Sort()方法：1.1秒
List类的Sort(Comparison comparison)方法：5.7秒
自己写的算法：2.7秒
3、1000万个随机数据，有大量相同的元素。
List类的Sort()方法：0.8秒
List类的Sort(Comparison comparison)方法：5.3秒
自己写的算法：1.7秒
4、1000万个全部相同的数据。
List类的Sort()方法：0.59秒
List类的Sort(Comparison comparison)方法：4.7秒
自己写的算法：0.42秒
非递归实现的快速排序算法：
复制代码
namespace Sort
{
///
/// 快速排序（非递归实现）
/// 2013年12月25日
///
public class QuickSort
{
///
/// 快速排序的非递归实现
///
/// 排序数组
public static void Sort(int[] array)
{
int start = 0;
int end = array.Length - 1;
int[] stackLeft = new int[array.Length];
int[] stackRight = new int[array.Length];
int left;
int right;
int index = 0;
SortUnit(array, start, end, out left, out right);
if (left > start)
{
stackLeft[index] = start;
stackRight[index] = left;
index++;
}
if (right < end)
{
stackLeft[index] = right;
stackRight[index] = end;
index++;
}
while (index > 0)
{
index--;
start = stackLeft[index];
end = stackRight[index];
if (end - start < 5)//排序算法执行到一定深度时，数组整体有序，局部无序，这时停止快速排序，后面将改用插入排序
{
continue;
}
SortUnit(array, start, end, out left, out right);
if (left > start)
{
stackLeft[index] = start;
stackRight[index] = left;
index++;
}
if (right < end)
{
stackLeft[index] = right;
stackRight[index] = end;
index++;
}
}
InsertionSort(array);
}//end of Sort
///
/// 一次排序单元，完成此方法，数组分成三部分，左边的比key小，右边的比key大，中间的和key相等
///
/// 排序数组
/// 排序起始位置
/// 排序结束位置
/// 当key存在相同元素时，完成排序后，中间部分的左边缘
/// 当key存在相同元素时，完成排序后，中间部分的右边缘
private static void SortUnit(int[] array, int start, int end, out int left, out int right)
{
int key = array[(start + end) / 2];
int[] stackRight = new int[end - start + 1];//存放原始数组中key右边的与key相等的元素的下标
int[] stackLeft = new int[end - start + 1];//存放原始数组中key左边的与key相等的元素的下标
int stackRightCount = 0;
int stackLeftCount = 0;
while (start < end)
{
while (start < end && array[end] >= key)
{
if (array[end] == key)
{
stackRight[stackRightCount++] = end;//把与key相等的元素的下标记录下来
}
end--;
}
if (start != end) array[start] = array[end];
while (start < end && array[start] <= key)
{
if (array[start] == key)
{
stackLeft[stackLeftCount++] = start;//把与key相等的元素的下标记录下来
}