数据结构与算法学习二：直接选择排序

一.排序方法

被排列的数组data[0...n]，选定当前位置i=0作为最小值下标position；在data[i+1...n]区间每个元素与data[position]比较，记录新position，最后交换data[i]和data[position]。这样最小的元素就到了当前位置了。当前位置i+1，重复1...

?

二.动画演示?

????? http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/zhijiexuanze.htm

?

三.Java代码

?????

public static int[] selectSort(int[] data) {int temp = 0;int position = 0;int j = 0;for (int i = 0; i < data.length - 1; i++) {//i当前位置position = i;//position最小下标j = i + 1;for (; j < data.length; j++) {//j从此区间选取最小下标if (data[j] < data[position]) {position = j;}}if (position != i) {temp = data[i];data[i] = data[position];data[position] = temp;}}return data;}

?

?

?四.时间复杂度和稳定性

?最好时间复杂度
若文件的初始状态是正序的，所需的关键字比较次数C和记录移动次数M。Cmin=n(n-1)/2=0(n2)Mmin=0直接选择排序最好的时间复杂度为O(n2)
最坏时间复杂度
若初始文件是反序的，所需的关键字比较次数C和记录移动次数M。Cmax=n(n-1)/2=O(n2)Mmax=3(n-1)=O(n)直接选择排序的最坏时间复杂度为O(n2)
平均时间复杂度
O(n2)
直接选择排序是就地排序，它是不稳定的。反例[2，2，1] 。