Sort
评价排序算法的标准
- 时间复杂度
- 空间复杂度
- 稳定性：如果一个排序算法能够保留数组中的重复元素的相对位置，则可以被称为是稳定的
冒泡排序
通过两两交换，每次循环都使最值上浮到开头或末尾
关键点在于每次循环结束后都将最值排在开头或末尾
public static void BubbleSort<T>(IList<T> list) where T : IComparable<T>
{
T temp;
for (int i = 1; i != list.Count; ++i) // 以从小到大的顺序作示范
{
bool sorted = true; // 如果在一趟遍历中没有需要移动的元素，那么说明已经排序好了
for (int j = 1; j != list.Count - i + 1; ++j)
{
if (list[j].CompareTo(list[j - 1]) < 0) // 将大的值放在更后面
{
temp = list[j];
list[j] = list[j - 1];
list[j - 1] = temp;
sorted = false;
}
}
if (sorted) return;
}
}
插入排序
就如同打牌时整理的方法，为新来的值在已有的排好序的数组中找好位置
public static void InsertionSort<T>(IList<T> list) where T : IComparable<T>
{
int count = list.Count;
if (count <= 1)
return;
T temp;
for (int i = 1; i != count; ++i)
{
int low = -1, high = i; // 鉴于前i个数已经排序好了，我们可以用二分搜索寻找位置
while (low + 1 != high) // assert: list[low] <= list[i]
{
int mid = (high - low) / 2 + low;
if (list[i].CompareTo(list[mid]) < 0)
high = mid;
else
low = mid;
} // 此时low + 1就是所求的位置
temp = list[i];
for (int j = i - 1; j != low; --j) // (low, i - 1]的数后移为新数提供位置
list[j + 1] = list[j];
list[low + 1] = temp;
}
}
选择排序
很好理解，在数组中找到最小（大）值之后放到开头（末尾）
public static void SelectionSort<T>(IList<T> list) where T : IComparable<T>
{
T temp;
for (int i = list.Count - 1; i > 0; --i)
{
int max = i;
for (int j = i - 1; j >= 0; --j)
if (list[max].CompareTo(list[j]) < 0)
max = j; // 寻找最大值
temp = list[i];
list[i] = list[max];
list[max] = temp;
}
}
希尔排序
希尔排序是插入排序的改进
- 使数组中任意间隔为seg的有序
- 令seg逐渐减小
- seg为1时数组有序
public static void ShellSort<T>(IList<T> list) where T : IComparable<T>
{
int count = list.Count;
int seg = 1;
T temp;
while (seg < count / 3)
seg = seg * 3 + 1;
while (seg > 0)
{
for (int i = seg; i < count; ++i)
{
temp = list[i];
int j;
for (j = i; j >= seg && temp.CompareTo(list[j - seg]) < 0; j -= seg)
list[j] = list[j - seg];
list[j] = temp;
}
seg /= 3;
}
}
归并排序
- 归并：将两个有序数组合成为一个有序数组
归并排序是基于归并手法和分治法思想的排序
- 长度为一的数组自然是有序的
- 将两个长度为一的有序数组合成为一个长度为二的有序数组
- 将两个长度为二的有序数组合成为一个长度为四的有序数组
- ...
- 直到将整个数组排序完
public static void MergeSort<T>(IList<T> list) where T : IComparable<T>
{
int count = list.Count;
if (count <= 1)
return;
IList<T> b = new T[count];
IList<T> a = list;
for (int seg = 1; seg < count; seg <<= 1)
{
for (int start = 0; start < count; start += seg << 1)
{
int low = start, high = Math.Min(low + (seg << 1), count), mid = Math.Min(low + seg, count);
int i = low, j = mid, k = low; // 归并a[low:mid], a[mid:high]
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 temp = a;
a = b;
b = temp; // 此时a指向更有序的数组
}
if (object.ReferenceEquals(b, list))
for (int i = 0; i != count; ++i)
list[i] = a[i];
}
堆排序
先将数组变为堆，再将堆变为排序好的数组
- 堆：一种完全二叉树，满足其父节点的值大于（小于）子节点，称为最大堆（最小堆）
- 完全二叉树可以用数组来实现
public static void HeapSort<T>(IList<T> list) where T : IComparable<T>
{
int index = 0, count = list.Count;
T temp; // swap
// Array -> Heap
while (++index < count) // 使用最大堆
{
int up;
int i = index;
while (i > 0 && list[up = (i - 1) >> 1].CompareTo(list[i]) < 0) // 子节点大于父节点，就交换
{
temp = list[up];
list[up] = list[i];
list[i] = temp;
i = up;
}
}
// Heap -> Sorted
while (--index != 0)
{
temp = list[0];
list[0] = list[index];
list[index] = temp;
int i = 0;
int down;
while ((down = (i << 1) + 1) < index)
{
if (down + 1 < index && list[down].CompareTo(list[down + 1]) < 0) // 如果有子节点大于父节点，就交换
++down;
if (list[down].CompareTo(list[i]) < 0)
break;
temp = list[down];
list[down] = list[i];
list[i] = temp;
i = down;
}
}
}
快速排序
基于分治法的一种排序，也是最被广泛应用的排序
- 寻找基准值
- 将小于基准值的放在左边，大于基准值的放在右边，基准值放中间
- 此时再对左右两侧进行1、2步直到长度为一
public static void QuickSort<T>(IList<T> list) where T : IComparable<T>
{
int count = list.Count;
if (count <= 1)
return;
(int, int)[] range = new (int, int)[count];
T temp, sep;
int p = 0;
range[p++] = (0, count); // 用作栈，保存始末位置
while (p != 0)
{
(int start, int stop) = range[--p];
if (start + 2 > stop)
continue;
sep = list[start];
int i = start, j = stop;
while (true)
{
do ++i; // 此时list[i] <= sep，所以先让i递增一位
while (i < stop && list[i].CompareTo(sep) < 0); // 循环结束后有list[i] >= sep
do --j; // 此时j == stop || list[j] >= sep， 所以先让j递减一位
while (list[j].CompareTo(sep) > 0); // 循环结束后有list[j] <= sep
// list[start]是哨兵，j == start时会自动停下
if (i > j)
break; // 已经分好左右两边了
temp = list[i];
list[i] = list[j];
list[j] = temp; // 使list[i] <= sep && list[j] >= sep
}
list[start] = list[j];
list[j] = sep;
range[p++] = (start, j);
range[p++] = (j + 1, stop);
}
}
计数排序
已知数组上限和下限，用一个辅助数组累计各个数出现的次数
public static void CountSort(IList<int> list, int lowerBound, int upperBound)
{
int[] count = new int[upperBound - lowerBound];
int index = 0;
foreach (int i in list)
++count[i - lowerBound];
for (int i = 0; i != count.Length; ++i)
for (int j = 0, c = count[i]; j != c; ++j)
list[index++] = i + lowerBound;
}
桶排序
将数分为几组，再对每组数进行排序
public static void BucketSort(IList<int> list, int bucketNum,
int lowerBound, int upperBound)
{
var buckets = new System.Collections.Generic.List<int>[bucketNum];
for (int i = 0; i != bucketNum; ++i)
buckets[i] = new();
foreach (int i in list)
buckets[(int)((double)(i - lowerBound) /
(upperBound - lowerBound) *
bucketNum)].Add(i);
foreach (var li in buckets)
QuickSort(li);
int index = 0;
foreach (var li in buckets)
foreach (int i in li)
list[index++] = i;
}
性能分析
当以上述算法实现时
| 算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 冒泡排序 | \(O(n^2)\) | \(O(1)\) | \(\surd\) |
| 选择排序 | \(O(n^2)\) | \(O(1)\) | \(\surd\) |
| 插入排序 | \(O(n^2)\) | \(O(1)\) | \(\surd\) |
| 希尔排序 | \(?\) | \(O(1)\) | |
| 堆排序 | \(O(n\log{n})\) | \(O(1)\) | |
| 归并排序 | \(O(n\log{n})\) | \(O(n)\) | \(\surd\) |
| 快速排序 | \(O(n\log{n})\) | \(O(n)\) |