选择排序 n + n-1 + n-2 + … + 2 + 1 = n * (n+1) / 2 = 0.5 * n ^ 2 + 0.5 * n,那么时间复杂度是O(N^2),这是雷打不动的时间复杂度
每一趟进行选择出最大值或最小值,然后进行交换首末位置,每趟减少一个
时间复杂度无论什么时候都是o(n^2),因为它是数据规模为n,然后每趟选出最大值或最小值,进行n趟;
空间算法度则为O(1) 因为只用了两中间变量
package sort;
/**
* @author wyc
* 选择排序
*/
public class SelectionSort {
public static void main(String[] args) {
int[] arrays = {1,11,12,4,2,6,9,0,3,7,8,2};
selectionSorting(arrays);
for(int value : arrays){
System.out.println(value);
}
}
private static void selectionSorting(int[] a){
int max,index;
for(int len = 0;len < a.length-1;len++){
max = a[len];
index = len;
for(int i = len;i < a.length;i++){
if(a[i] > max){
max = a[i];
index = i;
}
}
if(len != index){
a[len] = a[len] + a[index];
a[index] = a[len] - a[index];
a[len] = a[len] - a[index];
}
}
}
}