03月14th
?? 对于大部排序算法来说,它们对数据集的操作无外乎:一、比较数据集中两个值;二、交换数据集中的两个值。只需设计这两个操作的接口即可。显然,如何比较比较数据要依数据类型和业务要求而定,而如何交换数据的值则与数据集结构和数据类型有关。另一方面,其实算法所决定的只有一点:要比较或交换的数据的位置,算法所关心的也只有一点:比较操作的结果(即返回值)。
综上,可以抽象一个这样的数据操作接口:一、比较,接受两个索引,返回比较结果;二、交换,接受两个索引,无返回值。算法将计算出的索引传递给接口,调用方负责实现具体的接口。
对于C#而言,此接口可以使用委托实现,而对于Java,则只能使用Interface来实现。相对来说,委托实现简洁一点,使用方需要做的工作也少一点,效率也应该会高一点。
对于这样的实现,甚至不要求源数据具有数据集的特征。我之前用这样的二分查找算法来查找电力线路的故障位置,在算法提供的索引位置处模拟故障计算故障值,与实测值进行比较,并返回比较结果给算法。算法根据比较结果决定下一个测试位置。这样,我没有定义线路各位置故障的故障数据集,仍然利用了这个算法。而事实上,避免计算所有位置的故障数据正是我的目的所在。
1、选择排序 ??
??2、冒泡排序 ??
??3、快速排序 ??
class QuickSorter
{
private void swap(ref int l, ref int r)
{
int temp;
temp = l;
l= r;
r= temp;
}
public void Sort(int[] list, int low, int high)
{
int pivot;//存储分支点
int l, r;
int mid;
if (high <= low)
return;
else if (high == low + 1)
{
if (list[low] > list[high])
swap(ref list[low], ref list[high]);
return;
}
mid = (low + high) >> 1;
pivot = list[mid];
swap(ref list[low], ref list[mid]);
l= low + 1;
r= high;
do
{
while (l <= r && list[l] <pivot)
l++;
while (list[r] >= pivot)
r--;
if (l < r)
swap(ref list[l], ref list[r]);
} while (l < r);
list[low] = list[r];
list[r] = pivot;
if (low + 1 < r)
Sort(list, low, r - 1);
if (r + 1 < high)
Sort(list, r + 1, high);
}
}??4、插入排序 ??
??5、希尔排序
??6、归并排序 ??
??7、基数排序 ??

//基数排序
public int[] RadixSort(
int[] ArrayToSort,
int digit)
{
//low to high digit
for (int k = 1; k <= digit; k++)
{
//temp array to store thesort result inside digit
int[] tmpArray = new int[ArrayToSort.Length];
//temp array forcountingsort

int[] tmpCountingSortArray = new int[10] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
//CountingSort
for (int i = 0; i < ArrayToSort.Length; i++)
{
//split the specifieddigit from the element
int tmpSplitDigit = ArrayToSort[i] / (int) Math.Pow(10, k - 1) - (ArrayToSort[i] /(int) Math.Pow(10, k)) * 10;
tmpCountingSortArray[tmpSplitDigit] += 1;
}
for (int m = 1; m < 10; m++)
{
tmpCountingSortArray[m] += tmpCountingSortArray[m -1];
}
//output the value toresult
for (int n = ArrayToSort.Length - 1; n >= 0;n--)
{
int tmpSplitDigit = ArrayToSort[n] / (int) Math.Pow(10, k - 1) - (ArrayToSort[n] /(int) Math.Pow(10, k)) * 10;
tmpArray[tmpCountingSortArray[tmpSplitDigit] - 1] =ArrayToSort[n];
tmpCountingSortArray[tmpSplitDigit] -= 1;
}
//copy the digit-inside sortresult to source array
for (int p = 0; p < ArrayToSort.Length; p++)
{
ArrayToSort[p] = tmpArray[p];
}
}
return ArrayToSort;
}??8、计数排序 ??
??9、小根堆排序 ??