算法-排序

发表于 更新于 分类于
本文字数： 6.7k 阅读时长 ≈ 6 分钟

选择排序|插入排序|希尔排序|归并排序|快速排序|堆排序

通用模板

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
public class Example
{
    public static void sort(Comparable[] a)
    {
        //详见下文
    }

    private static boolean less(Comparable v, Comparable w)
    { return v.compareTo(w) < 0; }

    private static void exch(Comparable[] a, int i, int j)
    { Comparable t = a[i]; a[i] = a[j]; a[j] = t; }

    private static void show(Comparable[] a)
    {
        for (int i = 0; i < a.length; i++)
            StdOut.print(a[i] + " ");
        StdOut.println();
    }

    public static boolean isSorted(Comparable[] a)
    {
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args)
    {
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Selection
{
    public static void sort(Comparable[] a)
    {   //将a[]按升序排列
        int N = a.length;
        for (int i = 0;i < N;i++)
        {
            int min = i;
            for (int j = i + 1;j < N;j++)
                if (less(a[j], a[min])) min = j;
            exch(a, i, min);
        }
    }
    //less(),exch(),isSorted()和main()方法见通用模板
}

对于长度为$N$的数组，选择排序需要大约$N^{2}/2$次比较和$N$次交换

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Insertion_1
{
    public static void sort(Comparable[] a)
    {   //将a[]按升序排列
        int N = a.length;
        for (int i = 1; i < N; i++)
        {   //将a[i]插入到a[i-1],a[i-2],a[i-3]...之中
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--)
                exch(a, j, j - 1);
        }
    }
    //less(),exch(),isSorted()和main()方法见通用模板
}

要大幅提高插入排序的速度并不难，只需要在内循环中将较大的元素都向右移动而不总是交换两个元素（这样访问数组的次数就能减半）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Insertion_2
{
    public static void sort(Comparable[] a)
    {	//将a[]按升序排列
        int N = a.length;
        for (int i = 1; i < N; i++)
        {
            Comparable temp = a[i];
            int j = i - 1;
            for (; j >= 0 && less(temp, a[j]); j--)
                a[j + 1] = a[j];
            a[j + 1] = temp;
        }
    }
    //less(),exch(),isSorted()和main()方法见通用模板
}

总的来说，插入排序对于部分有序的数组十分高效，也适合小规模数组

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Shell_1
{
    public static void sort(Comparable[] a)
    {	//将a[]按升序排列
        int N = a.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1;// 1, 4, 13, 40, 121. ...
        while (h >= 1)
        {	//将数组变为h有序
            for (int i = h; i < N; i++)
            {	//将a[i]插入a[i - h],a[i - 2 * h],a[i - 3 * h]...之中
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
                    exch(a, j, j - h);
            }
            h /= 3;
        }
    }
    //less(),exch(),isSorted()和main()方法见通用模板
}

仿照Insertion_2，稍作改良

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Shell_2
{
    public static void sort(Comparable[] a)
    {	//将a[]按升序排列
        int N = a.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1;// 1, 4, 13, 40, 121. ...
        while (h >= 1)
        {
            for (int i = h; i < N; i++)
            {
                Comparable temp = a[i];
                int j = i - h;
                for (; j >= 0 && less(temp, a[j]); j -= h)
                    a[j + h] = a[j];
                a[j + h] = temp;
            }
            h /= 3;
        }
    //less(),exch(),isSorted()和main()方法见通用模板
}

归并排序

自顶向下

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
public class Merge
{
    private static Comparable[] aux;	//归并所需的辅助数组

    public static void sort(Comparable[] a)
    {
        aux = new Comparable[a.length];	//一次性分配空间
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi)
    {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    public static void merge(Comparable[] a, int lo, int mid, int hi)
    {
        int i = lo, j = mid + 1;

        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];

        for (int k = lo; k <= hi; k++)
        {
            if      (i > mid)               a[k] = aux[j++];
            else if (j > hi )               a[k] = aux[i++];
            else if (less(aux[j], aux[i]))  a[k] = aux[j++];
            else                            a[k] = aux[i++];
        }
    }
    //less(),exch(),isSorted()和main()方法见通用模板
}

用不同的方法处理小规模问题能改进大多数递归算法的性能，因为递归会使小规模问题的方法调用过于频繁，所以改进对它们的处理方法就能改进整个算法。对排序来说，我们已经知道插入排序（或者选择排序）非常简单，因此很可能在小数组上比归并排序更快。使用插入排序处理小规模的子数组（比如长度小于15）一般可以将归并排序的运行时间缩短10%~15%

自底向上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class MergeBU
{
    private static Comparable[] aux;
	//merge()方法见自顶向下版归并排序
    public static void sort(Comparable[] a)
    {	//进行lgN次两两归并
        int N = a.length;
        aux = new Comparable[N];
        for (int sz = 1; sz < N; sz *= 2)			//sz子数组大小
            for (int lo = 0; lo < N - sz; lo += 2 * sz)		//lo:子数组索引
                merge(a, lo, lo + sz - 1, Math.min(lo + 2 * sz - 1, N - 1));
    }
    //less(),exch(),isSorted()和main()方法见通用模板
}

归并排序是一种渐进最优的基于比较排序的算法

更准确地说，这句话的意思是，归并排序在最坏情况下的比较次数和任意基于比较的排序算法所需要的最少次数都是~$NlgN$

快速排序

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
public class Quick
{
    public static void sort(Comparable[] a)
    {
        StdRandom.shuffle(a);		//消除对输入的依赖
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi)
    {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);//切分
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private static int partition(Comparable[] a, int lo, int hi)
    {	//将数组切分为a[lo...i-1],a[i],a[i+1...hi]
        int i = lo, j = hi + 1;
        Comparable v = a[lo];	//切分元素
        while (true)
        {
            while (less(a[++i], v)) if (i == hi) break;
            while (less(v, a[--j])) if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
	//less(),exch(),isSorted()和main()方法见通用模板
}

将长度为$N$的无重复数组排序，快速排序平均需要~$2NlnN$次比较（以及$1/6$的交换）

算法改进

A.切换到插入排序

在排序小数组时切换到插入排序，如将$sort()$中的语句

1
if (hi <= lo) return;

替换为

1
if (hi <= lo + M) { Insertion.sort(a, lo, hi); return; }

转换参数M的最佳值是和系统相关的，但是5~15之间任意值在大多数情况下都能令人满意

B.三取样切分

改进快速排序性能的第二个办法是使用子数组的一小部分元素的中位数来切分数组。这样做得到的切分更好，但代价是需要计算中位数。人们发现将取样大小设置为3并用大小居中的元素切分的效果最好

C.熵最优的排序

实际应用中经常会出现含有大量重复元素的数组。我们实现的快速排序的性能尚可，但还有巨大的改进空间。一个简单的想法是将数组切分为三部分，分别对应小于、等于和大于切分元素的数组元素。

三向切分的快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Quick3way
{
    private static void sort(Comparable[] a, int lo, int hi)
    {	//调用此方法的公有sort()函数见上
        if (hi <= lo) return;
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];
        while (i <= gt)
        {
            int cmp = a[i].compareTo(v);
            if	(cmp < 0) exch(a, lt++, i++);
            else if (cmp > 0) exch(a, i, gt--);
            else i++;
        }//现在 a[lo...lt - 1] < v = a[lt..gt] < a[gt + 1..hi]成立
        
        sort(a, lo, lt - 1);
    	sort(a, gt + 1, hi);
    }
}

这段排序代码的切分能够将和切分元素相等的元素归为，这样它们就不会被包含在递归调用处理的子数组之中了。对于存在大量重复元素的数组，这种方法比标准的快速排序的效率高很多

快排应用实例：找出一组数中的第k小元素

1
2
3
4
5
6
7
8
9
10
11
12
13
public static Comparable select(Comparable[] a, int k)
{
    StdRandom.shuffle(a);
    int lo = 0, hi = a.length - 1;
    while (hi > lo)
    {
        int j = partition(a, lo, hi);
        if (j == k) break;
        else if (j > k) hi = j - 1;
        else if (j < k) lo = j + 1;
    }
    return a[k];
}

堆排序

由$N$个给定的元素构造一个堆有多难？我们当然可以在与$NlgN$成正比的时间内完成这项任务，只需从左至右遍历数组，用swim()保证扫描指针左侧的所有元素已经是一棵堆有序的完全树即可，就像连续向优先队列中插入元素一样。一个更聪明更高效的办法是从右至左用sink()函数构造子堆。数组的每个位置都已经是一个子堆的根节点了，sink()对于这些子堆也适用

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
50
51
52
53
54
55
56
public class Heap
{
    private Heap() { }

    public static void sort(Comparable[] pq)
    {
        int n = pq.length;

        for (int k = n / 2; k >= 1; k--)
            sink(pq, k, n);

        int k = n;
        while (k > 1) {
            exch(pq, 1, k--);
            sink(pq, 1, k);
        }
    }

    private static void sink(Comparable[] pq, int k, int n)
    {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && less(pq, j, j + 1)) j++;
            if (!less(pq, k, j)) break;
            exch(pq, k, j);
            k = j;
        }
    }

    private static boolean less(Comparable[] pq, int i, int j) 
    {
        return pq[i - 1].compareTo(pq[j - 1]) < 0;
    }

    private static void exch(Object[] pq, int i, int j) 
    {
        Object swap = pq[i - 1];
        pq[i - 1] = pq[j - 1];
        pq[j - 1] = swap;
    }

    private static void show(Comparable[] a) 
    {
        for (int i = 0; i < a.length; i++) 
        {
            StdOut.println(a[i]);
        }
    }

    public static void main(String[] args) 
    {
        String[] a = StdIn.readAllStrings();
        Heap.sort(a);
        show(a);
    }
}

堆排序应用见数据结构-优先队列