1.選擇排序
一種最簡單的排序算法是這樣的：首先谎倔，找到數(shù)組中的最小的元素柳击，其次，將他和第一個元素交換位置片习。再次捌肴，在剩下的元素中找到最小的元素蹬叭，將他換到第二個元素的位置。如此往復(fù)状知，這種方法就是選擇排序秽五，一直不斷不斷地選擇剩余元素中的最小者。選擇排序的時間復(fù)雜度為n2饥悴。
實現(xià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.插入排序
將一個數(shù)字插入一個已經(jīng)有序的數(shù)組中坦喘，并且依然保持有序，這就是插入排序西设。插入排序的時間復(fù)雜度在最壞的情況下瓣铣，時間時間復(fù)雜度為n2，最好的情況下的時間復(fù)雜度則為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;
}
}
}
希爾排序
希爾排序是基于插入排序的一種排序算法棠笑。對于大規(guī)模的亂序數(shù)組插入排序會很慢，因為它只會交換相鄰的元素禽绪，因此元素只能一點點的從一端移動到另一端蓖救。希爾排序為了加速簡單地改進了插入排序。
希爾排序的思想是使數(shù)組中的任意間隔為h的元素都是有序的印屁。對于沒一段間隔h循捺，用插入排序的將h個子數(shù)組獨立。每次每個元素的移動有插入排序的1變?yōu)閔库车。希爾排序的高效在于它權(quán)衡了子數(shù)組規(guī)模和有序性巨柒。
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;
}
}
歸并排序
歸并排序是基于歸并這個操作，即將兩個有序的數(shù)組歸并成一個更大的有序數(shù)組柠衍。歸并排序的時間復(fù)雜度為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){
//將數(shù)組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++];
}
}
}
}
快速排序
快速是基于分治的排序算法。它將一個數(shù)組分成兩個數(shù)組珍坊，將兩部分獨立的排序牺勾。快速排序和歸并排序是互補的：歸并排序?qū)?shù)組分成兩個子數(shù)組分別排序阵漏，并將有序的子數(shù)組歸并以將整個數(shù)組排序驻民；而快速排序是當成兩個子數(shù)組都有序時整個數(shù)組也就自然有序了。歸并排序遞歸調(diào)用發(fā)生在處理整個數(shù)組之前履怯，一個數(shù)組被等分為兩半回还；快速排序遞歸發(fā)生在處理整個數(shù)組之后，切分的位置取決于數(shù)組的內(nè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);
}
}
}
