【java基础】选择排序算法原理+实现

川长思鸟来 2022-08-23 05:42 136阅读 0赞

# 思想: #

一次遍历,只需一次交换;

选择排序,每次选最小,放在已排序队列末尾,依次进行,直到全部排序完成.

# 执行: #

![Center][]

(1)从待排序序列中，找到最小的元素；

(2)如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；

(3)从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

[1, 54, 6, 3, 78, 34, 12, 45]
    ---第1轮 
    ---------第1次 
    1 54 6 3 78 34 12 45  
    ---------第2次 
    1 54 6 3 78 34 12 45  
    ---------第3次 
    1 54 6 3 78 34 12 45  
    ---------第4次 
    1 54 6 3 78 34 12 45  
    ---------第5次 
    1 54 6 3 78 34 12 45  
    ---------第6次 
    1 54 6 3 78 34 12 45  
    ---------第7次 
    1 54 6 3 78 34 12 45  
    ---第2轮 
    ---------第2次 
    1 3 6 54 78 34 12 45  
    ---------第3次 
    1 3 6 54 78 34 12 45  
    ---------第4次 
    1 3 6 54 78 34 12 45  
    ---------第5次 
    1 3 6 54 78 34 12 45  
    ---------第6次 
    1 3 6 54 78 34 12 45  
    ---------第7次 
    1 3 6 54 78 34 12 45  
    ---第3轮 
    ---------第3次 
    1 3 6 54 78 34 12 45  
    ---------第4次 
    1 3 6 54 78 34 12 45  
    ---------第5次 
    1 3 6 54 78 34 12 45  
    ---------第6次 
    1 3 6 54 78 34 12 45  
    ---------第7次 
    1 3 6 54 78 34 12 45  
    ---第4轮 
    ---------第4次 
    1 3 6 12 78 34 54 45  
    ---------第5次 
    1 3 6 12 78 34 54 45  
    ---------第6次 
    1 3 6 12 78 34 54 45  
    ---------第7次 
    1 3 6 12 78 34 54 45  
    ---第5轮 
    ---------第5次 
    1 3 6 12 34 78 54 45  
    ---------第6次 
    1 3 6 12 34 78 54 45  
    ---------第7次 
    1 3 6 12 34 78 54 45  
    ---第6轮 
    ---------第6次 
    1 3 6 12 34 45 54 78  
    ---------第7次 
    1 3 6 12 34 45 54 78  
    ---第7轮 
    ---------第7次 
    1 3 6 12 34 45 54 78  
    1 3 6 12 34 45 54 78

# 分析: #

如下代码可看出，选择排序的时间复杂度是O(n\*n)；由于此算法利用了一个临时空间，当做中转位置来放置每次的最小值，所以，它的空间复杂度是O(1).

# 实现： #

import java.util.Arrays;
    
    public class selectSort {  
    
        	public static void main(String[] args){
    	       int a[]={1,54,6,3,78,34,12,45};  
    	        //输出定义的数组
    	       System.out.println(Arrays.toString(a));
    	       
    	       //可以理解成这是一个每次比较的标志位
    	       int position=0;  
    	  
    	       for(int i=1;i<a.length;i++){  
    	           System.out.println("---第"+i+"轮 ");
    	           
    	           position=i;  
    	           //定义一个临时存放数值
    	           int temp=a[i];  
    	  
    	           //内层循环---循环找出当前最小的，和标志位的数字比较，若小则交换位置
    	           for(int j=i;j<a.length;j++){  
    	  
    		           if(a[j]<temp){  
    		  
    		              temp=a[j];  
                                                                                                              
    		              position=j;  
    		           }  
    		           
    		           System.out.println("---------第"+j+"次 ");
    		         //依次循环输出当前数组中的数字
    					 for (int l = 0; l < a.length; l++) {  
    			                System.out.print(a[l] + " ");  
    			            }  
    			            System.out.println(" "); 
    	          } 
    	           //若本轮中数字不用交换位置，则保持当前
    	           a[position]=a[i];  
    	           a[i]=temp; 
    	       }  
    	    }  
    }

[Center]: /images/20220721/5edc754233ac40dc825f575a1f2bee27.png