选择排序分析：1.第i趟确定数组下标为i的对应的第i小（大）数，n个数比较n-1趟 2.第i趟需要与array.length-i个数逐一比较，从下标[i+1]比起，直到[array.length-1]
假设数组array有array.length个元素
第一趟：确定数组第一个下标位置存最小（大）值，用第一个下表的元素逐一与右边的下标元素比较，值大就交换，值小就不变，接着与右边的右边元素比较，直到和最后的下标位置元素比较完毕，这样下来，数组第一个下标位置存的就是最小（大）值了，需要比较array.length-1次
......
第i趟：确定数组的第i个下标位置存第i小（大）值，此时只剩下下标为i+1到array.length-1的元素与之逐一比较，需要比较array.length-(i-1)-1，即array.length-i次
......
最后一趟：确定数组倒数第二个下标位置存第倒数第二小的数，此时只剩下最后一个下标元素与之比较，需要比较一次
结论：array.length个元素需要走array.length-1趟，第i趟需要比较array.length-i次
假设问题规模为n，即n个元素的排序问题。
第1趟：需要比较n-1次
第2趟：需要比较n-2次
...
第n-1趟：需要比较1次
总计：(n-1)+(n-2)+...+1=(n-1)(n-1+1)/2,时间复杂度为O(n^2),只需要一个额外空间O(1)。
我个人代码示例：
public class SelectionSort {
public static void selectionSort(int[] array) {
for(int i=0;i<array.length-1;i++)
for(int j=i+1;j<array.length;j++)
if(array[i]>array[j]) {
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
public static void main(String[] args) {
int[] array= {6,5,3,2,4,8,9,1};// TODO Auto-generated method stub
System.out.println("排序前：");
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
System.out.println();
selectionSort(array);
System.out.println("排序后:");
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
}
}
代码输出结果：
排序前：
6 5 3 2 4 8 9 1
排序后:
1 2 3 4 5 6 8 9
网友评论