冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。每次遍历一次都使一个元素归位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Bubble {
public static void sort(Comparable[] a){
int N = a.length;
for(int i=0; i<N-1; ++i){
for(int j=1; j<N-i; j++){
if(a[j].compareTo(a[j-1]) < 0){
Comparable temp = a[j];
a[j] = a[j-1];
a[j-1] =temp;
}
}
}
}
}
|
选择排序(Selection Sort)
选择排序是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小元素，存放到排序序列的前部分，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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 (a[min].compareTo(a[j]) > 0) min = j;
}
Comparable temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
}
|
插入排序（Insertion Sort）
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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 && a[j].compareTo(a[j-1])<0 ;j--){
Comparable temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
}
|
希尔排序（Shell Sort）
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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 && a[j].compareTo(a[j-h])<0; j-=h){
Comparable temp = a[j];
a[j] = a[j-h];
a[j-h] = temp;
}
}
h = h/3;
}
}
}
|
归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为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
| 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){
for(int k=lo; k<=hi; ++k)
aux[k] = a[k];
int i = lo, j = mid+1;
for(int k=lo; k<=hi; ++k){
if(i > mid) a[k] = aux[j++];
else if(j > hi) a[k] = aux[i++];
else if(aux[i].compareTo(aux[j]) < 0) a[k] = aux[i++];
else a[k] = aux[j++];
}
}
}
|
快速排序（Quick Sort）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
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
| public class Quick {
public static void sort(Comparable[] 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);
}
public static int partition(Comparable[]a, int lo, int hi){
int i=lo,j=hi;
Comparable v = a[lo];
while(i != j){
while(j > i && a[j].compareTo(v) >= 0){
j--;
};
while(i < j && a[i].compareTo(v) <= 0){
i++;
};
if(i<j){
Comparable temp = a[i];
a[i] = a[j];
a[j] =temp;
}
}
Comparable temp = a[lo];
a[lo] = a[j];
a[j] =temp;
return j;
}
}
|
堆排序（Heap Sort）
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-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
| public class Heap {
public static void sort(Comparable[] a){
for(int i=a.length/2-1; i>=0; i--){
adjustDown(a,i,a.length);
}
for(int j=a.length-1; j>0; j--){
Comparable temp = a[0];
a[0] = a[j];
a[j] = temp;
adjustDown(a,0,j);
}
}
private static void adjustDown(Comparable[] a,int i,int length){
Comparable temp = a[i];
for(int k=2*i+1; k<length; k=k*2+1){
if(k+1<length && a[k].compareTo(a[k+1])<0){
k++;
}
if(a[k].compareTo(temp) > 0){
a[i] = a[k];
i = k;
}else{
break;
}
}
a[i] = temp;
}
}
|
参考：https://www.cnblogs.com/onepixel/articles/7674659.html