从零开始学算法--冒泡排序和选择排序

本文主要是介绍从零开始学算法--冒泡排序和选择排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

数据结构：指计算机组织存储数据的方式，其实就是数据之间的关系。我们通常从逻辑和存储两个角度来理解数据结构

逻辑结构：集合结构，线性结构，树形结构，图形结构

存储结构：表，数组，堆栈，队列，树，图。。。

衡量一个算法的优劣：空间复杂度（算法运行时占用的内存空间）+时间复杂度（关键代码的执行次数）+应用场景（非常重要）

一个简单例子帮我们理解时间复杂度：

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     }

这种方法利用了二进制的异或，同样节省了中间变量，运行速度也快

但缺点是可读性差。所以一般情况下我们还是用方法一，只有在内存空间紧张的情况下才会考虑方法二三（如无人机等要求空间占用少）

这篇关于从零开始学算法--冒泡排序和选择排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

从零开始学算法--冒泡排序和选择排序

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯