算法-快速排序

发表于 更新于 分类于 ， 阅读次数： 
关于排序算法，不得不说排序算法。排序算法被认为是冒泡算法的优化，以优异的平均算法复杂度【O(nlgn)】而著名。
算法思想主要分为2个步骤：
（1）划分数组a[p..r]为两个子数组a[p,i-1],a[i+1,r],使得a[p,i-1]中的数都小于等于a[i],a[i+1,r]中的数都大于等于a[i] 
（2）递归对a[p,i-1],a[i+1,r]分别排序
*算法核心是如何分割为比基准数小的数组和比基准数大的数组，对应一下Partition方法
下面是代码部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public static class SortingSupport 
{
    public delegate bool CompareLess<T>(T t1, T t2);

    static void Swap<T>(T[] a, int i, int j)
    {
        T temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    #region 快速排序
    public static void QuickSort<T>(T[] a, CompareLess<T> cp)
    {
        QSort(a, 0, a.Length - 1, cp);
    }

    /// <summary>
    /// *递归保证子数组有序
    /// </summary>
    static void QSort<T>(T[] a,int p,int r, CompareLess<T> cp)
    {
        if (p >= r)
            return;
        int i = Partition(a, p, r, cp);
        QSort(a, p, i - 1, cp);
        QSort(a, i + 1, r, cp);
    }

    /// <summary>
    /// *分割数字保证所有 a[p..i-1] <= p[i] && a[i+1..r] >= p[i]
    /// </summary>
    static int Partition<T>(T[] a,int p, int r, CompareLess<T> cp)
    {
        T x = a[r];
        int i = p - 1;
        for(int j = p;j < r ;j ++)
        {
            if(cp(a[j],x))
            {
                i++;
                Swap(a, i, j);
            }
        }
        Swap(a, i + 1, r);
        return i + 1;
    }
    #endregion
}