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
40public 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);
}
}
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);
}
}
时间复杂度：平均情况O(n2)，最坏O(n2)，最好O(n2)。选择排序每次需要大约n2/2次比较和n次交换。
空间复杂度：O(1)
稳定性：不稳定。比如数组5 4 5 2 1，第一次排序时就要将第一个5和1交换，造成两个5的先后顺序发生改变，故为不稳定排序。
2、插入排序
思想：
将每一个数据插入到其他已经有序的数组中。
图示(深色代表移动的元素，浅色代表不移动的元素)：
代码：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
38public 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);
}
}
}
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);
}
}
时间复杂度：平均情况O(n2)，最坏O(n2)逆序，最好O(n)有序。
空间复杂度：O(1)
稳定性：稳定
3、希尔排序(Shell)
思想：
一种插入排序算法，目的是使数组中任意间隔为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
44public 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++){
//j>=h用于控制不要超过h的范围
for(int j=i;j>=h&&less(a[j],a[j-h]);j-=h)
exch(a,j,j-h);
}
h=h/3;
}
}
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);
}
}
时间复杂度：平均情况O(n1.3)，最坏O(n2)，最好O(n)
空间复杂度：O(1)
稳定性：不稳定。因为在对每隔h的数据进行排序的过程中可能会将相同大小的数据位置进行交换。
这其中的StdOut以及StdIn库使用自algs4这个jar包，下载地址：
https://algs4.cs.princeton.edu/code/algs4.jar