class SortHelper
{
#region 冒泡排序
/// <summary>
/// 冒泡排序
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="compare"></param>
/// <returns></returns>
public static IList<T> BubbleSort<T>(IList<T> list, Comparison<T> compare)
{
T temp;
for (int i = 0; i < list.Count - 1; i++)
{
for (int j = list.Count - 1; j > i; j--)
{
if (compare(list[j - 1], list[j]) > 0)
{
temp = list[j - 1];
list[j - 1] = list[j];
list[j] = temp;
}
}
}
return list;
}
#endregion
#region 快速排序
/// <summary>
/// 快速排序
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="compare"></param>
/// <returns></returns>
public static IList<T> QuickSort<T>(IList<T> list, Comparison<T> compare)
{
return QuickSort(list, 0, list.Count - 1, compare);
}
private static IList<T> QuickSort<T>(IList<T> list, int left, int right, Comparison<T> compare)
{
if (left < right)
{
int index = Division(list, left, right, compare);
QuickSort(list, left, index - 1, compare);
QuickSort(list, index + 1, right, compare);
}
return list;
}
private static int Division<T>(IList<T> list, int left, int right, Comparison<T> compare)
{
T baseObj = list[left];
while (left < right)
{
while (left < right && compare(list[right], baseObj) >= 0)
right -= 1;
list[left] = list[right];
while (left < right && compare(list[left], baseObj) <= 0)
left += 1;
list[right] = list[left];
}
list[left] = baseObj;
return left;
}
#endregion
#region 直接选择排序
/// <summary>
/// 直接选择排序
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="compare"></param>
/// <returns></returns>
public static IList<T> SelectionSort<T>(IList<T> list, Comparison<T> compare)
{
for (int i = 0; i < list.Count - 1; i++)
{
int tempIndex = i;
for (int j = i + 1; j < list.Count; j++)
{
if (compare(list[tempIndex], list[j]) > 0)
{
tempIndex = j;
}
}
var tempObj = list[tempIndex];
list[tempIndex] = list[i];
list[i] = tempObj;
}
return list;
}
#endregion
#region 堆排序
/// <summary>
/// 堆排序
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="compare"></param>
/// <returns></returns>
public static IList<T> HeapSort<T>(IList<T> list, Comparison<T> compare)
{
//list.Count/2-1:就是堆中父节点的个数
for (int i = list.Count / 2 - 1; i >= 0; i--)
{
HeapAdjust(list, i, list.Count, compare);
}
//最后输出堆元素
for (int i = list.Count - 1; i > 0; i--)
{
//堆顶与当前堆的第i个元素进行值对调
T temp = list[0];
list[0] = list[i];
list[i] = temp;
//因为两值交换，可能破坏根堆，所以必须重新构造
HeapAdjust(list, 0, i, compare);
}
return list;
}
/// <summary>
/// 构建堆
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="parent"></param>
/// <param name="length"></param>
/// <param name="compare"></param>
private static void HeapAdjust<T>(IList<T> list, int parent, int length, Comparison<T> compare)
{
//temp保存当前父节点
T temp = list[parent];
//得到左孩子
int child = 2 * parent + 1;
while (child < length)
{
//如果parent有右孩子，则要判断左孩子是否小于右孩子
if (child + 1 < length && compare(list[child], list[child + 1]) < 0)
{
child++;
}
//父亲节点大于子节点，就不用做交换
if (compare(temp, list[child]) >= 0)
{
break;
}
//将较大子节点的值赋给父亲节点
list[parent] = list[child];
//然后将子节点做为父亲节点，已防止是否破坏根堆时重新构造
parent = child;
//找到该父亲节点较小的左孩子节点
child = 2 * parent + 1;
}
//最后将temp值赋给较大的子节点，以形成两值交换
list[parent] = temp;
}
#endregion
#region 直接插入排序
/// <summary>
/// 直接插入排序
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="compare"></param>
/// <returns></returns>
public static IList<T> InsertSort<T>(IList<T> list, Comparison<T> compare)
{
// 无序序列
for (int i = 1; i < list.Count; i++)
{
var temp = list[i];
int j = i - 1;
// 有序序列
for (; j >= 0 && compare(temp, list[j]) < 0; j--)
{
list[j + 1] = list[j];
}
list[j + 1] = temp;
}
return list;
}
#endregion
#region 希尔排序
/// <summary>
/// 希尔排序
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="compare"></param>
/// <returns></returns>
public static IList<T> ShellSort<T>(IList<T> list, Comparison<T> compare)
{
int step = list.Count / 2;
while (step >= 1)
{
// 无序序列
for (int i = step; i < list.Count; i++)
{
var temp = list[i];
int j = i - step;
// 有序序列
for (; j >= 0 && compare(temp, list[j]) < 0; j = j - step)
{
list[j + step] = list[j];
}
list[j + step] = temp;
}
step = step / 2;
}
return list;
}
#endregion
#region 归并排序
public static IList<T> MergeSort<T>(IList<T> list, Comparison<T> compare)
{
return MergeSort(list, new T[list.Count], 0, list.Count - 1, compare);
}
private static IList<T> MergeSort<T>(IList<T> list, IList<T> tempList, int left, int right, Comparison<T> compare)
{
if (left < right)
{
//取分割位置
int middle = (left + right) / 2;
//递归划分数组左序列
MergeSort(list, tempList, left, middle, compare);
//递归划分数组右序列
MergeSort(list, tempList, middle + 1, right, compare);
//数组合并操作
Merge(list, tempList, left, middle + 1, right, compare);
}
return list;
}
/// <summary>
/// 数组的两两合并操作
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="tempList"></param>
/// <param name="left"></param>
/// <param name="middle"></param>
/// <param name="right"></param>
/// <param name="compare"></param>
private static void Merge<T>(IList<T> list, IList<T> tempList, int left, int middle, int right, Comparison<T> compare)
{
//左指针尾
int leftEnd = middle - 1;
//右指针头
int rightStart = middle;
//临时数组的下标
int tempIndex = left;
//数组合并后的length长度
int tempLength = right - left + 1;
//先循环两个区间段都没有结束的情况
while ((left <= leftEnd) && (rightStart <= right))
{
//如果发现有序列大，则将此数放入临时数组
if (compare(list[left], list[rightStart]) < 0)
tempList[tempIndex++] = list[left++];
else
tempList[tempIndex++] = list[rightStart++];
}
//判断左序列是否结束
while (left <= leftEnd)
tempList[tempIndex++] = list[left++];
//判断右序列是否结束
while (rightStart <= right)
tempList[tempIndex++] = list[rightStart++];
//交换数据
for (int i = 0; i < tempLength; i++)
{
list[right] = tempList[right];
right--;
}
}
#endregion
}