算法基础——冒泡排序和选择排序

发表于 | 分类于 > >
本文字数： 1.6k | 阅读时长 ≈ 1 分钟

冒泡排序

原理分析：

索引0和1比；1和2比；2和3比…

  • 两两比较，较大者和较小者交换位置，最后一个数不需要主动比较
  • 因此第一轮后，最大数就在最大索引处
  • 第二轮开始，比较次数因此减1次
  • 因此，总比较轮数为数组长度减1轮

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class BubbleSort {

	public static void main(String[] args) {

		int[] arr = {24, 69, 80, 57, 13};
		System.out.println("排序前：\n" + Arrays.toString(arr));
		bubbleSort(arr);
		System.out.println("排序后：\n" + Arrays.toString(arr));

	}

	private static void bubbleSort(int[] arr) {

		// 控制比较轮数
		for (int i = 0; i < arr.length - 1; i++) {

			// 控制比较次数
			// -1是因为最后一个索引不需要主动比较
			// -i是因为每轮比较的最大索引即是最大值，因此，每过1轮即可少比较一次
			for (int j = 0; j < arr.length - 1 - i; j++) {

				// 比较大小，大值向后交换
				if (arr[j] > arr[j + 1]) {
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
	}
}

选择排序

选择排序

原理分析：

索引：0和1比，0和2比，0和3比…

  • 值小的往前交换，一轮结束，最小索引处即是最小值
  • 内循环的索引对应被比较的对象，内循环启始索引永远比外循环索引大1位
  • 每一轮都需要比较直到最大索引处，但是启始索引每一轮都会加1位
  • 外循环控制比较轮次，也是当前比较者的索引；类似于冒泡排序，轮次等于数组长度减1次

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class SelectSort {

	public static void main(String[] args) {

		int[] arr = {24, 69, 80, 57, 13};
		System.out.println("排序前：\n" + Arrays.toString(arr));
		selectSort(arr);
		System.out.println("排序后：\n" + Arrays.toString(arr));
	}

	private 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;
				}
			}
		}
	}
}