java 排序 1和1_新手入门-冒泡排序和选择排序第一节排序1.1排序概述排序（

怼烎@ 2022-11-10 03:47 112阅读 0赞

该楼层疑似违规已被系统折叠 隐藏此楼查看此楼

新手入门-冒泡排序和选择排序

第一节排序

1.1排序概述

排序(sorting)的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。

内部排序和外部排序

一类是整个排序过程在内存储器中进行，称为内部排序；

另一类是由于待排序元素数量太大，以至于内存储器无法容纳全部数据，排序需要借助外部存储设备才能完成，这类排序称为外部排序。

本章介绍的排序方法都属于内部排序

比较排序和非比较排序

大部分排序都是需要通过比较首先来判断大小，作为排序的依据的。

但是也有例外的，比如计数排序、基数排序，不需要进行比较。效率可以做到更高，但是会有一些限制条件，也可能需要更多的空间。

冒泡排序、选择排序、直接插入排序是最基本的三种排序，效率最低，但是算法简单。排序的学习一般从这三种排序算法开始。

1.2冒泡排序

冒泡排序的算法

1) 整个数列分成两部分：前面是无序数列，后面是有序数列

2) 初始状态下，整个数列都是无序的，有序数列是空

3) 如果一个数列有n个元素，则至多需要n-1趟循环才能保证数列有序

4) 每一趟循环可以让无序数列中最大数排到最后，(也就是说有序数列的元素个数增加1)

5) 每一趟循环都从数列的第一个元素开始进行比较，依次比较相邻的两个元素，比较到无序数列的末尾即可(而不是数列的末尾)

6) 如果前一个大于后一个，交换

【示例1】冒泡排序算法

public class TestBubbleSort1\{ public static void main(String \[\] args)\{ //定义一个无序数组 int \[\] arr = \{75,87,56,45,89,100,76,34,89,97\}; //排序前输出 System.out.println("排序前"); for(int score :arr)\{ System.out.print(score+"\\t"); \} //排序 //大循环：n个元素排序，则至多需要n-1趟循环 for(int i=0;i arr\[j+1\])\{ //交换 int temp; temp = arr\[j\]; arr\[j\] = arr\[j+1\]; arr\[j+1\] = temp; \} \} \} //排序后输出 System.out.println("\\n排序后"); for(int score :arr)\{ System.out.print(score+"\\t"); \} \} \}

缺点1：每一趟比较都要比较到数组的最后，没有必要，只要比较到无序数列的最后即可

for(int j=0;j

i j

0 <6

1 <5

2 <4

3 <3

i j<6-i scoreArr.length-1-i

解决：j

缺点2：不管是否有序，都要进行n-1趟循环；

如何判断有序：比较了一趟，没有发生交换

解决：定义一个符号量flag，默认有序true；发生交换，置为false，

一趟循环结束后，根据flag的值判断是否有序；有序，退出即可；

【示例2】完善冒泡排序算法

public class TestBubbleSort2\{ public static void main(String \[\] args)\{ //定义一个无序数组 int \[\] arr = \{75,87,56,45,89,100,76,34,89,97\}; //排序前输出 System.out.println("排序前"); for(int score :arr)\{ System.out.print(score+"\\t"); \} //排序 bubbleSort(arr); //排序后输出 System.out.println("排序后"); for(int score :arr)\{ System.out.print(score+"\\t"); \} \} public static void bubbleSort(int arr\[\])\{ //大循环：n个元素排序，则至多需要n-1趟循环 int temp; int i; for(i=0;i arr\[j+1\])\{ //交换 temp = arr\[j\]; arr\[j\] = arr\[j+1\]; arr\[j+1\] = temp; //发生了交换，数组无序 flag = false; \} \} //3.判断是否有序，有序，退出 if(flag)\{ break; \} \} //System.out.println("\\n一共进行了"+(i+1)+"趟循环"); \} \}

1.3 选择排序

选择排序的算法

1) 整个数列分成两部分：前面是有序数列，后面是无序数列

2) 初始状态下，整个数列都是无序的，有序数列是空

3) 一共n个数，需要n-1趟循环(一趟都不能少)

4) 每比较完一趟，有序数列数量+1，无序数列数量-1

5) 每趟先假设无序数列的第1个元素(整个数列的第i个元素)是最小的，让当前的最小数，从第i+1个元素开始比较，一直比较到最后一个元素。如果发现更小的数，就假设当前数是最小数。

6) 一趟比较完后，将发现最小数和无序数列的第一个数交换(如果最小数不是无序数列的第一个数)

【示例3】选择排序

public class TestSelectSort \{ public static void main(String\[\] args) \{ //给定无序的数组 int \[\] scoreArr = \{75,87,56,45,89,100,76,34,89,97\}; //输出无序的数组 System.out.println(Arrays.toString(scoreArr)); //选择排序 selectSort(scoreArr); //输出有序的数组 System.out.println(Arrays.toString(scoreArr)); \} public static void selectSort(int\[\] scoreArr) \{ //大循环：n个元素排序，则需要n-1趟循环 for(int i=0;i scoreArr\[j\])\{ minIndex = j; \} \} //一趟比较完后，或者最小值的索引，如果不是第i个，就交换 if(minIndex !=i)\{ int temp; temp = scoreArr\[i\]; scoreArr\[i\] = scoreArr\[minIndex\]; scoreArr\[minIndex\] = temp; \} \} \} \}

注意

q 冒泡排序最多需要n-1趟循环，最少1趟循环；选择排序必须进行n-1趟循环，一趟也不能少

q 冒泡排序中最多的操作就是比较和交换，一趟循环中可能发生多次交换；而选择排序中最多的操作是比较，一趟比较结束后如果发现更小的值才交换一次。

q 如果数组元素不是基本数据类型，而是对象，应该如何判断大小呢？可以让相应类实现Comparable接口并调用comparTo()方法进行比较。

q 快速排序是冒泡排序的完善版，都是基于交换的排序，是各种基于比较的排序算法中效率最高的，用到了分治和递归的思想。需要认真准备。

本节作业

1. 使用冒泡排序实现对分数排序

2. 使用选择排序实现对分数排序

3. 可选：使用选择排序实现对课程名称(比如Java、MySQL等)按照字母排序

4. 可选：查询资料掌握直接插入排序算法并实现对分数排序