1.选择排序
一种最简单的排序算法是这样的：首先，找到数组中的最小的元素，其次，将他和第一个元素交换位置。再次，在剩下的元素中找到最小的元素，将他换到第二个元素的位置。如此往复，这种方法就是选择排序，一直不断不断地选择剩余元素中的最小者。选择排序的时间复杂度为n²。
实现：
public static void sort(Comparable[] a){
int n = a.length;
for(int i = 0; i < n; i++){
//将a[i]和a[+1]中最小的元素进行交换
int min = i;
for(int j = i + 1; j < n; j++){
if(a[j].compareTo(a[min]) > 0){
min = j;
}
Comparable t = a[i];
a[i] = a[min];
a[min] = t;
}
}
}
2.插入排序
将一个数字插入一个已经有序的数组中，并且依然保持有序，这就是插入排序。插入排序的时间复杂度在最坏的情况下，时间时间复杂度为n²，最好的情况下的时间复杂度则为n。
public static void sort(Comparable[] a){
int n = a.length;
for(int i = 0; i < n; i++){
for(int j = i; j > 0 && a[j].compareTo(a[j - 1]) > 0; j--){
Comparable t = a[j];
a[j] = a[j - 1];
a[j - 1] = t;
}
}
}
希尔排序
希尔排序是基于插入排序的一种排序算法。对于大规模的乱序数组插入排序会很慢，因为它只会交换相邻的元素，因此元素只能一点点的从一端移动到另一端。希尔排序为了加速简单地改进了插入排序。
希尔排序的思想是使数组中的任意间隔为h的元素都是有序的。对于没一段间隔h，用插入排序的将h个子数组独立。每次每个元素的移动有插入排序的1变为h。希尔排序的高效在于它权衡了子数组规模和有序性。
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 t = a[j];
a[j] = a[j - h];
a[j - h] = t;
}
}
h = h / 3;
}
}
归并排序
归并排序是基于归并这个操作，即将两个有序的数组归并成一个更大的有序数组。归并排序的时间复杂度为NlgN。
public class MergeSort {
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 start, int end){
//将数组a[start..end]排序
if(end <= start)
return;
int mid = start + (end - start) / 2;
sort(a, start, mid);
sort(a, mid + 1, end);
merge(a, start, mid, end);
}
public static void merge(Comparable[] a, int start, int mid, int end){
//归并
int i = start;
int j = mid + 1;
//保存副本
for(int k = start; k <= end; k++)
aux[k] = a[k];
for(int k = start; k <= end; k++){
if(i > mid){
a[k] = aux[j++];
} else if(j > end){
a[k] = aux[i++];
} else if(aux[j].compareTo(aux[i]) > 0){
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
}
快速排序
快速是基于分治的排序算法。它将一个数组分成两个数组，将两部分独立的排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序是当成两个子数组都有序时整个数组也就自然有序了。归并排序递归调用发生在处理整个数组之前，一个数组被等分为两半；快速排序递归发生在处理整个数组之后，切分的位置取决于数组的内容。
public class QuickSort {
public static void sort(Comparable[] a){
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int start, int end){
if(end <= start)
return;
int j = partition(a, start, end);
sort(a, start, j - 1);
sort(a, j + 1, end);
}
private static int partition(Comparable[] a, int start, int end){
int i = start;
int j = end + 1;
Comparable v = a[start];
while (true){
while (a[++i].compareTo(v) > 0)
if(i == end)
break;
while (v.compareTo(a[--j]) > 0)
if(j == start)
break;
if(i >= j)
break;
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
Comparable t = a[start];
a[start] = a[j];
a[j] = t;
return j;
}
public static void main(String[] args) {
Integer[] a = new Integer[]{4,9,2,8};
sort(a);
for(Integer b : a){
System.out.println(b);
}
}
}
