简单排序(Java实现)。
最好情况:O(n) 平均时间复杂度: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);
}
每次选出最小的元素放到开始位置。
时间复杂度 O(n^2) 但是交换次数比冒泡排序少
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);
}
}
在局部有序的数字中插入被标记的值。
时间复杂度为O(n^2) 但是一般情况下比冒泡排序快一倍,比选择排序也快一点。
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;
}
}
选择排序降低了交换次数,但是比较次数仍然很多,当数据量比较少,或者基本上有序的时候,使用选择排序。 对于其他情况,应该选择插入排序。