JavaSE基础 - 数组排序之选择排序

逃离我推掉我的手 2022-05-28 03:43 150阅读 0赞

**选择排序的原理：**每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

**时间复杂度：**最好或者最坏的情况下时间复杂度都是![e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg][]。

为了方便后续操作，采用数组的静态创建方式创建原始数组，如下：

int[] arr = new int[]{12,-3,89,43,66};

排序过程如下：

![20180328231949796][]

过程解释：

第一次比较：用arr\[0\]和后面的每个数组数据做比较，由于arr\[0\] > arr\[1\]，所以交换位置。第一次交换为后的数组为：-3，12，89，43，66。

第二次比较：用arr\[1\]和后面的每个数组数据做比较。由于arr\[1\] < arr\[2-4\]，所以位置不变。非如此交换后的数组为：-3，12，89，43，66。

第三次比较：用arr\[2\]和后面的每个数组数据做比较。由于arr\[2\] > arr\[3\]，所以交换位置；然后arr\[2\]继续和arr\[4\]继续比较，由于arr\[2\]小于arr\[4\],所以位置不变。第三次交换后的数组为：-3，12，43，89，66。

第四次比较：用arr\[3\]和arr\[4\]比较，由于arr\[3\] > arr\[4\],所以交换位置。最终结果为：-3,12,43,66,89。

**规律：每次都用前一个数和后面所有的数做比较，只要碰到比它大的数就交换位置。**

代码如下：

class ArrayDemo4
    {
    	public static void main(String[] args) 
    	{
    		int[] arr = new int[]{12,-3,89,43,66};
    		selectSort(arr);
    		show(arr);
    	}
    
    	//需求：选择排序（从小到大）
    	public static void selectSort(int[] arr)
    	{
    		for (int i = 0; i < arr.length - 1; i++)
    		{
    			for (int j = i + 1; j < arr.length ; j++)
    			{
    				if (arr[i] > arr[j])
    				{
    					int temp = arr[i];
    					arr[i] = arr[j];
    					arr[j] = temp;
    				}
    			}
    		}
    		return;
    	}
    
    	//需求：显示排序后的数组。
    	public static void show(int[] arr)
    	{
    		System.out.println("数组元素如下：");
    		for (int i = 0; i < arr.length; i++)
    		{
    			System.out.print(arr[i] + " ");
    		}
    	}
    }

**选择排序的性能问题：**选择排序的过程中，比较一遍，可能需要多次交换数组的元素的位置。如果能减少交换次数，便可以提高选择排序的性能。

**改进1：**定义两个变量，分别临时保存一次比较中最小的数和该数的角标值，一次比较结束后更换在数组中的位置.也就是说，一次比较，仅需交换一次位置，在一定程度上改善选择排序的性能。

代码如下：

class Sort 
    {
    	public static void main(String[] args) 
    	{
    		int[] arr = new int[]{12,-3,89,43,66};
    		improveSelectSort(arr);
    		show(arr);
    	}
    
    	public static void improveSelectSort(int[] arr)
    	{
    		int temp,index;		//存放一次比较后最小的值和该数的角标值。
    
    		for (int i = 0; i < arr.length - 1; i++)
    		{
    			index = i;
    
    			for (int j = i + 1; j < arr.length; j++)
    			{
    				if(arr[j] < arr[index])
    				{
    					index = j;
    				}
    			}
    
    			//交换位置
    			if(index != i){
    				temp = arr[i];
    				arr[i] = arr[index];
    				arr[index] = temp;
    			}
    
    		}
    	}
    
    	public static void show(int[] arr)
    	{
    		System.out.println("排序后的数组元素如下：");
    		for (int i = 0; i < arr.length; i++)
    		{
    			System.out.print(arr[i] + " ");
    		}
    	}
    }

改进2：在改进1的基础之上对交换位置的代码块进行封装。（Ps:因为方法先要入栈内存，每次交换后都会被释放掉，所以斗胆尝试封装。具体会不会提高性能，这个我没验证过）

代码如下：

class Sort 
    {
    	public static void main(String[] args) 
    	{
    		int[] arr = new int[]{12,-3,89,43,66};
    		improveSelectSort(arr);
    		show(arr);
    	}
    
    	public static void improveSelectSort(int[] arr)
    	{
    		int temp,index;		//存放一次比较后最小的值和该数的角标值。
    
    		for (int i = 0; i < arr.length - 1; i++)
    		{
    			index = i;
    
    			for (int j = i + 1; j < arr.length; j++)
    			{
    				if(arr[j] < arr[index])
    				{
    					index = j;
    				}
    			}
    
    			//交换位置
    			if(index != i){
    				swap(arr,i,index);		//调用swap方法。
    			}
    
    		}
    	}
    
    	public static void show(int[] arr)
    	{
    		System.out.println("排序后的数组元素如下：");
    		for (int i = 0; i < arr.length; i++)
    		{
    			System.out.print(arr[i] + " ");
    		}
    	}
    
    	public static void swap(int[] arr,int a,int b)
    	{
    		int temp = arr[a];
    		arr[a] = arr[b];
    		arr[b] = temp;
    	}
    }

总结：选择排序是几种排序算法中的基础算法。希望我的文章对你有帮助。

[e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D40/sign=17b28fa860d0f703e2b294dc09fa9d5c/e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg
[20180328231949796]: /images/20220528/f8339038439a415fad1354fd72209f88.png