基本思想

 每一趟从待排序的数据元素中选出最小（最大）的元素，顺序放在待排序的数列最前，直到全部待排序的数据元素全部排完。

特点

 数据结构：数组

 稳定性：不稳定

过程


 初始关键字：『 8，5，2，6，9，3，1，4，0，7 』

 第一趟排序后：0，『5，2，6，9，3，1，4，8，7』

 第二趟排序后：0，1，『2，6，9，3，5，4，8，7』

 第三趟排序后：0，1，2，『6，9，3，5，4，8，7』

 第四趟排序后：0，1，2，3，『9，6，5，4，8，7』

 第五趟排序后：0，1，2，3，4，『6，5，9，8，7』

 第六趟排序后：0，1，2，3，4，5，『6，9，8，7』

 第七趟排序后：0，1，2，3，4，5，6，『9，8，7』

 第八趟排序后：0，1，2，3，4，5，6，7，『8，9』

 第九趟排序后：0，1，2，3，4，5，6，7，8，『9』

 结果：          『 0，1，2，3，4，5，6，7，8，9 』

 

 

          

   排序过程           宏观过程

 

复杂度与辅助空间


 最差时间复杂度：O(n^2)

 最优时间复杂度：O(n^2)

 平均时间复杂度：O(n^2)

 所需辅助空间：O(1)

实现方法


 双重循环，外层i控制当前序列最小（最大）值存放的数组元素位置，内层循环j控制从i+1到n序列中选择最小的元素所在位置k。

源程序
 


void select_sort(int a[],int n)
{
    for(int i=0;i<n-1;i++)//i为已排序序列的末尾
    {
        for(int j=i+1;j<n;j++){
            if(a[j]<a[i]){
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
            
    }
}

优化 

void select_sort(int a[],int n)
{
    int min;
    for(int i=0;i<n-1;i++)//i为已排序序列的末尾
    {
        min=i;
        for(int j=i+1;j<n;j++)//未排序序列
            if(a[j]<a[min])//找出未排序序列中的最小值
                min=j;
        if(min!=i)
            swap(a[i],a[min]);//放到已排序序列的末尾，该操作很有可能把稳定性打乱，所以选择排序是不稳定的排序算法
    }
}
 

JAVA版本

//选择排序
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr={1,3,2,45,65,33,12};
        System.out.println("交换之前：");
        for(int num:arr){
            System.out.print(num+" ");
        }        
        //选择排序的优化
        for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
            int k = i;
            for(int j = k + 1; j < arr.length; j++){// 选最小的记录
                if(arr[j] < arr[k]){ 
                    k = j; //记下目前找到的最小值所在的位置
                }
            }
            //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
            if(i != k){  //交换a[i]和a[k]
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }    
        }
        System.out.println();
        System.out.println("交换后：");
        for(int num:arr){
            System.out.print(num+" ");
        }
    }

}