level 7
我是😈乖宝宝
楼主
新手入门-冒泡排序和选择排序
第一节排序
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.length-1;i++){ //小循环：每一趟循环都从数列的前两个元素开始进行比较， //比较到数组的最后 for(int j=0;j<arr.length-1;j++){ //如果前一个大于后一个 if(arr[j] > 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<scoreArr.length-1;j++){ }
i j<?
0 <6
1 <5
2 <4
3 <3
i j<6-i scoreArr.length-1-i
解决：j<scoreArr.length-1 修改为 j<scoreArr.length-1-i
缺点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.length-1;i++){ //1. 假设有序 boolean flag = true; //2.小循环：每一趟循环都从数列的前两个元素开始进行比较， // 比较到数组的最后 for(int j=0;j<arr.length-1-i;j++){ //如果前一个大于后一个 if(arr[j] > 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.length-1;i++){ //第i趟先假设第i个最小 int minIndex = i; //从第i+1个元素开始，依次使用最小元素和每元素比较，一直比较到最后 for (int j = i+1; j <scoreArr.length ; j++) { if(scoreArr[minIndex] > 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. 可选：查询资料掌握直接插入排序算法并实现对分数排序
2020年06月02日 15点06分
1
第一节排序
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.length-1;i++){ //小循环：每一趟循环都从数列的前两个元素开始进行比较， //比较到数组的最后 for(int j=0;j<arr.length-1;j++){ //如果前一个大于后一个 if(arr[j] > 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<scoreArr.length-1;j++){ }
i j<?
0 <6
1 <5
2 <4
3 <3
i j<6-i scoreArr.length-1-i
解决：j<scoreArr.length-1 修改为 j<scoreArr.length-1-i
缺点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.length-1;i++){ //1. 假设有序 boolean flag = true; //2.小循环：每一趟循环都从数列的前两个元素开始进行比较， // 比较到数组的最后 for(int j=0;j<arr.length-1-i;j++){ //如果前一个大于后一个 if(arr[j] > 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.length-1;i++){ //第i趟先假设第i个最小 int minIndex = i; //从第i+1个元素开始，依次使用最小元素和每元素比较，一直比较到最后 for (int j = i+1; j <scoreArr.length ; j++) { if(scoreArr[minIndex] > 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. 可选：查询资料掌握直接插入排序算法并实现对分数排序