前言
- 假定待排序的元素是引用类型，为了便于比较，以及比较逻辑和排序代码的混杂，待排序的元素需要实现java的Comparable接口，该接口有compareTo方法，用其来判断两个元素的大小关系。
- less()和swap() 负责比较和交换，这样做是把这两个关键步骤抽离，方便维护，易读
- 排序算法的成本是比较和交换的次数
1
2
3
4
5
6
7
8
9
10
11
12
13
| public abstract class Sort <T extends Comparable<T>>{
public abstract void sort(T[] nums);
protected boolean less(T v, T w){
return v.compareTo(w) < 0;
}
protected void swap(T[] a, int i, int j){
T t = a[i];
a[i] = a[j];
a[j] = t;
}
}
|
冒泡排序
循环每次确定一个当前最大值，放到本次循环的最后，直到整体有序；优化过后的冒泡排序可以在过程中确定是否已经有序，从而提前终止循环，缺点是需要不断地交换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Bubble<T extends Comparable<T>> extends Sort<T>{
@Override
public void sort(T[] nums) {
int N = nums.length;
boolean isSorted = false;
for(int i = N-1; i>0 && !isSorted ; i--){
isSorted = true;
for(int j = 0; j < i; j++){
if(less(nums[j+1],nums[j])){
isSorted = false;
swap(nums, j, j+1);
}
}
}
}
}
|
选择排序
数组的每一个位置都是一个擂台，打擂台的选手是当前擂台上的元素以及以后的元素，擂台的级别从左到右逐次降低，按顺序从左到右每一轮打擂台选出一个擂台上的胜者，从而选出第一小，第二小…的元素，实现排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public class Selection<T extends Comparable<T>> extends Sort<T> {
@Override
public void sort(T[] nums) {
int N = nums.length;
for(int i=0;i<N-1;i++){
int min = i;
for(int j = i + 1; j < N; j++){
if(less(nums[j],nums[min])){
min = j;
}
}
swap(nums, i, min);
}
}
}
|
选择和冒泡的优缺点
两者十分类似：
- 冒泡需要频繁交换，会造成排序的成本增大
- 冒泡因为一直进行相邻元素的比较，所以优化后可以提前预知序列的有序；选择排序不能
- 选择排序 直到确定了局部的最大值才会进行交换，交换时跨度大，可以降低排序的成本
插入排序
一个首元素一定是一个有序序列，然后后面第二个元素根据与第一个元素比较的结果插入第一个元素的前面或者后面形成序列，第三个元素选择性插入前面中间或者后面可以形成三个元素的有序序列，局部有序序列越来越大，最终有序。
不足之处：当数据量足够大时，假如当前第10000个元素选择插入位置，实际上判断后他需要插入到第100个元素的位置上，这时它就需要不断地与相邻元素交换，直到到达插入位置，这样的成本非常大。时间复杂度（O(N) ~ O(N*N), 根据初始序列而有不同）
1
2
3
4
5
6
7
8
9
10
11
| public class Insertion <T extends Comparable<T>> extends Sort<T> {
@Override
public void sort(T[] nums) {
int N = nums.length;
for(int i=1; i<N;i++){
for(int j = i; j > 0 && less(nums[j],nums[j-1]); j--){
swap(nums,j,j-1);
}
}
}
}
|
希尔排序
插入排序升级版，增加了交换的跨度。
假如跨度是30，总共100个元素
那么首先
- 0 30 60 90 插入排序使其有序
- 1 31 61 91 插入排序使其有序
- …
然后逐步缩小跨度，直到跨度为1，将成为基本的插入排序，但是此时基本不会出现 较长距离的移动了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public class Shell<T extends Comparable<T>> extends Sort<T> {
@Override
public void sort(T[] nums) {
int N = nums.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(nums[j],nums[j-h]);j-=h){
swap(nums, j,j-h);
}
}
h = h / 3;
}
}
}
|
归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public abstract class MergeSort<T extends Comparable<T>> extends Sort<T> {
protected T[] aux;
protected void merge(T[] nums,int l,int m,int h){
int i = l, j = m + 1;
for(int k = l; k <= h; k++){
aux[k] = nums[k];
}
for(int k = l; k <= h; k++){
if(i > m){
nums[k] = aux[j++];
}else if(j>h){
nums[k] = aux[i++];
}else if(aux[i].compareTo(aux[j]) <= 0){
nums[k] = aux[i++];
}else{
nums[k] = aux[j++];
}
}
}
}
|
自顶向下的归并排序
由于自顶向下的进行，刚拿到手上的是一个大问题，需要递归成一个个小规模的问题来解决。
一个序列，使之左边有序，右边有序，然后合并两个有序子序列就会容易很多
左边有序，问题还很大，使左边的左边有序，左边的右边有序，然后合并两个子序列
左边的左边。。。
直到子序列只有一个元素了，它一定有序了，合并相邻的子序列就好，
所以重要的部分是 合并的算法 递归的过程是分治的过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public class UpDownMergeSort<T extends Comparable<T>> extends MergeSort<T>{
@Override
public void sort(T[] nums) {
aux = (T[]) new Comparable[nums.length];
sort(nums,0,nums.length - 1);
}
private void sort(T[] nums,int l,int h){
if(h <= l){
return;
}
int mid = l + (h-l)/2;
sort(nums,l,mid);
sort(nums,mid+1,h);
merge(nums,l,mid,h);
}
}
|
自底向上的归并排序
其实按名字来讲这种只能称为合并排序，是因为弄清楚了递归的逻辑并且深刻理解了归并排序的实质后才写出来的，所以有些难写，而且边界也不太好控制。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public class DownToUpMergeSort <T extends Comparable<T>> extends MergeSort<T>{
@Override
public void sort(T[] nums) {
int N = nums.length;
aux = (T[]) new Comparable[N];
for(int sz = 1; sz < N; sz += sz){
for(int lo = 0; lo < N - sz; lo += sz + sz){
merge(nums, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
}
}
}
}
|
快速排序
一个序列中选择一个任意的元素，找准它的位置并且使得其左边全都是比它小的数据，右边全都是比它大的数据，
再递归地使用快速排序使得左边有序和右边有序即可
最坏的情况是递归的过程中数据一直处于一边的状态，这样不能很快地降低数据的规模，退化成选择排序O(N*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 java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class QuickSort <T extends Comparable<T>> extends Sort<T>{
@Override
public void sort(T[] nums) {
shuffle(nums);
sort(nums, 0, nums.length - 1);
}
protected void sort(T[] nums, int l,int h){
if(h <= l)
return;
int j = partition(nums,l,h);
sort(nums,l,j-1);
sort(nums, j+1, h);
}
private void shuffle(T[] nums){
List<Comparable> list = Arrays.asList(nums);
Collections.shuffle(list);
list.toArray(nums);
}
private int partition(T[] nums, int l, int h){
int i = l,j = h + 1;
T v = nums[l];
while(true){
while(less(nums[++i] , v) && i != h);
while(less(v, nums[--j]) && j != l);
if(i >= j)
break;
swap(nums,i,j);
}
swap(nums, l ,j);
return j;
}
}
|
基于切分的快速选择算法
由于切分函数每次确定一个元素的具体位置所以我们只要有意缩小范围，可以利用此函数来找到数组中第N小的数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public T select(T[] nums,int k){
int l = 0, h = nums.length - 1;
while(h > l){
int j = partition(nums, l, h);
if(j == k){
return nums[k];
}else if(j > k){
h = j - 1;
}else{
l = j + 1;
}
}
return nums[k];
}
|
j如果每次能将子序列一分为2，那么查找的次数是O(logN)级别的
三向切分
对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。
三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class ThreeWayQuickSort<T extends Comparable<T>> extends QuickSort<T> {
@Override
protected void sort(T[] nums, int l,int h){
if(h <= l){
return;
}
int lt = l,i = l + 1,gt = h;
T v = nums[l];
while(i <= gt){
int cmp = nums[i].compareTo(v);
if(cmp < 0){
swap(nums, lt++, i++);
}else if(cmp > 0){
swap(nums,i,gt--);
}else{
i ++;
}
}
sort(nums, l, lt - 1);
sort(nums, gt + 1, h);
}
}
|
java的排序算法的实现
Java 主要排序方法为 java.util.Arrays.sort()，对于原始数据类型使用三向切分的快速排序，对于引用类型使用归并排序。