选择排序

1.选择排序

　　首先在未排序序列找到最小( 大 )元素,存放到排序序列的起始位置.

　　再从剩余未排序元素中继续寻找最小 ( 大 ) 元素,然后放到已排序序列的末尾.

　　重复第二步,直到所有元素均排序完毕

2.举例说明

　　数组 int[] arr={5,2,8,4,9,1};

-------------------------------------------------------

第一趟排序： 原始数据：5  2  8  4  9  1

最小数据1，把1放在首位，也就是1和5互换位置，

排序结果：1  2  8  4  9  5

-------------------------------------------------------

第二趟排序：

第1以外的数据{2  8  4  9  5}进行比较，2最小，

排序结果：1  2  8  4  9  5

-------------------------------------------------------

第三趟排序：

除1、2以外的数据{8  4  9  5}进行比较，4最小，8和4交换

排序结果：1  2  4  8  9  5

-------------------------------------------------------

第四趟排序：

除第1、2、4以外的其他数据{8  9  5}进行比较，5最小，8和5交换

排序结果：1  2  4  5  9  8

-------------------------------------------------------

第五趟排序：

除第1、2、4、5以外的其他数据{9  8}进行比较，8最小，8和9交换

排序结果：1  2  4  5  8  9

3.代码展示

　　

//java代码展示
public class selectSort implements IArraySort{

    @Override
    public int[] sort(int[] sourceArray) {
        int[] arr = Arrays.copyOf(sourceArray,sourceArray.length);
        
        //总共要经过N-1轮比较
        for(int i = 0;i < arr.length - 1 ; i++){
            //假定第一个i的值为最小值
            int min = i;
            
            //每轮需要比较的次数N-i
            for(int j = i + 1 ; j < arr.length ; j++){
                //比较当前值与假定的最小值比较
                if(arr[j] < arr[min]){
                    //记录目前能找到的最小值元素的下标
                    min = j ;
                    
                }
            }
            //将找到的最小值和i位置所在的值进行交换
            if(i != min){
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
        
        return arr;
    }
    
    

}

　　注:每一趟排序获得最小数的方法：for循环进行比较，定义一个第三个变量temp，首先前两个数比较，把较小的数放在temp中，然后用temp再去跟剩下的数据比较，如果出现比temp小的数据，就用它代替temp中原有的数据。具体参照后面的代码示例，相信你在学排序之前已经学过for循环语句了，这样的话，这里理解起来就特别容易了。

4.选择排序的时间复杂度

　　简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数永远都是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为3N (N - 1) /  2。

　　所以，综上，简单排序的时间复杂度为 O_(N²)。