排序之简单选择排序详解

今天药忘吃喽~ 2023-07-20 05:40 28阅读 0赞

## 1.核心思想 ##

数组第一个数字与剩下的n-1个数字比较，遇到比自身小的就交换，以达到筛选出最小值的目的，经过一轮，最小值在下标为0的位置，第二轮，下标为1的数字与剩下的n-2个数字比较，方法与第一轮一样，经过多轮这样的操作，达到排序的目的。**相当于每次从一个篮子里找出当前篮子里面最小的鸡蛋，有序的放到另外一个篮子里，但是这里没有使用额外的数组空间。**

## 2.图解 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70]  
9和7比较，7比9小，互换，并向后移  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 1]  
7和3比较，3比7小，互换，并向后移  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 2]  
3和2比较，2比3小，互换，并后移  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 3]  
4不小于2，后移  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 4]  
5不小于2 ，后移  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 5]  
1小于2，互换。第一轮排序完成，最小值2在下标为0的位置，多次类似操作，可得到有序序列

## 3.完整代码 ##

c语言

#include<stdio.h>
    int main(){ 
    	int nums[]={ 9,7,3,2,4,5,1};
    	int t,i,j,len=sizeof(nums)/sizeof(nums[0]);
    	for(i=0;i<len-1;i++){ 
    		for(j=i+1;j<len;j++){ //每次从未排序的地方开始比较 
    			if(nums[j]<nums[i]){ //遇到比自身小的数字，互换 
    				t=nums[j];
    				nums[j]=nums[i];
    				nums[i]=t;
    			}
    		}
    	}
    	for(i=0;i<len;i++)
    		printf("%d,",nums[i]);
    	return 0;
    }

java

public class SelectSort { 
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		int[] nums=new int[] { 1,7,3,9,4,5,2};
    		for(int i=0;i<nums.length-1;i++) { 
    			for(int j=i+1;j<nums.length;j++){ 
    				if(nums[i]>nums[j]) { 
    					int t=nums[i];
    					nums[i]=nums[j];
    					nums[j]=t;
    				}
    			}
    		}
    		for(int e:nums)
    			System.out.print(e+" ");
    	}
    }

## 直接选择排序与冒泡排序 ##

直接选择排序时间复杂度是O(n²)，冒泡排序是每一趟每相邻两个数字之间相互比较，直接选择排序是每趟一个数字与剩下的为排序的数字相互比较

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70]: /images/20230528/c9b8eba6d0f54158a4ae7e72f2048228.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 1]: /images/20230528/af08d49a11c54223bd408989621627af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 2]: /images/20230528/8bf4eb3262af4dd9a174f5c0696c3d52.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 3]: /images/20230528/7409c40f9e7e4cd297fccd8137410a19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 4]: /images/20230528/4bf715eb2182481cb98b09c2c749f06c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 5]: /images/20230528/c95b692595fb487ba60d956e7a0a315e.png