八大排序之选择排序—选择排序

怼烎@ 2022-05-13 04:18 181阅读 0赞

## 选择排序 ##

参考：[https://www.cnblogs.com/shen-hua/p/5424059.html][https_www.cnblogs.com_shen-hua_p_5424059.html]  
我们在一个序列当中选出一个最大的（升序为最小的），然后和第一个元素交换，然后后面再在剩下的找最大的，再和第二个元素交换。这样最终就可以得到一个有序的序列。

时间复杂度：简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数永远都是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为3N (N - 1) / 2。  
所以，综上，简单排序的时间复杂度为 O(N2)。

代码：

public class SelectSort {
    	public static void main(String[] args) {
    		int[] arr = {12,32,123,54,2,643,3,45,765,22};
    		SelectSort ss = new SelectSort();
    		ss.selectSort(arr);
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i]+" ");
    		}
    	}
    	
    	public void selectSort(int[] arr){
    		// 做第i趟排序
    		for (int i = 0; i < arr.length-1; i++) {
    			int k = i;
    			for (int j = i+1; j < arr.length; j++) {
    				 //找到最小的数的下标
    				if (arr[j] < arr[k] ) {
    					k = j;//记下目前找到的最小值所在的位置
    				}
    			}
    			//在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
    			if (k != i) {//交换a[i]和a[k]
    				int temp = arr[k];
    				arr[k] = arr[i];
    				arr[i] = temp;
    			}
    		}
    	}
    }

**优化版本**：  
根据上边的分析，如果在每一次查找最小值的时候，也可以找到一个最大值，然后将两者分别放在它们应该出现的位置，这样遍历的次数就比较少了。  
代码：

public class Main {
    	public static void main(String[] args) {
    		int[] arr = { 12, 32, 0, 54, 2, 643, 3, 45, 765, 22 };
    		Main ss = new Main();
    		ss.selectSort(arr);
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i] + " ");
    		}
    	}
    
    	public void selectSort(int[] arr) {
    		int left = 0;
    		int right = arr.length - 1;
    		int min = left;// 存储最小值的下标
    		int max = left;// 存储最大值的下标
    		while (left <= right) {
    			for (int i = left; i <= right; i++) {
    				if (arr[i] < arr[min]) {
    					min = i;
    				}
    				if (arr[i] > arr[max]) {
    					max = i;
    				}
    			}
    			int temp = arr[left];
    			arr[left] = arr[min];
    			arr[min] = temp;
    			if (left == max) {
    				max = min;
    			}
    			int temp1 = arr[right];
    			arr[right] = arr[max];
    			arr[max] = temp1;
    			left++;
    			right--;
    		}
    	}
    }

[https_www.cnblogs.com_shen-hua_p_5424059.html]: https://www.cnblogs.com/shen-hua/p/5424059.html