几个高级排序
Merge Sort
定义
Merge Sort是建立在归并操作上的一种有效的排序方法, 效率为O(n*log(n)). 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用, 求各层分治可以同时进行.
算法(C#)
public class MergeSort
{
/// <summary>
/// 归并排序
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="arr"></param>
/// <returns></returns>
public static T[] Sort<T>(T[] arr)where T:IComparable
{
T[] aux = new T[arr.Length]; //建立辅助列表
Sort(ref arr, ref aux, 0, arr.Length - 1);
return arr;
}
private static void Sort<T>(ref T[] arr, ref T[] aux, int begin, int end) where T : IComparable
{
if (begin < end) //当begin和end相等时跳出
return;
int mid = (end + begin) / 2;
Sort(ref arr, ref aux, begin, mid);
Sort(ref arr, ref aux, mid + 1, end);
Merge(ref arr, ref aux, begin, mid, end); //对分块排序
}
private static void Merge<T>(ref T[] arr, ref T[] aux, int begin, int mid, int end) where T : IComparable
{
int left = begin;
int right = mid + 1;
int index = 0;
while (left<=mid && right<=end) { //左右数组比较大小再将小的放入辅助数组
aux[index++] = arr[left].CompareTo(arr[right]) <= 0 ? arr[left++] : arr[right++];
}
while(left<=mid)//将左边剩余元素填充进aux中
aux[index++] = arr[left++];
while(right<=end)//将右序列剩余元素填充进aux中
aux[index++] = arr[right++];
index = 0;
//将aux中的元素全部拷贝到原数组中
while(begin <= end)
arr[begin++] = aux[index++];
}
}其实最重要的就是以下的递归操作.
Sort(ref arr, ref aux, begin, mid);
Sort(ref arr, ref aux, mid + 1, end);
Merge(ref arr, ref aux, begin, mid, end); //对分块排序其实这个是从别人的Java代码对int[]进行MergeSort拿出来做成泛型的, 因为我一直不能理解网上各种乱七八糟的代码, 自己又写不出来这个递归QAQ…
花了我好长时间, 真的好蠢…
Merge Sort (Bottom to Up)
谁能想到, 在我写完递归算法后, 立马就讲了一个Bottom to Up的算法, 易读性马上暴涨一百倍!!!
public static T[] Sort<T>(T[] arr)where T:IComparable
{
int N = arr.Length;
T[] aux = new T[N];
for(int sz = 1; sz <N; sz *= 2) {
//size 每次x2
for (int low = 0; low < N-sz; low+=2*sz) {
//最低索引每次增加两倍的size
Merge(ref arr, ref aux, low, low + sz - 1,
Math.Min(low + 2 * sz - 1, N - 1));
}
}
return arr;
}Merge方法完全不用变化!!!
复杂度分析
Merge Sort是一个稳定的排序算法
无论数据如何分布, Merge Sort总是以O(nlog(n))的时间复杂度进行排序, 不过需要额外占用n单位(Array)或log(n)单位(Link list)的空间.
快速排序
定义
快速排序(英语：Quicksort), 又称分区交换排序(partition-exchange sort), 简称快排, 一种排序算法, 最早由东尼·霍尔提出. 在平均状况下, 排序n个项目要{\displaystyle \ O(n\log n)}次比较.在最坏状况下则需要{\displaystyle O(n^{2})}次比较, 但这种状况并不常见. 事实上, 快速排序{\displaystyle \Theta (n\log n)}通常明显比其他算法更快, 因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成.
伪代码
function quicksort(q)
{
var list less, pivotList, greater
if length(q) ≤ 1
return q
else
{
select a pivot value pivot from q
for each x in q except the pivot element
{
if x < pivot then add x to less
if x ≥ pivot then add x to greater
}
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))
}
}真代码
private static void Sort<T>(ref T[] arr, int begin, int end) where T IComparable {
if (end<=begin) return;
int partition = Partition(ref arr, begin, end);
Sort(ref arr, begin, partition - 1);
Sort(ref arr, partition+1, end);
}
private static int Partition<T>(ref T[] arr, int begin, int end) where : IComparable {
int i = begin, j = end + 1;
while (true) {
while (arr[++i].CompareTo(arr[begin]) < 0) //循环直到i处大于beg的元素
if (i==end)
break;
while (arr[--j].CompareTo(arr[begin]) > 0) //循环直到j处小于beg的元素
if (j==begin)
break;
if (i >= j) break; //ij相等则弹出
Swap(ref arr, i, j); //交换ij位置
}
Swap(ref arr, begin,j); //交换隔板和j的位置
return j; //返回隔板值
}
值得注意的是, 我之前把i当作隔板值, 因为我认为i在任何时候都是相等的, 但是不然, 在最后一次计算ij值时, j可能比i大1.
复杂度分析
-
Best Case:
每次都在中间被分割, 复杂度为nLg(n); -
Worst Case:
已排好序, 隔板从头遍历至尾, 复杂度为\frac{1}{2}n^2; -
Average Cost:
变种
通过使用辅助数组可以完成稳定的QuickSort.
