选择排序与冒泡排序

数组中常见的操作就是对数组进行排序，我们常用的排序方法有两种，即冒泡排序和选择排序，这篇博客，我们一起来详细了解一下这两种排序方法的使用方法。

 

选择排序

1、选择排序具体过程如下图，排序过程是从左向右排序，选取数组第一个元素，依次和后面的元素比较大小，如果小于第一个元素，则将两个元素的位置交换，最终将最小的元素放在数组第一个位置，然后进行第二个位置存储元素的选择，即我们可以理解为选择排序是从前向后排序的过程。

2、具体代码示例：

class  selectSort
{
	public static void main(String[] args) 
	{
		int[] arr = {1,8,5,87,34,98};
		System.out.println("排序前");
		print(arr);
		System.out.println("排序后");
		selectSort(arr);
		print(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;
				}
			}
		}
	}

	//打印数组
	public static void print(int[] arr)
	{
		for (int i=0; i<arr.length ;i++ )
		{
			if(i!=arr.length-1)
				System.out.print(arr[i]+",");
			else
				System.out.print(arr[i]+"\n");
		}
	}
}

运行结果

 

冒泡排序 

1、如下图，冒泡排序的过程，是将一个数组中相邻的两个元素进行比较，将较大的元素向后移，最终将最大的数据移动至数组的最后一位，即我们可以理解为冒泡排序是从后向前排序的过程。

2、具体代码示例：

class  bubbleSort
{
	public static void main(String[] args) 
	{
		int[] arr = {1,97,5,87,34,98};
		System.out.println("排序前");
		print(arr);
		System.out.println("排序后");
		bubbleSort(arr);
		print(arr);
	}
	
	//冒泡排序示例
	public static void bubbleSort(int[] arr)
	{
		for (int i=0 ; i<arr.length-1 ; i++ )
		{
			for (int j=0; j<arr.length-1-i ; j++ )
			{
				if(arr[j] > arr[j+1])
				{
					swap(arr,j,j+1);
				}
			}
		}
	}

	//打印数组
	public static void print(int[] arr)
	{
		for (int i=0; i<arr.length ;i++ )
		{
			if(i!=arr.length-1)
				System.out.print(arr[i]+",");
			else
				System.out.print(arr[i]+"\n");
		}
	}

	//数据交换
	public static void swap(int[] arr,int a,int b)
	{
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}

运行结果

 

排序方法优化

1、因为选择排序和冒泡排序，在每一次内循环中，只要符合交换条件，就会进行数据交换，这样排序性能并不是最好的，所以我们可以换一种思考方式，在内存中定义两个变量，一个用于存放数组元素，一个用于存放数组角标，我们在内层循环中不进行数据交换，仅记录最小元素的角标，当我们执行完内层循环时，在进行数据交换，这样可以对排序方法进行优化，如下图。

2、我们用选择排序来举例

class  selectSort
{
	public static void main(String[] args) 
	{
		int[] arr = {1,8,5,87,34,98};
		System.out.println("排序前");
		print(arr);
		System.out.println("排序后");
		selectSort(arr);
		print(arr);
	}
	
	//优化后选择排序示例
	public static void selectSort(int[] arr)
	{
		for (int i=0 ; i<arr.length-1 ; i++ )
		{
			int num = arr[i];
			int index = i;
			for (int j=i+1; j<arr.length ; j++ )
			{
				if(arr[i] > arr[j])
				{
					num = arr[j];
					index = j;
				}
			}
			swap(arr,i,index);
		}
	}

	//打印数组
	public static void print(int[] arr)
	{
		for (int i=0; i<arr.length ;i++ )
		{
			if(i!=arr.length-1)
				System.out.print(arr[i]+",");
			else
				System.out.print(arr[i]+"\n");
		}
	}

	//数据交换
	public static void swap(int[] arr,int a,int b)
	{
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}

运行结果

总结

1、值得注意的是，我上面的冒泡排序和选择排序的函数并没有设置返回值，因为，我们要清楚，排序过程是对堆内存中存储的数据进行排序且数组的首地址不会改变，而数组名称和数组的首地址（指针）都存储在栈内存中，这一部分并没有改变，所以排序函数并不需要返回值，如果对栈内存和堆内存还有疑惑，可以去看我的这一篇博客：https://blog.****.net/qq_41819988/article/details/88542485。

2、实际上，Java有自带的排序方法，采用的方法是希尔排序，我们需要时调用就可以了，但是我们还是需要熟练掌握选择排序和冒泡排序，因为面试可能会考到。