我现在正在学习不同类型的排序,发现从某一点开始,我的快速排序算法根本就不那么快了。
以下是我的代码:
class QuickSort
{
// partitioning array on the key so that the left part is <=key, right part > key
private int Partition(int[] arr, int start, int end)
{
int key = arr[end];
int i = start - 1;
for (int j = start; j < end; j++)
{
if (arr[j] <= key) Swap(ref arr[++i], ref arr[j]);
}
Swap(ref arr[++i], ref arr[end]);
return i;
}
// sorting
public void QuickSorting(int[] arr, int start, int end)
{
if (start < end)
{
int key = Partition(arr, start, end);
QuickSorting(arr, start, key - 1);
QuickSorting(arr, key + 1, end);
}
}
}
class Test
{
static void Main(string[] args)
{
QuickSort quick = new QuickSort();
Random rnd = new Random(DateTime.Now.Millisecond);
int[] array = new int[1000000];
for (int i = 0; i < 1000000; i++)
{
int i_rnd = rnd.Next(1, 1000);
array[i] = i_rnd;
}
quick.QuickSorting(array, 0, array.Length - 1);
}
}
在一个包含一百万个元素的数组上运行这段代码大约需要15秒的时间。而例如MergeSort或HeapSort则可以在不到一秒钟的时间内完成相同的任务。
您能否解释一下为什么会出现这种情况?