700字范文 > 浅谈排序算法：冒泡排序法和选择排序法的区别

浅谈排序算法：冒泡排序法和选择排序法的区别

时间：2020-12-19 16:47:01

之前学习了冒泡排序法和选择排序法，最近被老师问某个道题用的是什么排序法。自己居然答不出来，才发现自己没有真正弄懂，这两个算法的原理和区别，所以·····

1冒泡排序法

1.1什么是冒泡排序法？

顾名思义，冒泡排序法，就是把要排序的一组数据中的元素当成一个一个气泡,每次比较相邻两个相邻“气泡”的"轻重’，“气泡”较重的往下"沉"，轻的往上”浮“。

1.2原理

从第一个数开始，依次往后进行相邻两个数之间的比较，如果前面的数比后面的数大就交换这两个数的位置，如果前面的数较小或两者一样大，就不作处理。

1.3详细描述

➀比较相邻的元素的大小。如果第一个比第二个大，就交换它们两个的顺序；

➁对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

➂针对所有的元素重复以上的步骤，除了最后一个；

➃重复步骤➀~➂，直到排序完成。

1.4动态图片演示

1.5代码演示

1.5.1首先是从大到小

public class BubbleSortMax {public static void main(String[] args) {int[] array = { 1, 8, 5, 16, 32, 21 };int temp;System.out.print("原来数组排序为：");// for循环输出数组for (int i = 0; i< array.length; i++)System.out.print(array[i] + ",");//换行System.out.println();// 开始冒泡排序// 外层循环控制比较的趟数,一般为数组长度-1for (int i = 0; i < array.length - 1; i++) {// 内层循环控制每一趟排序多少次，一般为数组长度-外层循环变量-1for (int j = 0; j < array.length - i - 1; j++) {// 降序--如果前面小于后面则交换if (array[j] < array[j + 1]) {//引入temp变量作为交换媒介temp = array[j + 1];array[j + 1] = array[j];array[j] = temp;}}}System.out.print("由大到小的排序为：");// for循环输出数组for (int i= 0; i< array.length; i++)System.out.print(array[i] + ",");}}

运行结果：

1.5.2从小到大排序

public class BubbleSortMin {public static void main(String[] args) {int[] array = { 1, 8, 5, 16, 32, 21 };int temp;System.out.print("原来数组排序为：");// for循环输出数组for (int i = 0; i < array.length; i++)System.out.print(array[i] + ",");// 换行System.out.println();// 开始冒泡排序// 外层循环控制比较的趟数,一般为数组长度-1for (int i = 0; i < array.length - 1; i++) {// 内层循环控制每一趟排序多少次，一般为数组长度-外层循环变量-1for (int j = 0; j < array.length - i - 1; j++) {// 升序--如果前面大于后面则交换if (array[j] > array[j + 1]) {// 引入temp变量作为交换媒介temp = array[j + 1];array[j + 1] = array[j];array[j] = temp;}}}System.out.print("由小到大的排序为：");// for循环输出数组for (int i = 0; i < array.length; i++)System.out.print(array[i] + ",");}}

运行结果：

1.6对比分析

从上面两个排序我们可以发现，

1.外层控制循环的比较次数，循环次数：数组长度-1

2.内层控制循环排序次数，，循环次数：数组长度-外层循环变量-1

3.要实现一组数据的排序是从大到小还是从小到大，只需要改变下面这一行代码的比较大小符号即可。

if (array[j] > array[j + 1]) {

从小到大===大于号>

从大到小===小于号<

1.7冒泡排序法的主体框架

for (int i = 0; i < 数组长度变量名- 1; i++) {// 内层循环控制每一趟排序多少次，一般为数组长度-外层循环变量-1for (int j = 0; j <数组长度变量名 - i - 1; j++) {// 升序--如果前面大于后面则交换if (array[j] 视情况填写大于号和小于号array[j + 1]) {// 引入temp变量作为交换媒介temp = array[j + 1];array[j + 1] = array[j];array[j] = temp;}}}

1.8如何快速写出一个冒泡排序法

明白了原理，理解了从小到大和从大到小的规律，再记住冒泡排序法的基本框架，我们只需要确定几个量就可以写出一个冒泡排序法了。

步骤：

1.先确定所需要排序的数据元素个数----->用于确定外层循环的次数，循环次数：数组长度-1

2.确定内层循环次数，循环次数：数组长度-外层循环变量-1

3.根据从大到小还是从小到大的排序确定下面这行代码的符号

4.代入主体框架

if (array[j] 视情况填写大于号和小于号array[j + 1]) {

2.选择排序法

2.1什么是选择排序法？

还是顾名思义，选择排序法就是从需要排序的数据元素中选出最小或最大的一个元素，把他和第一个位置的元素进行互换。

2.2原理

通过自定义的最小值元素的下标，在内层循环中通过下标进行比较，查找过程中不移动数位置, 如果发现比自定义最小值元素下标还要小的值，则将该值的下标赋值给自定义的最小值元素下标。在一次内层循环结束后，将最小值元素交换至数组左端。

2.3详细描述

将要排序的数组分成两个数组，一个是有序数组一个是无序数组，再定义一个最值下标

假定有序数组是数组的第一个元素，这个最值也假定为数组的第一个数，最值下标从第一个数开始

然后将有序数组中的数和最值下标指向的数进行比较，如果无序数组中的数大于或小于有序数组中的数，那么将最大值或者最小值的下标更新为无序数组中那个值的下标

然后再将新的最大值或者最小值的下标和有序数组中的数比较，若大于或者小于，那就将它们两的值进行交换。

2.4动态图片演示

2.5代码演示

2.5.1首先是从大到小

public class SelectSortMax {public static void main(String[] args) {int[] a = { 1, 8, 5, 16, 32, 21 };int max;// 最大值下标int temp;// 外层循环控制循环次数,通常为数组长度-1for (int i = 0; i < a.length - 1; i++) {max = i;// 假设最大值是a[i],即a[0]for (int j = i + 1; j < a.length; j++) {if (a[j] > a[max])// 如果有比现在制定的最大元素还小的，就更新最大值下标max = j;}//退出内层循环后，判断最大下标是否//与原来相等，不等，说明有更大的，进行更新排序//if (a[i] != a[min]) {if (i != max) {// if (a[i] != a[min]) {//也可以更改这个temp = a[max];a[max] = a[i];a[i] = temp;}}for (int i = 0; i < a.length; i++)System.out.print(a[i] + ",");}}

运行结果：

2.5.2从小到大排序

public class SelectSortMin {public static void main(String[] args) {int[] a = { 1, 8, 5, 16, 32, 21 };int min;// 最小值下标int temp;// 外层循环控制循环次数,通常为数组长度-1for (int i = 0; i < a.length - 1; i++) {min = i;// 假设最小值是a[i],即a[0]for (int j = i + 1; j < a.length; j++) {if (a[j] < a[min])// 如果有比现在制定的最小元素还小的，就更新最小值下标min = j;}//退出内层循环后，判断最小下标是否//与原来相等，不等，说明有更小的，进行更新排序if (i != min) {//if (a[i] != a[min]) {// 也可以更改为这个temp = a[min];a[min] = a[i];a[i] = temp;}}for (int i = 0; i < a.length; i++)System.out.print(a[i] + ",");}}

运行结果：

2.6对比分析

1.外层控制循环的比较次数，循环次数：数组长度-1

2.内层控制循环排序次数，循环次数：数组长度

3.要实现一组数据的排序是从大到小还是从小到大，只需要改变下面这一行代码的比较大小符号即可。

if (a[j] < a[min])//或者是if (a[j] > a[max])

从小到大===大于号<

从大到小===小于号>

2.7冒泡排序法的主体框架

int max;// 最大值下标int temp;// 外层循环控制循环次数,通常为数组长度-1for (int i = 0; i < a.length - 1; i++) {max = i;// 假设最大值是a[i],即a[0]for (int j = i + 1; j < a.length; j++) {if (a[j] 视情况填写大于号和小于号 a[max])// 如果有比现在制定的最大元素还小的，就更新最大值下标max = j;}//退出内层循环后，判断最大下标是否//与原来相等，不等，说明有更大的，进行更新排序if (i != max) {// if (a[i] != a[min]) {//也可以更改这个temp = a[max];a[max] = a[i];a[i] = temp;}}