新手请教,谢谢!
大家好,我现在用C#实现了快排,但是还需要用一个计数器来计算内部的key comparison,是我不太清楚该怎样实现。希望高手教我,我把源码贴出来了,谢谢大家!using System;
using
using System.Data;
namespace coreQuickSort
{
public class QuickSort
{
private void Swap(ref int i, ref int j)
//swap two integer
{
int t;
t = i;
i = j;
j = t;
}
public QuickSort()
{ }
public void Sort(int[] list)
{
Sort(list, 0, list.Length - 1);
}
public void Sort(int[] list)
{
Sort(list, 0, list.Length - 1);
}
public void Sort(int[] list, int low, int high)
{
if (high <= low)
{
//only one element in array list
//so it do not need sort
return;
}
else if (high == low + 1)
{
//means two elements in array list
//so we just compare them
if (list[low] > list[high])
{
//exchange them
Swap(ref list[low], ref list[high]);
return;
}
}
//more than 3 elements in the arrary list
//begin QuickSort
myQuickSort(list, low, high);
}
public void myQuickSort(int[] list, int low, int high)
{
if (low < high)
{
int pivot = Partition(list, low, high);
myQuickSort(list, low, pivot - 1);
myQuickSort(list, pivot + 1, high);
}
}
private int Partition(int[] list, int low, int high)
{
//get the pivot of the arrary list
int pivot;
pivot = list[low];
while (low < high)
{
while (low < high && list[high] >= pivot)
{
high--;
}
if (low != high)
{
Swap(ref list[low], ref list[high]);
low++;
}
while (low < high && list[low] <= pivot)
{
low++;
}
if (low != high)
{
Swap(ref list[low], ref list[high]);
high--;
}
}
return low;
}
public class MainClass
{
public static void Main()
{
int[] iArrary = new int[] { 1, 5, 13, 6, 10, 55, 99, 2, 87, 12, 34, 75, 33, 47 };
QuickSort sh = new QuickSort();
sh.Sort(iArrary);
for (int m = 0; m < iArrary.Length; m++)
Console.Write("{0} ", iArrary[m]);
Console.WriteLine();
}
}
}
}