sort

发表于 | 分类于
排序算法学习与总结
简介

排序：将数组中的元素按指定的大小顺序排列好
排序算法类模板：

  • void sort(Comparable[] a) //排序算法
  • boolean less(Comparable v,Comparable w) //比较两个元素大小
  • void exch(Comparable[] a,int i,int j) //交换两个元素位置
  • void show(Comparable[] a) //打印数组
  • boolean isSorted(Comparable[] a) //判断数组是否已排序完成
    选择排序
    简介
    数组a[],长度为N；
    从左i=0处往右依次进行：选择i到N里最小的数放在i处
    代码
    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
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    import edu.princeton.cs.algs4.In;
    import edu.princeton.cs.algs4.StdOut;

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;

    /**
     * 选择排序
     * 从左往右依次进行
     * 选择i到a.length里最小的数放在i处
     */
    public class Selection
    {
        public static void sort(Comparable[] 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);
            }
        }

        public static void main(String[] args) throws IOException
        {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String inputStr = br.readLine();
            String[] a = inputStr.split(" ");
            sort(a);
            assert isSorted(a);
            show(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 = 0; i < a.length; i++)
            {
                if (less(a[i], a[i - 1]))
                {
                    return false;
                }
            }
            return true;
        }
    }
分析

对于长度为N的数组，从0到N-1的任意i都会进行一次交换和N-1-i次比较
所以总共有N次交换及(N+1)+(N+2)+…+2+1=N(N-1)/2~N^2/2次比较。
特点：交换操作少，比较次数过多。

插入排序
简介

从左往右依次进行
将i与i到0的数据依次比较，直到将i移动到适当位置。

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
57
58
59
60
61
62
63
64
65
66
67
68
import edu.princeton.cs.algs4.StdOut;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 插入排序
 * 从左往右依次进行
 * 将i与i到0的数据依次比较，直到将i移动到适当位置。
 */
public class Insertion
{
    public static void sort(Comparable[] a) //排序算法
    {
        int N = a.length;
        for (int i = 1; i < N; i++)
        {
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j++)
            {
                exch(a, j, j - 1);
            }
        }
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();
        String[] a = inputStr.split(" ");
        sort(a);
        assert isSorted(a);
        show(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 = 0; i < a.length; i++)
        {
            if (less(a[i], a[i - 1]))
            {
                return false;
            }
        }
        return true;
    }
}

分析

对于长度为N且主键不重复的数组，最坏情况下需要~N^2/2次比较和~N^2/2次交换
最好情况下需要N-1次比较，0次交换。
对部分有序数组十分高效。

实验比较

T次，每次用长度为N的随机数组，测试两种排序方法的效率。

代码
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
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.Stopwatch;

public class SortCompare
{
    public static double time(String alg,Double[] a)
    {//为排序算法计时
        Stopwatch timer = new Stopwatch();
        if(alg.equals("Insertion")) Insertion.sort(a);
        if(alg.equals("Selection")) Selection.sort(a);
        return timer.elapsedTime();
    }
    public static double timeRandomInput(String alg,int N,int T)
    {
        double total = 0.0;
        Double[] a = new Double[N];
        for(int t=0;t<T;t++)
        {
            for (int i = 0; i < N; i++)
            {
                a[i] = StdRandom.uniform();
            }
            total += time(alg,a);
        }
        return total;
    }

    public static void main(String[] args)
    {
        String alg1 = "Insertion";  
        String alg2 = "Selection";
        int N = 100;
        int T = 1000;
        double t1 = timeRandomInput(alg1,N,T);
        double t2 = timeRandomInput(alg2,N,T);
        StdOut.printf("%f,%f\n",t1,t2);
        StdOut.printf("%d 次，每次%d长度数组",T,N);
        StdOut.printf("插入排序比选择排序快%.1f倍",t2/t1);
    }
}

对 1000 组长度为 1000 的数组进行排序测试
Selection用时：1.48
Insertion用时：1.22
Insertion 比 Selection 快 1.2倍

希尔排序

一个h有序数组就是h个互相独立的有序数组编织在一起的数组
按照增量序列依次将数组以增量h进行普通插入排序，直到h=1完成排序

代码
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import edu.princeton.cs.algs4.StdOut;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 希尔排序
 * 一个h有序数组就是h个互相独立的有序数组编织在一起的数组
 * 按照增量序列依次将数组以增量h进行普通插入排序，直到h=1完成排序
 */
public class Shell
{
    public static void sort(Comparable[] a) //排序算法
    {
        int N = a.length;
        int h = 1;
        while (h < N / 3)
        {
            h = 3 * h + 1;
        }
        while (h >= 1)
        {
            for (int i = h; i < N; i++)
            {
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
                {
                    exch(a, j, j - h);
                }
            }
            h /= 3;
        }
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();
        String[] a = inputStr.split(" ");
        Integer[] aa = new Integer[a.length];
        int i = 0;
        for (String str:a)
        {
            aa[i++] = Integer.parseInt(str);
        }
        sort(aa);
        assert isSorted(aa);
        show(aa);
    }

    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 = 0; i < a.length; i++)
        {
            if (less(a[i], a[i - 1]))
            {
                return false;
            }
        }
        return true;
    }
}
分析

希尔排序的关键在于增量序列的选取，暂无法准确描述其对于乱序的数组的性能特征。
希尔排序对于插入排序，数组越大优势越大：

对 1000 组长度为 1000 的数组进行排序测试
Shell用时：0.20
Insertion用时：1.36
Shell 比 Insertion 快 6.7倍

归并排序
简介

递归地将数组分成两半分别排序，然后将结果归并（即将两个有序数组合并成一个有序数组）起来。

代码
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * Description: 归并排序
 * Author: Hodge
 * Date: 2018-03-25
 */
public class Merge
{
    //将以mid分隔的两个有序数组合并成一个有序数组
    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++];
            }
        }
    }

    private static Comparable[] aux;

    public static void sort(Comparable[] a)
    {
        aux = new Comparable[a.length];
        sortTopDown(a, 0, a.length - 1);
    }

    //自顶向下的归并排序
    public static void sortTopDown(Comparable[] a, int lo, int hi)
    {
        if (lo >= hi)
        {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sortTopDown(a, lo, mid);
        sortTopDown(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }
    
    //自底向上的归并排序
    public static void sortDownTop(Comparable[] a)
    {
        int N = a.length;
        aux = new Comparable[N];
        for (int sz = 1; sz < N; sz = sz + sz)
        {
            for (int lo = 0; lo < N - sz; lo += sz + sz)
            {
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }
        }
    }

    private static boolean less(Comparable v, Comparable w) //比较两个元素大小
    {
        return v.compareTo(w) < 0;
    }
}
分析

对于长度为N的任意数组，归并排序需要0.5NlgN至NlgN次比较，最多需要访问数组6N*lgN次。

对 1000 组长度为 10000 的数组进行排序测试
Shell用时：2.22
Merge用时：1.76
Merge 比 Shell 快 1.3倍

对 1000 组长度为 10000 的数组进行排序测试
Shell用时：2.33
MergeDownTop用时：1.76
MergeDownTop 比 Shell 快 1.3倍

对 1000 组长度为 10000 的数组进行排序测试
Merge用时：1.83
MergeDownTop用时：1.63
MergeDownTop 比 Merge 快 1.1倍

对 10000 组长度为 10000 的数组进行排序测试
Merge用时：17.07
MergeDownTop用时：16.47
MergeDownTop 比 Merge 快 1.0倍

快速排序
经典快排

从第一个元素v起，同时从数组两端遍历，将大于和小于v的元素互换位置。
然后将v分割出来的两个子数组分别递归做上述操作。

代码
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
57
58
59
60
61
62
63
64
65
66
67
68
import edu.princeton.cs.algs4.StdRandom;

/**
 * Description: 快速排序
 * Author: Hodge
 * Date: 2018-03-26
 */
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 (lo >= hi)
        {
            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;
    }

    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;
    }
}
分析

将长度为N的无重复数组排序，快排平均需要~2NlnN次比较（约等于1.39NlgN）
快排最多需要约N^2/2次比较，但随机打乱数组能预防这种情况。

对 10000 组长度为 10000 的数组进行排序测试
Merge用时：16.66
Quick用时：11.89
Quick 比 Merge 快 1.4倍

三向切分的快速排序

对于有大量重复数据的大型数组，在快速排序的基础上，将数组分为大于、等于、小于v的三部分
递归时仅对大于、小于v的数组进行排序，即可在此特定条件下获得更优的表现。

代码
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
import edu.princeton.cs.algs4.StdRandom;

/**
 * Description: 三向切分的快速排序
 * Author: Hodge
 * Date: 2018-03-26
 */
public class Quick3way
{
    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 (lo >= hi)
        {
            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++;
        }
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }

    private static void exch(Comparable[] a, int i, int j) //交换两个元素位置
    {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}