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

一.排序方法

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

 

 

 四.时间复杂度和稳定性

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