Java基本排序算法 -- 直接选择排序

ゝ一纸荒年。 2023-10-06 12:00 59阅读 0赞

## `一、直接选择排序` ##

> 直接选择排序是一种简单的排序方法。它每次从待排序的记录序列中选取关键字最小的记录，把它同当前记录序列中的第一个记录交换位置。具体的作法是：
> 
>  *  (1)开始时,待排序序列为R\[0\]…R\[n-1\],经过选择和交换后,R\[0\]中存放最小关的记录
>  *  (2)第二次待排序记录序列为R\[1\]…R\[n-1\],经过选择和交换后,R\[1\]为仅次于R\[0\]的具有次小关键字的记录;
>  *  (3)如此类推,经过n-1次选择和交换之后,R\[0\]…R\[n-1\]成为有序序列,即可实现排序

> A=(16，15，19，16，18，19，20，14)![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]

public class SelectSort {
        
    
    	/** 直接选择排序 */
    	public void selectSort(int[] data) {
        
    		int i, j, small;
    		int temp;
    		for (i = 0; i < data.length - 1; i++) {
        
    			small = i;
    			for (j = i+1; j < data.length; j++) {
         //寻找最小的数据元素
    				if (data[j] < data[small]) {
        
    					small = j; // 记录最小的数据元素
    				}
    			}
    			if (small != i) {
         // 交换数据元素
    				temp = data[i];
    				data[i] = data[small];
    				data[small] = temp;
    			}
    		}
    	}	
    }

> 在直接选择排序中,不论初始记录序列状态如何,共需进行n-1次交换，每选择需要进行ni次比较(1≤i≤n-1),而每次交换最多需要3次移动。因此,总的比较次数为：> C = ∑ n − 1 i = 1 ( n − i ) = 1 2 ( n 2 − n ) C=\\sum\_\{n-1\}^\{i=1\}(n-i)=\\frac\{1\}\{2\}(n^2-n) C=∑n−1i=1(n−i)=21(n2−n)总的移动次数为： M = ∑ n − 1 i = 1 3 = 3 ( n − 1 ) 。 M=\\sum\_\{n-1\}^\{i=1\}3=3(n-1)。 M=∑n−1i=13=3(n−1)。  
> 由此可见,直接选择排序的时间复杂度为0(n2),所以当记录占用的字节数较多时,通常比直接插入排序的执行速度要快。  
> 由于在直接选择排序中存在着不相邻记录之间的互换，因此，直接选择排序是一种不稳定的排序方法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200716233248529.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70