Примерна имплементация на хийпсорт:
public void SortDownward(int[] array)
{
HeapifySiftDown(array);
var index = array.Length - 1;
while (index > 0)
{
Swap(array, index, 0);
index--;
SiftDown(array, 0, index);
}
}
private void HeapifySiftDown(int[] array)
{
var index = array.Length - 1;
while (index >= 0)
{
SiftDown(array, index, array.Length - 1);
index--;
}
}
private void SiftDown(int[] array, int start, int end)
{
var root = start;
while (root <= end)
{
var child = root;
var swap = root;
if (array[swap] < array[child])
swap = child;
// if there is a right child and it is greater
if (child + 1 <= end && array[swap] < array[child + 1])
swap = child + 1;
if (swap == root)
return;
Swap(array, root, swap);
root = swap;
}
}
private static void Swap(int[] array, int x, int y)
{
var temp = array[x];
array[x] = array[y];
array[y] = temp;
}
примерна имплементация на куиксорт
/// <summary>
/// Quicksort is a divide and conquer algorithm. An array is divided into two chunks - lower and
/// higher sub-arrays. Then both two chunks are quicksorted recursively. Two approaches are
/// available - Lomuto's and Hoare's approach.
/// </summary>
public class Quicksort
{
public void SortLomuto(int[] array)
{
Lomuto(array, 0, array.Length - 1);
}
public void SortHoare(int[] array)
{
Hoare(array, 0, array.Length - 1);
}
private void Lomuto(int[] array, int low, int high)
{
if (low < high)
{
var pivot = LomutoPartition(array, low, high);
Lomuto(array, low, pivot - 1);
Lomuto(array, pivot + 1, high);
}
}
private void Hoare(int[] array, int low, int high)
{
if (low < high)
{
var pivot = HoarePartition(array, low, high);
Hoare(array, low, pivot);
Hoare(array, pivot + 1, high);
}
}
private int LomutoPartition(int[] array, int low, int high)
{
var pivot = array[high];
var index = low;
for (var jIndex = low; jIndex < high; jIndex++)
{
if (array[jIndex] < pivot)
{
Swap(array, index, jIndex);
index += 1;
}
}
Swap(array, index, high);
return index;
}
private int HoarePartition(int[] array, int low, int high)
{
var pivot = array[low + (high - low) / 2];
var tempLow = low - 1;
var tempHigh = high + 1;
while (true)
{
do
tempLow++;
while (array[tempLow] < pivot);
do
tempHigh--;
while (array[tempHigh] > pivot);
if (tempLow >= tempHigh)
return tempHigh;
Swap(array, tempLow, tempHigh);
}
}
}
примерна имплементация на мерджсорт
public class Mergesort
{
public void SortTopDownWithSubArrays(ref int[] array)
{
var temp = TopDownSubArraysSort(array);
array = temp;
}
public void SortTopDownWorkingCopy(int[] array)
{
var workingCopy = new int[array.Length];
Array.Copy(array, 0, workingCopy, 0, array.Length);
TopDownSplitMerge(workingCopy, array, 0, array.Length);
}
public void SortBottomUpWorkingCopy(int[] array)
{
var workingCopy = new int[array.Length];
Array.Copy(array, 0, workingCopy, 0, array.Length);
BottomUpMergeSort(array, workingCopy);
}
private int[] TopDownSubArraysSort(int[] array)
{
if (array.Length <= 1)
return array;
var leftLength = array.Length / 2;
var left = new int[leftLength];
var right = new int[array.Length - leftLength];
Array.Copy(array, 0, left, 0, leftLength);
Array.Copy(array, leftLength, right, 0, right.Length);
left = TopDownSubArraysSort(left);
right = TopDownSubArraysSort(right);
return MergeSubArrays(left, right);
}
private int[] MergeSubArrays(int[] left, int[] right)
{
var result = new int[left.Length + right.Length];
var leftIndex = 0;
var rightIndex = 0;
var index = 0;
while (index < result.Length)
{
if (leftIndex < left.Length && rightIndex < right.Length)
{
if (left[leftIndex] <= right[rightIndex])
{
result[index] = left[leftIndex];
index++;
leftIndex++;
}
else
{
result[index] = right[rightIndex];
index++;
rightIndex++;
}
}
else if (leftIndex < left.Length)
{
result[index] = left[leftIndex];
index++;
leftIndex++;
}
else if (rightIndex < right.Length)
{
result[index] = right[rightIndex];
index++;
rightIndex++;
}
}
return result;
}
private void TopDownSplitMerge(int[] source, int[] destination, int start, int end)
{
if (end - start < 2) // if sorted
return;
var median = (end + start) / 2;
TopDownSplitMerge(destination, source, start, median);
TopDownSplitMerge(destination, source, median, end);
TopDownMerge(source, destination, start, median, end);
}
private void TopDownMerge(int[] source, int[] destination, int start, int median, int end)
{
var indexStart = start;
var indexMedian = median;
for (int index = start; index < end; index++)
{
if (indexStart < median && (indexMedian >= end || source[indexStart] <= source[indexMedian]))
{
destination[index] = source[indexStart];
indexStart++;
}
else
{
destination[index] = source[indexMedian];
indexMedian++;
}
}
}
private void BottomUpMergeSort(int[] source, int[] destination)
{
for (int index = 1; index < source.Length; index *= 2)
{
for (int jIndex = 0; jIndex < source.Length; jIndex += 2 * index)
{
BottomUpMerge(
source,
destination,
jIndex,
Math.Min(index + jIndex, source.Length),
Math.Min(jIndex + 2 * index, source.Length));
}
Array.Copy(destination, source, source.Length);
}
}
private void BottomUpMerge(int[] source, int[] destination, int left, int right, int end)
{
var indexLeft = left;
var indexRight = right;
for (int index = left; index < end; index++)
{
if (indexLeft < right && (indexRight >= end || source[indexLeft] <= source[indexRight]))
{
destination[index] = source[indexLeft];
indexLeft++;
}
else
{
destination[index] = source[indexRight];
indexRight++;
}
}
}
}
и да речем, може да получа:
Dry run algorithms...
Generating int array with 10000 elements
Quicksort Lomuto: 00:00:00.0031586
Quicksort Hoare: 00:00:00.0029382
Mergesort Top-Down with Subarrays: 00:00:00.0053670
Mergesort Top-Down with Working Copy: 00:00:00.0032543
Mergesort Bottom-Up with Working Copy: 00:00:00.0041929
Heapsort SiftDown: 00:00:02.3419572
ПС: Не съм имплементирал още sift up на хийп сорта