几个高级排序

• 几个高级排序
  • Merge Sort
  • Merge Sort (Bottom to Up)
  • 快速排序

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.