从零开始学算法--冒泡排序和选择排序
2021/10/5 1:42:12
本文主要是介绍从零开始学算法--冒泡排序和选择排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
数据结构： 指计算机组织存储数据的方式， 其实就是数据之间的关系。我们通常从逻辑和存储两个角度来理解数据结构
逻辑结构：集合结构，线性结构，树形结构，图形结构
存储结构：表，数组，堆栈，队列，树，图。。。
衡量一个算法的优劣： 空间复杂度（算法运行时占用的内存空间）+时间复杂度（关键代码的执行次数）+应用场景（非常重要）
一个简单例子帮我们理解时间复杂度：
fun1的时间复杂度为n^2 + n +1, fun2的时间复杂度为n^2
但是我们一般认为fun1和fun2的时间复杂度是相同的， 因为当n趋于无穷大时， 主要是看n的几次方
冒泡排序
比如我们有个数组 {3,1,6,8,4,9,7,2,5}， 现在要对它进行升序排序。那么我们的思路是：
第一轮， 数组元素两两比较， 如果前一个数比后一个数大， 则这两个数交换位置。对于上面的数组，3>1, 所以1和3交换位置， 1成为第一个元素； 然后3小于6，位置不变，3成为第二个元素； 然后6小于8， 位置不变， 6成为第三个元素； 然后8大于4， 所以8和4交换位置， 4成为第四个元素。。。。以此类推， 第一轮排序完成后， 最大数9会固定在数组的最后位置。
代码实现：
//冒泡排序的步骤一：两两比较， 把大的放到后面
public static void bubbleTest(int[] array) {
//注意这里i<length-1, 因为只需要遍历到倒数第二个数
for (int i = 0; i < array.length-1; i++) {
//如果前一个数大于后一个数
if (array[i] > array[i+1]) {
//则两个数交换位置
int temp = array[i+1];
array[i+1] = array[i];
array[i] = temp;
}
}
}
public static void main(String[] args) {
int[] testData = {3,1,6,8,4,9,7,2,5};
bubbleTest(testData);
for (int i = 0; i < testData.length; i++) {
System.out.print(testData[i]+" ");
}
}
运行结果：
我们看到经过第一轮排序， 最大数9已经被放到了最后的位置，接下来进行第二轮排序
第二轮， 重复第一轮的方法，但是我们只需要比较前面8个元素，就可以将数字8放到数组的倒数第二个位置
接下来再重复第一轮的方法，就只需要比较前7个元素。。。
以此类推， 直到数组中只有一个元素
代码实现：基于上面的方法，加个for循环就可以实现。
public static void bubbleTest(int[] array) {
//冒泡排序的步骤二：重复步骤一，
for (int j = array.length-1; j > 0; j--) {
//冒泡排序的步骤一：两两比较， 把大的放到后面
for (int i = 0; i < j; i++) {
//如果前一个数大于后一个数
if (array[i] > array[i+1]) {
//则两个数交换位置
int temp = array[i+1];
array[i+1] = array[i];
array[i] = temp;
}
}
}
}
看下运行结果
我们看到， 冒泡算法的核心就是不断进行两两比较并交换位置。那么对于长度为n的数组，比较的次数为 (n-1) + (n-2) + (n-3)... + 1. 当数据量很小时，我们可以认为其时间复杂度为n
另外， 上面的写法还可以进行优化
可以想象， 只有在极端情况下， 数组才需要进行(n-1) + (n-2) + (n-3)... + 1这么多次比较， 通常情况下， 经过几次比较就已经得到了排序正确的数组， 那么这时我们就需要跳出循环，直接看代码
1 public static void bubbleTest(int[] array) {
2 //冒泡排序的步骤二：重复步骤一，
3 for (int j = array.length-1; j > 0; j--) {
4 boolean flag = true;
5 //冒泡排序的步骤一：两两比较， 把大的放到后面
6 for (int i = 0; i < j; i++) {
7 //如果前一个数大于后一个数
8 if (array[i] > array[i+1]) {
9 //则两个数交换位置
10 int temp = array[i+1];
11 array[i+1] = array[i];
12 array[i] = temp;
13 //如果发生了交换，把flag置为false
14 flag = false;
15 }
16 }
17 //如果flag为true, 说明没有发生交换，也就是说当前已经是正确的排序
18 if (flag) {
19 //则跳出循环
20 break;
21 }
22 }
23 }
当n很小，如小于5时， 冒泡排序效率最高
- 选择排序
选择排序就是我们先固定第一个元素，从后面的元素中找到最小的元素，和第一个元素交换
然后再固定第二个元素， 从后面的元素中得到最小的，和第二个交换
。。。。。。
我们先看第一次排序的代码
1 public static void selectSort(int[] array) {
2 int index = 0;
3 //从数组的第二个元素开始遍历
4 for (int i = 1; i < array.length; i++) {
5 //如果当前元素比第一个元素小
6 if (array[i] < array[index]) {
7 //将index定位到i
8 //这样，当for循环走完时， index就将定位到数组中最小的元素
9 index = i;
10 }
11 }
12 //上面的代码已经得到了最小元素的Index
13 //那么下一步就将数组第一个位置元素和index位置的元素交换
14 int temp = array[index];
15 array[index] = array[0];
16 array[0] = temp;
17 }
18
19 public static void main(String[] args) {
20 int[] testData = {3,1,6,8,4,9,7,2,5};
21 selectSort(testData);
22
23 for (int i = 0; i < testData.length; i++) {
24 System.out.print(testData[i]+" ");
25 }
26 }
运行结果：
可以看到，最小数字1已经被放到了第一个位置
然后下一步， 重复上面的步骤，体现在代码里就是for循环
1 public static void selectSort(int[] array) {
2 for (int j = 0; j < array.length; j++) {
3 int index = j;
4 //从数组的第j+1个元素开始遍历
5 for (int i = j+1; i < array.length; i++) {
6 //如果当前元素比第j个元素小
7 if (array[i] < array[index]) {
8 //将index定位到j
9 //这样，当for循环走完时， index就将定位到数组中最小的元素
10 index = i;
11 }
12 }
13 //上面的代码已经得到了最小元素的Index
14 //那么下一步就将数组第j个位置元素和index位置的元素交换
15 int temp = array[index];
16 array[index] = array[j];
17 array[j] = temp;
18 }
19 }
运行结果：
同样的， 上述方法也可以进行优化
1 public static void selectSort(int[] array) {
2 for (int j = 0; j < array.length; j++) {
3 int index = j;
4 //从数组的第j+1个元素开始遍历
5 for (int i = j+1; i < array.length; i++) {
6 //如果当前元素比第j个元素小
7 if (array[i] < array[index]) {
8 //将index定位到j
9 //这样，当for循环走完时， index就将定位到数组中最小的元素
10 index = i;
11 }
12 }
13 if (index != j) {
14 //上面的代码已经得到了最小元素的Index
15 //那么下一步就将数组第j个位置元素和index位置的元素交换
16 int temp = array[index];
17 array[index] = array[j];
18 array[j] = temp;
19 }
20 }
21 }
如果Index等于j, 说明index位置上的元素就已经时最小的元素， 那么就不需要再执行交换
相对于冒泡排序来说， 选择排序减少了交换的次数。
但是当数组size很小时， 几乎没有区别
- tips: 交换两个变量的方法
方法一： 借助中间变量（可读性最好）
1 public static void main(String[] args) {
2 int a = 3;
3 int b = 5;
4 System.out.println("a= "+a+" b="+b);
5 int c=b;
6 b = a;
7 a= c;
8 System.out.println("after swap, a= "+a+" b="+b);
9 }
这里我们新加了一个变量c， 那么能不能不要呢？
方法二：
1 public static void main(String[] args) {
2 int a = 3;
3 int b = 5;
4 System.out.println("a= "+a+" b="+b);
5 a = a+b; //a=8, b=5
6 b = a-b; //a=8, b=3
7 a= a-b; //a=5, b=3
8 System.out.println("after swap, a= "+a+" b="+b);
9 }
方法二利用加减法消除了中间变量，节省了空间， 但有个缺点是只适用于数字， 不适用于一般对象
方法三， 位运算 （性能最优）
1 public static void main(String[] args) {
2 int a = 3; //011
3 int b = 5; //101
4 System.out.println("a= "+a+" b="+b);
5 a = a^b; //a=110, b=101
6 b = a^b; //a=110, b=011
7 a= a^b; //a=101
8 System.out.println("after swap, a= "+a+" b="+b);
9 }
这种方法利用了二进制的异或， 同样节省了中间变量，运行速度也快
但缺点是可读性差。 所以一般情况下我们还是用方法一， 只有在内存空间紧张的情况下才会考虑方法二三（如无人机等要求空间占用少）
这篇关于从零开始学算法--冒泡排序和选择排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-12-26大厂数据结构与算法教程：入门级详解
- 2024-12-26大厂算法与数据结构教程：新手入门指南
- 2024-12-26Python编程入门指南
- 2024-12-26数据结构高级教程：新手入门及初级提升指南
- 2024-12-26并查集入门教程：从零开始学会并查集
- 2024-12-26大厂数据结构与算法入门指南
- 2024-12-26大厂算法与数据结构入门教程
- 2024-12-26二叉树入门教程：轻松掌握基础概念与操作
- 2024-12-26初学者指南：轻松掌握链表
- 2024-12-26平衡树入门教程：轻松理解与应用
