簡單排序（Java實現(xiàn)）蒋譬。
冒泡排序
原理
- 比較相鄰元素享钞，如果前者比后者大揍诽，交換
- 對所有相鄰元素重復(fù)
- 對除了最后一個的所有元素重復(fù)2
復(fù)雜度
最好情況：O(n)
平均時間復(fù)雜度：O(n^2)
代碼
public static void bubbleSort(int[] a){
for(int outer = a.length - 1; outer > 1; outer--)
for(int inner = 0; inner < outer ;inner++)
if(a[inner] > a[inner + 1])
swap(a, inner, inner+1);
}
選擇排序
原理
每次選出最小的元素放到開始位置。
復(fù)雜度
時間復(fù)雜度 O(n^2)
但是交換次數(shù)比冒泡排序少
代碼
public static void selectSort(int[] a){
int min;
for(int i = 0; i < a.length - 1; i++){
min = i;
for(int j = i + 1; j < a.length; j++)
if(a[j] < a[min]) min = j;
swap(a, i, min);
}
}
插入排序
原理
在局部有序的數(shù)字中插入被標(biāo)記的值嫩与。
復(fù)雜度
時間復(fù)雜度為O(n^2)
但是一般情況下比冒泡排序快一倍寝姿，比選擇排序也快一點(diǎn)。
代碼
public static void insertSort(int[] a){
for(int i = 1; i < a.length; i++){
int j = i, temp = a[i];
while(j > 0 && a[j - 1] >= temp){
a[j] = a[j - 1];j--;
}
a[j] = temp;
}
}
三種排序的比較
選擇排序降低了交換次數(shù)划滋，但是比較次數(shù)仍然很多饵筑，當(dāng)數(shù)據(jù)量比較少，或者基本上有序的時候处坪，使用選擇排序根资。
對于其他情況架专，應(yīng)該選擇插入排序。
