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