简介
排序:将数组中的元素按指定的大小顺序排列好
排序算法类模板:
- 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
74import 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
68import 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 | import edu.princeton.cs.algs4.StdOut; |
对 1000 组长度为 1000 的数组进行排序测试
Selection用时:1.48
Insertion用时:1.22
Insertion 比 Selection 快 1.2倍
希尔排序
一个h有序数组就是h个互相独立的有序数组编织在一起的数组
按照增量序列依次将数组以增量h进行普通插入排序,直到h=1完成排序
代码
1 | import edu.princeton.cs.algs4.StdOut; |
分析
希尔排序的关键在于增量序列的选取,暂无法准确描述其对于乱序的数组的性能特征。
希尔排序对于插入排序,数组越大优势越大:
对 1000 组长度为 1000 的数组进行排序测试
Shell用时:0.20
Insertion用时:1.36
Shell 比 Insertion 快 6.7倍
归并排序
简介
递归地将数组分成两半分别排序,然后将结果归并(即将两个有序数组合并成一个有序数组)起来。
代码
1 | /** |
分析
对于长度为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 | import edu.princeton.cs.algs4.StdRandom; |
分析
将长度为N的无重复数组排序,快排平均需要~2NlnN次比较(约等于1.39NlgN)
快排最多需要约N^2/2次比较,但随机打乱数组能预防这种情况。
对 10000 组长度为 10000 的数组进行排序测试
Merge用时:16.66
Quick用时:11.89
Quick 比 Merge 快 1.4倍
三向切分的快速排序
对于有大量重复数据的大型数组,在快速排序的基础上,将数组分为大于、等于、小于v的三部分
递归时仅对大于、小于v的数组进行排序,即可在此特定条件下获得更优的表现。
代码
1 | import edu.princeton.cs.algs4.StdRandom; |