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
///
/// 插入排序
///
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[] CreateData()
{
Random rnd = new Random();
int count = 1000000;
int __max = 100000;
int[] array = new int[count];
for (int i = 0; i < count; i++)
{
array[i] = rnd.Next(1, __max);
}
return array;
}
private void button1_Click(object sender, EventArgs e)
{
DateTime dt1 = DateTime.Now;
//=====================================================================================
int[] array = CreateData();
List list = array.ToList();
list.Sort();
//=====================================================================================
DateTime dt2 = DateTime.Now;
//=====================================================================================
array = CreateData();
list = array.ToList();
list.Sort((a, b) => a - b);
//=====================================================================================
DateTime dt3 = DateTime.Now;
//=====================================================================================
array = CreateData();
QuickSort.Sort(array);
//=====================================================================================
DateTime dt4 = DateTime.Now;
string t1 = dt2.Subtract(dt1).TotalMilliseconds.ToString();
string t2 = dt3.Subtract(dt2).TotalMilliseconds.ToString();
s