选择排序示范-从小到大 关键操作“从左至右逐一比较”

选择排序分析：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