选择排序算法的实现及原理---Java实现

亦凉 2023-01-07 05:55 127阅读 0赞

# 选择排序 #

## 选择排序的原理 ##

**选择排序：每循环一次，从要比较的元素当中找出最小值，用这个最小值和所参加比较的最前面的元素交换位置**

## 选择排序的思路分析 ##

给定一个数组 arr \[3,1,6,2,5\]

*  要比较的元素：3 1 6 2 5 （这一堆参加比较的元素中最左边的元素下标为0）
 *  **第1次循环**：找出最小的元素与所参加比较的最前面的元素交换位置
 *  交换位置后元素排列为：1 3 6 2 5  
      
    
 *  要比较的元素：3 6 2 5 （这一堆参加比较的元素中最左边的元素下标为1）
 *  **第2次循环**：抛开在上次循环后的最小元素，在剩下的元素中找出要比较的元素中最小元素，并与最左边的元素交换位置
 *  交换位置后元素排列为：2 6 3 5  
      
    
 *  要比较的元素：6 3 5
 *  **第3次循环**：抛开在上次循环后的最小元素，在剩下的元素中找出要比较的元素中最小元素，并与最左边的元素交换位置
 *  交换位置后元素排列为：3 6 5  
      
    
 *  要比较的元素： 6 5
 *  **第4次循环**：抛开在上次循环后的最小元素，在剩下的元素中找出要比较的元素中最小元素，并与最左边的元素交换位置
 *  交换位置后元素排列为： 5 6

*  最后只剩一个元素6

**注：5个元素进行选择排序，循环了4次**

**代码实现如下：**

package Sort;
    public class selectSort { 
    	public static void main(String[] args) { 
    		int[] arr = { 3,1,6,2,5};
    // 5个元素比较4次
    		for (int i = 0; i < arr.length-1; i++) { 
    // i 为 0 1 2 3
    // i 正好是“参加比较的这堆元素中最左边的那个元素的下标”
    // i 正好是参与比较的这堆元素中的起点下标
    // 假设 起点下标i位置上的元素是最小的
    			int min = i;
    // 拿着下标i位置的元素与后面参与比较的元素进行比较，如果发现有比它还要小的元素，则这两个元素交换位置
    			for(int j = i+1;j<arr.length;j++) { 
    				if(arr[j] < arr[min]) { 
    					min = j ; //此时最小值元素下标的是j，所以将j的值赋给min
    				}
    			}
    			
    // 当 i 和 min 相等时，表示假设成立
    // 当 i 和 min 不相等时，表示假设不成立，有比假设更小的元素
    // 此时，需要拿着这个更小的元素和要比较的元素中最左边的元素交换位置
    			if(min != i) { 
    // 表示存在更小的元素
    // arr[min] 指的是最小的元素
    // arr[i] 指的是最前面的元素
    				int temp;
    				temp = arr[min];
    				arr[min] = arr[i];
    				arr[i] = temp;
    			}
    		}
    // 排序后进行遍历
    		for (int i : arr) { 
    			System.out.print(i + " "); //1 2 3 5 6
    		}
    	}
    }