C#实现各种排序
每种排序的要点和实现
目录文章中参数Func<T, T, bool> comp
的意思是:排序后对于任意i < j
,不可能有comp(list[j], list[i])
冒泡排序
- 每次循环都将最值放到最前或者最后
- 倒着排序,只需访问一次
list.Count
(可选) - 使用
sorted
布尔变量,如果中途已经排序好了就不用继续排了(可选) - 稳定,最值稳定上浮
public static void BubbleSort<T>(IList<T> list)
where T : IComparable<T>
{
for (int i = list.Count; i > 0; i--)
{
bool sorted = true;
for (int j = 1; j < i; j++)
{
if (list[j].CompareTo(list[j - 1]) < 0)
{
T swap = list[j - 1];
list[j - 1] = list[j];
list[j] = swap;
sorted = false;
}
}
if (sorted)
return;
}
}
public static void BubbleSort<T>(IList<T> list, Func<T, T, bool> comp)
{
for (int i = list.Count; i > 0; i--)
{
bool sorted = true;
for (int j = 1; j < i; j++)
{
if (comp(list[j], list[j - 1]))
{
T swap = list[j - 1];
list[j - 1] = list[j];
list[j] = swap;
sorted = false;
}
}
if (sorted)
return;
}
}
选择排序
- 每次都选出未排序段的最值,加入排序段
- 倒着排序,只需访问一次
list.Count
(可选) - 不稳定,最值放入排序段时与最值交换的数位置改变
public static void SelectionSort<T>(IList<T> list)
where T : IComparable<T>
{
for (int i = list.Count - 1; i > 0; i--)
{
int maxIndex = i;
T maxValue = list[i];
for (int j = i - 1; j >= 0; j--)
{
T value = list[j];
if (maxValue.CompareTo(value) < 0)
{
maxValue = value;
maxIndex = j;
}
}
T swap = list[i];
list[i] = list[maxIndex];
list[maxIndex] = swap;
}
}
public static void SelectionSort<T>(IList<T> list, Func<T, T, bool> comp)
{
for (int i = list.Count - 1; i > 0; i--)
{
int maxIndex = i;
T maxValue = list[i];
for (int j = i - 1; j >= 0; j--)
{
T value = list[j];
if (comp(maxValue, value))
{
maxValue = value;
maxIndex = j;
}
}
T swap = list[i];
list[i] = list[maxIndex];
list[maxIndex] = swap;
}
}
插入排序
- 将新值插入已排序的一段中
- 排序段已排序,可以使用二分搜索寻找插入位置(可使用其他方式)
- 稳定,插入时遇到相同值保持相对位置
public static void InsertionSort<T>(IList<T> list)
where T : IComparable<T>
{
int count = list.Count;
for (int i = 1; i < count; i++)
{
T insert = list[i];
int low = -1, high = i;
do
{
int mid = ((high - low) >> 1) + low;
if (insert.CompareTo(list[mid]) < 0)
high = mid;
else
low = mid;
} while (low + 1 != high);
for (int j = i; j > high; j--)
list[j] = list[j - 1];
list[high] = insert;
}
}
public static void InsertionSort<T>(IList<T> list, Func<T, T, bool> comp)
{
int count = list.Count;
for (int i = 1; i < count; i++)
{
T insert = list[i];
int low = -1, high = i;
do
{
int mid = ((high - low) >> 1) + low;
if (comp(insert, list[mid]))
high = mid;
else
low = mid;
} while (low + 1 != high);
for (int j = i; j > high; j--)
list[j] = list[j - 1];
list[high] = insert;
}
}
希尔排序
- 每次循环结束后,将相隔距离为一个区间的值看作一组,这一组是有序的
- 区间大小和区间每次缩小的倍数是可以选择的
- 不稳定,值可能会跳到另一个区间中
public static void ShellSort<T>(IList<T> list)
where T : IComparable<T>
{
int count = list.Count;
int seg = (count >> 1) + 1;
while (seg > 0)
{
for (int i = seg; i < count; i++)
{
for (int j = i;
j >= seg && list[j].CompareTo(list[j - seg]) < 0;
j -= seg)
{
T swap = list[j];
list[j] = list[j - seg];
list[j - seg] = swap;
}
}
seg /= 2;
}
}
public static void ShellSort<T>(IList<T> list, Func<T, T, bool> comp)
{
int count = list.Count;
int seg = (count >> 1) + 1;
while (seg > 0)
{
for (int i = seg; i < count; i++)
{
for (int j = i;
j >= seg && comp(list[j], list[j - seg]);
j -= seg)
{
T swap = list[j];
list[j] = list[j - seg];
list[j - seg] = swap;
}
}
seg /= 2;
}
}
堆排序
- 数组\(\rightarrow\)堆\(\rightarrow\)已排序的数组
- 堆是完全二叉树,完全二叉树可以用数组实现
- 计算机倾向于将相邻地址的值同时载入,索引在数组中跳跃幅度过大,难以利用此功能
- 不稳定,值在堆中移动,相同的值的相对位置受它们之间的值的影响
public static void HeapSort<T>(IList<T> list)
where T : IComparable<T>
{
int i = 0, count = list.Count;
while (++i < count)
{
int j = i;
int up;
while (j > 0 && list[up = (j - 1) >> 1].CompareTo(list[j]) < 0)
{
T swap = list[up];
list[up] = list[j];
list[j] = swap;
j = up;
}
}
while (--i > 0)
{
T swap = list[i];
list[i] = list[0];
list[0] = swap;
int j = 0;
int down;
while ((down = (j << 1) + 1) < i)
{
if (down + 1 < i && list[down].CompareTo(list[down + 1]) < 0)
down++;
if (list[down].CompareTo(list[j]) < 0)
break;
swap = list[down];
list[down] = list[j];
list[j] = swap;
j = down;
}
}
}
public static void HeapSort<T>(IList<T> list, Func<T, T, bool> comp)
{
int i = 0, count = list.Count;
while (++i < count)
{
int j = i;
int up;
while (j > 0 && comp(list[up = (j - 1) >> 1], list[j]))
{
var swap = list[up];
list[up] = list[j];
list[j] = swap;
j = up;
}
}
while (--i > 0)
{
var swap = list[i];
list[i] = list[0];
list[0] = swap;
int j = 0;
int down;
while ((down = (j << 1) + 1) < i)
{
if (down + 1 < i && comp(list[down], list[down + 1]))
down++;
if (comp(list[down], list[j]))
break;
swap = list[down];
list[down] = list[j];
list[j] = swap;
j = down;
}
}
}
归并排序
- 自底向上合并有序数组
- 使用辅助数组,使用指针使原数组和辅助数组身份多次交换,最后将结果放回原数组
- 稳定,合并有序数组时不改变相对位置
public static void MergeSort<T>(IList<T> list)
where T : IComparable<T>
{
int count = list.Count;
IList<T> a = list;
IList<T> b = new T[count];
for (int seg = 1; seg < count; seg <<= 1)
{
for (int low = 0; low < count; low += seg << 1)
{
int mid = Math.Min(count, low + seg);
int high = Math.Min(count, low + (seg << 1));
int i = low, j = mid, k = low;
while (i != mid && j != high)
b[k++] = a[j].CompareTo(a[i]) < 0 ? a[j++] : a[i++];
while (i != mid)
b[k++] = a[i++];
while (j != high)
b[k++] = a[j++];
}
var swap = a;
a = b;
b = swap;
}
if (!ReferenceEquals(a, list))
for (int i = 0; i != count; i++)
list[i] = a[i];
}
public static void MergeSort<T>(IList<T> list, Func<T, T, bool> comp)
{
int count = list.Count;
IList<T> a = list;
IList<T> b = new T[count];
for (int seg = 1; seg < count; seg <<= 1)
{
for (int low = 0; low < count; low += seg << 1)
{
int mid = Math.Min(count, low + seg);
int high = Math.Min(count, low + (seg << 1));
int i = low, j = mid, k = low;
while (i != mid && j != high)
b[k++] = comp(a[j], a[i]) ? a[j++] : a[i++];
while (i != mid)
b[k++] = a[i++];
while (j != high)
b[k++] = a[j++];
}
var swap = a;
a = b;
b = swap;
}
if (!ReferenceEquals(a, list))
for (int i = 0; i != count; i++)
list[i] = a[i];
}
快速排序
- 自顶向下使用基准分割数组
- 使用随机数选择基准(可选)
- 使用双指针分别从前往后和从后往前(可使用其他方式)
- 不稳定,双指针的交换会改变顺序
public static void QuickSort<T>(IList<T> list)
where T : IComparable<T>
{
Stack<(int, int)> ranges = new Stack<(int, int)>();
Random rand = new Random();
ranges.Push((0, list.Count));
while (ranges.Count != 0)
{
(int low, int high) = ranges.Pop();
if (high <= low + 1)
continue;
int temp = rand.Next(low, high);
T sep = list[temp];
list[temp] = list[low];
list[low] = sep;
int i = low, j = high;
for (; ; )
{
do
i++;
while (i < high && list[i].CompareTo(sep) < 0);
do
j--;
while (sep.CompareTo(list[j]) < 0);
if (i > j)
break;
T swap = list[i];
list[i] = list[j];
list[j] = swap;
}
list[low] = list[j];
list[j] = sep;
ranges.Push((low, j));
ranges.Push((i, high));
}
}
public static void QuickSort<T>(IList<T> list, Func<T, T, bool> comp)
{
Stack<(int, int)> ranges = new Stack<(int, int)>();
Random rand = new Random();
ranges.Push((0, list.Count));
while (ranges.Count != 0)
{
(int low, int high) = ranges.Pop();
if (high - low <= 1)
continue;
int temp = rand.Next(low, high);
T sep = list[temp];
list[temp] = list[low];
list[low] = sep;
int i = low, j = high;
for (; ; )
{
do
i++;
while (i < high && comp(list[i], sep));
do
j--;
while (comp(sep, list[j]));
if (i > j)
break;
T swap = list[i];
list[i] = list[j];
list[j] = swap;
}
list[low] = list[j];
list[j] = sep;
ranges.Push((low, j));
ranges.Push((i, high));
}
}
标签:count,C#,list,seg,int,算法,swap,排序
From: https://www.cnblogs.com/violeshnv/p/16831729.html