快速排序在大量数据，数据随机分布，并且重复数据较少时，性能较好。
主要作了如下改进：
1、非递归实现，防止数据量大时栈溢出。
2、对于数据是全部相等时候的改进。
3、如果数据小于一定的数目，采用插入排序。
4、中间值的选择。
测试结果：
1、1000万个随机数据，各不相同。
List<T>类的Sort()方法：1.3秒
List<T>类的Sort(Comparison<T> comparison)方法：6.2秒
自己写的算法：3.7秒
2、1000万个随机数据，有少量相同的元素。
List<T>类的Sort()方法：1.1秒
List<T>类的Sort(Comparison<T> comparison)方法：5.7秒
自己写的算法：2.7秒
3、1000万个随机数据，有大量相同的元素。
List<T>类的Sort()方法：0.8秒
List<T>类的Sort(Comparison<T> comparison)方法：5.3秒
自己写的算法：1.7秒
4、1000万个全部相同的数据。
List<T>类的Sort()方法：0.59秒
List<T>类的Sort(Comparison<T> comparison)方法：4.7秒
自己写的算法：0.42秒
非递归实现的快速排序算法：
namespace Sort { /// <summary> /// 快速排序（非递归实现） /// 2013年12月25日 /// </summary> public class QuickSort { /// <summary> /// 快速排序的非递归实现 /// </summary> /// <param name="array">排序数组</param> 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 /// <summary> /// 一次排序单元，完成此方法，数组分成三部分，左边的比key小，右边的比key大，中间的和key相等 /// </summary> /// <param name="array">排序数组</param> /// <param name="start">排序起始位置</param> /// <param name="end">排序结束位置</param> /// <param name="left">当key存在相同元素时，完成排序后，中间部分的左边缘</param> /// <param name="right">当key存在相同元素时，完成排序后，中间部分的右边缘</param> private static void SortUnit(int[] array, int start, int end, out int left, out int right) { int mid = (start + end) / 2; int _temp = array[start]; array[start] = array[mid]; array[mid] = _temp; int key = array[start]; 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相等的元素的下标记录下来 } start++; } if (start != end) array[end] = array[start]; } array[start] = key; //把key右边的与key相等的元素放在key的右侧 int i; int index = 0; for (i = start + 1; i <= start + stackRightCount; i++) { if (array[i] != key) { int temp = array[i]; array[i] = array[stackRight[index]]; array[stackRight[index]] = temp; index++; } } //把key左边的与key相等的元素放在key的左侧 index = 0; for (i = start - 1; i >= start - stackLeftCount; i--) { if (array[i] != key) { int temp = array[i]; array[i] = array[stackLeft[index]]; array[stackLeft[index]] = temp; index++; } } right = start + stackRightCount + 1; left = start - stackLeftCount - 1; }//end of SortUnit /// <summary> /// 插入排序 /// </summary> private static void InsertionSort(int[] array) { int i, j; int temp; for (i = 1; i < array.Length; i++) { temp = array[i]; j = i - 1; //与已排序的数逐一比较，大于temp时，该数移后 while (j >= 0 && array[j] > temp) { array[j + 1] = array[j]; j--; } array[j + 1] = temp; } } } }
测试代码：
using System; using System.Collections.Generic; using System.Linq; using System.Windows.Forms; namespace Sort { public partial class Form1 : Form { public Form1() { InitializeComponent(); } private int[] m_data; /// <summary> /// 产生测试数据 /// </summary> private int[] GetData() { if (m_data == null) { Random rnd = new Random(); int count = 10000000; int __max = 1000000; m_data = new int[count]; for (int i = 0; i < count; i++) { m_data[i] = rnd.Next(1, __max + 1); } return m_data.ToArray<int>(); } else { return m_data.ToArray<int>(); } } private void button1_Click(object sender, EventArgs e) { DateTime dt1 = DateTime.Now; //======================================================= int[] array = GetData(); List<int> list = array.ToList<int>(); list.Sort(); //======================================================= DateTime dt2 = DateTime.Now; //======================================================= array = GetData(); list = array.ToList<int>(); list.Sort((a, b) => a - b); //======================================================= DateTime dt3 = DateTime.Now; //======================================================= array = GetData(); QuickSort.Sort(array); //======================================================= DateTime dt4 = DateTime.Now; //判断排序前的数组和排序后的数组的元素是否匹配 //bool bl = ArrayComparison.compare(array, GetData()); string t1 = dt2.Subtract(dt1).TotalMilliseconds.ToString(); string t2 = dt3.Subtract(dt2).TotalMilliseconds.ToString(); string t3 = dt4.Subtract(dt3).TotalMilliseconds.ToString(); MessageBox.Show(t1 + " — " + t2 + " — " + t3); } } }