以下是2W个数排序时间 重复10次
由于快速排序每次都将问题规模缩小一倍 所以数据量越大 快速排序优势越明显 以下为测试代码
public static void quickSort(List<int> list)
{
int s = list[0];
List<int> arrayAtemp = new List<int> { };
List<int> arrayBtemp = new List<int> { };
for (int i = 1; i < list.Count; i++)
{
if (list[i] > list[0]) arrayAtemp.Add(list[i]);
else if (list[i] <= list[0]) arrayBtemp.Add(list[i]);
}
if (arrayAtemp.Count > 1)
{
quickSort(arrayAtemp);
}
else
{
foreach (var a in arrayAtemp)
{
sortResult.Add(a);
}
}
sortResult.Add(s);
if (arrayBtemp.Count > 1)
{
quickSort(arrayBtemp);
}
else
{
foreach (var b in arrayBtemp)
{
sortResult.Add(b);
}
}
}
// 1 3 5 7 6 8 9
public static List<int> sortBubble(List<int> list)
{
for (int i = 0; i < list.Count(); i++)
{
for (int s =list.Count-1; s > i; s--)
{
if (list[i] > list[s])
{
list[i] = list[s] + list[i];
list[s] = list[i] - list[s];
list[i] = list[i] - list[s];
}
}
}
return list;
}
public static void text() {
sortResult.Clear();
List<int> list = new List<int> { };
Random r = new Random((int)DateTime.Now.Ticks);
Stopwatch swatch = new Stopwatch();
for (int i = 0; i < 20000; i++)
{
list.Add(r.Next(1, 999999));
}
swatch = new Stopwatch();
swatch.Start();
quickSort(list);
swatch.Stop();
Console.WriteLine("快速:" + swatch.Elapsed);
swatch = new Stopwatch();
swatch.Start();
List<int> sortResults = sortBubble(list);
Console.WriteLine("冒泡:" + swatch.Elapsed);
swatch.Stop();
}
static void Main(string[] args)
{
for (int i = 0; i < 10; i++)
{
text();
}
Console.Read();
}
当然 速度总是以内存为代价的 快速排序的内存占用也能吓你一跳 如果使用非递归 少创建点数组还会好点 后台做数据分析比较合适
快速排序由于排序是遍历的