Java从入门到精通_学习笔记07（数组的排序算法）

冒泡算法

冒泡排序算法是最常用的数组排序算法之一，它排序数组元素的过程总是将较小的数往前放、较大数往后放，类似水中旗袍往上升的动作，所以称作冒泡排序。

1. 基本思想

冒泡排序的基本思想是比较相邻的元素值，如果满足条件就交换元素值，把较小的元素移到数组前面，把较大的元素移到数组后面（交换两个元素在数组中的位置）。

2. 算法实现原理

冒泡算法由 双层循环 实现，其中外层循环用于控制排序的轮次（一般为数组长度减1），内层循环用于控制相邻两元素的比较次数，若满足条件就交换位置，内层循环的每次的开始比较的位置都是从0索引处开始。

详细排序过程：

• 数组长度为6，所以设置外层循环轮次为(6-1) = 5；
• 第一轮内层数组元素两两之间需要比较5次，第二轮需要进行4次，第三轮需要进行3次，第四轮需要进行2次，第五轮需要进行1次。
• 内层循环每比较一次，若满足交换条件，就交换一次比较元素的位置。

3. 算法实现

public class BubbleSort{
	public static void main(String args[]){
		// 创建一个乱序的数组
		int arrays[] = {63,4,24,1,3,15};
		// 创建冒泡排序的对象
		BubbleSort sorter = new BubbleSort();
		sorter.showArray(arrays);
		sorter.sort(arrays);
	}
	
	/**
	*冒泡排序
	*
	*@param arr
	*要排序的数组
	*/
	public void sort(int arr[]){
		// 双层循环实现冒泡算法
		for(int i = 0 ; i < arr.length-1 ; i++){ // 外层循环控制冒泡排序的轮次
			for(int j = 0 ; j < arr.length - i ; j++){ // 内存循环控制相邻元素比较的次数
				if(arr[j] > arr[j + 1]) { // 满足交换条件，就交换位置
					int temp = arr[j] ; // 将较大值赋值给一个空的整型变量
					arr[j] = arr[j+1] ; // 将较小值往前移
					arr[j + 1] = temp ; // 将较大值往后移
				}
			}
		}
		showArray(arrays);
	}
	
	/**
	*显示数组中的所有元素
	*
	*@ param arr
	*要显示的数组
	*/
	public void showArray(int arr[]) {
		// 使用foreach循环遍历数组
		for(int a : arr){
		System.out.print(">" + a);
		}
	}
}

直接选择排序

直接选择排序是属于选择排序的一种，排序速度比冒泡速度快一些，也是常用的排序算法。

1. 基本思想

直接选择排序的基本思想是将指定排序位置与其他数组元素分别进行比较，如果满足交换条件就交换位置。与冒泡排序的不同是，直接选择排序不是比较相邻位置，而是指定一个位置，将其他数组一一分别于它进行较。 相比于冒泡排序，直接选择排序的交换次数要少很多。

2. 算法实现原理

详细排序过程：

• 首先指定要进行比较的位置，如：数组末尾为15；
• 将其他位置的数组元素分别与数组末尾处的元素值进行比较，若符合交换条件，就交换元素位置；

3. 算法实现

public class SelectSort{
	public static void main(String args[]){
		// 创建一个无序数组
		int array[] = {63,4,24,1,3,15};
		// 创建直接排序类的对象
		SelectSort sorter = new SelectSort();
	}
	/**
	*直接选择排序
	*
	*@param arr
	*要排序的数组
	*/
	public void sort(int arr[]){
		int index;
		// 实现直接选择排序
		for(int i = 1 ; i < arr.length - 1 ; i++){
			index = 0; // 每次循环从索引值为0处开始比较选择
			for(int j = 1 ; j <= arr.length - i ; j++){
				if(arr[j] > arr[index]){
				index = j; //找到最大值所在的索引值
				}	
			}
		// 交换在位置arr.length - i 和index(最大值)上的两个数
		int temp = arr[arr.length - i]; // 把最后一个元素值赋值给temp
		arr[arr.length - i] = arr[index]; // 将最大值arr[index]移到数组 arr.length-i 位置处
		arr[index] = temp; // 将temp保存的值保存到index位置处
		}
		showArray(arr);
	}
	
	/**
	*显示数组中的所有元素
	*
	*@ param arr
	*要显示的数组
	*/
	public void showArray(int arr[]) {
		// 使用foreach循环遍历数组
		for(int a : arr){
		System.out.print(">" + a);
		}
	}
}

反转排序

反转排序就是以相反的顺序把原有数组的内容重新排序。

1. 基本思想

反转排序的思路就是把数组最后一个元素与第一个元素交换位置，倒数第二个元素与第二个元素交换位置，依次完成反转替换。

2. 算法实现原理

详细排序过程：

• 通过数组长度，计算出排序的循环次数：数组长度的半次数( i = 数组引用名.length / 2 )；
• 每次循环就交换一次元素位置。

3. 算法实现

public class ReverseSort{
	public static void main(String args[]){
		// 创建一个数组
		int array[] = {10,20,30,40,50,60};
		// 创建反转排序类的对象
		ReverseSort sorter = new ReverseSort();
		sorter.sort(array);
	}
/**
	*反转排序
	*
	*@param arr
	*要排序的数组
	*/
	public void sort(int arr[]){
		System.out.println("数组排序前的顺序：");
		showArray(arr);
		//实现反转排序
		int temp;
		int len = arr.length;
		for(int i = 0 ; i < len / 2 ; i++){
			temp = arr[i];
			arr[i] = arr[len - 1 - i];
			arr[len - 1 - i] = temp;	
		}
		System.out.println("数组排序后的顺序：");
		showArray(arr);
	}
	
	/**
	*显示数组中的所有元素
	*
	*@ param arr
	*要显示的数组
	*/
	public void showArray(int arr[]) {
		// 使用foreach循环遍历数组
		for(int a : arr){
		System.out.print(">" + a);
		}
	}
	
}

本文地址：https://blog.csdn.net/qq_42429057/article/details/107593303