简单选择排序 java实现

刺骨的言语ヽ痛彻心扉 2022-06-15 10:57 179阅读 0赞

**简单选择排序**

基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

代码实现如下

public class SimpleSelectSort {
        public static void main(String[] args) {
            int[] arr={
       34,23,4,52,33,54,11,7,10,45,29};
            simpleSelectSort(arr);
            System.out.println("简单选择排序最终结果："+toString(arr));
        }
    
        private static void simpleSelectSort(int[] arr) {
            for(int i=0;i<arr.length-1;i++){
                int temp=0;
                int key=i;//假设刚开始是第i个位置最小
                for(int j=i+1;j<arr.length;j++){
                    if(arr[key]>arr[j]){
                        key=j;   //将最小值的索引赋值给key
                    }
                }
                temp=arr[i];
                arr[i]=arr[key];
                arr[key]=temp;
                System.out.println("循环第"+i+"次，排序结果："+toString(arr));
            }
    
        }
    
        //将数组转为字符串
        public static String toString(int[] a){
            StringBuffer sb=new StringBuffer();
               for(int each:a){
                   sb.append(each+" ");
               }
               return  sb.toString();
        }
    }

执行结果  
![这里写图片描述][SouthEast]

时间复杂度：  
简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数总是N (N -1) / 2。  
移动次数—当正序时，移动次数为0，当反序时，移动次数为3N（N-1）/2。所以时间复杂度为O（n^2）.

空间复杂度：  
简单选择排序需要占用 1 个临时空间，在交换数值时使用。

[SouthEast]: /images/20220615/0c24e13a7ab546b29b6efaa2d988a423.png