一、观看PPT教程
【01】排序算法【02】冒泡排序【03】选择排序
二、练习题（不清楚回头查看有关PPT）
【01】有关排序算法的描述，错误的是：①排序就是将一组元素按照特定的顺序进行排列。
②排序只有按照升序（从小到大）或降序（从大到小）的方式对元素进行排序。
③排序过程一般都要进行元素的比较和交换。
④在处理大量数据时，会对算法的效率有要求，需要考虑到数据的各种限制寻找一种合适的排序算法，因此便演变出多种排序算法。
【02】常用排序算法的描述，错误的是：
①比较排序包括交换排序、选择排序、插入排序、归并排序。
②交换排序包括冒泡排序和快速排序。
③选择排序包括选择排序和堆排序。④插入排序包括插入排序和希尔排序。
⑤归并排序包括二路归并排序和多路归并排序。
⑥非比较排序包括计数排序、桶排序、基数排序和哈希排序。
⑦排序算法的优缺点主要从三个方面来评价：时间复杂度、空间复杂度和稳定性（相同值的元素排序后如果一定保持原来的顺序是稳定排序，否则是不稳定排序。）。【03】有关冒泡排序的描述，错误的是：
①冒泡排序的名字由来是因为特点的元素会经由交换慢慢“浮”到数列的顶端，就如同碳酸饮料中的二氧化碳的气泡最终会浮到顶端一样，故名“冒泡排序”。
②以从小到大的排序为例，冒泡排序的基本思想是——从数列的第一个元素开始比较相邻的元素，如果前面的元素比后面的元素大，那么就交换，一轮之后，最大的元素必要在最后，扣除最后的元素，用同样的方法处理，如此类推。直到所有的元素成为有序的序列。③以从大到小的排序为例，冒泡排序的基本思想是——从数列的第一个元素开始比较相邻的元素，如果前面的元素比后面的元素小，那么就交换，一轮之后，最小的元素必要在最后，扣除最后的元素，用同样的方法处理，如此类推。直到所有的元素成为有序的序列。
④以从大到小的排序为例，如果数列已经从小到大的排序，冒泡排序会直接倒置数列从而完成排序。【04】以从小到大的排序为例的排序步骤，请改正错误的地方：
①从待排序序列中的第一个元素开始，比较相邻的两个元素；
②如果后一个元素大于前一个元素，则交换这两个元素的位置；③继续编辑下一对相邻元素，重复步骤2，直到本轮元素操作完成（假如序列有n个元素，第一轮比较到n-1对，第二轮到n-2对，如此类推）；
④重复上述①、②、③过程；
⑤直到所有元素都排序完成。
【05】下面是对序列{6, 4, 9, 7, 2}进行升序排序的代码，请修改其中错误的地方：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
#include<iostream>using namespace std;void bubbleSort(int arr[], int n){ for(int i = n-1; i > 0; i--){ for(int j = 0; j < i; j++){ if(arr[j] < arr[j + 1]){ swap(arr[j], arr[j + 1]); } } }}int main(){ int arr[] = {6, 4, 9, 7, 2}; int n = sizeof(arr)/sizeof(int); bubbleSort(arr, n); cout << "最后排序结果："; for(int i = 0; i < n; i++) cout << arr[i] << " "; return 0;}
【06】冒泡排序优化的原理描述，错误的是：
①假如经过前面记录排序后，整个序列就已经排好序了，其实后面的几轮就无需再做排序了。即使后面记录排序只进行比较不进行交换，但是当元素数量很大的时候，依旧会很耗时。
②因此，我们在做排序操作时要对序列进行判断，如果整个系列已排好序了，就停止后续的排序操作。
③如果在某一轮排序中，没有发生元素交换或只是最后一对元素发生交换，就说明已经排好序了。【07】下面是对序列{6, 5, 4, 1, 2, 3}进行升序排序的优化代码，改正错误的地方：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
#include<iostream>using namespace std;void bubbleSort(int arr[], int n){ for(int i = n-1; i > 0; i--){ int flag = i; for(int j = 0; j < i; j++){ if(arr[j] > arr[j + 1]){ swap(arr[j], arr[j + 1]); flag--; } } if(!flag)return; }}int main(){ int arr[] = {6, 5, 4, 1, 2, 3}; int n = sizeof(arr)/sizeof(int); bubbleSort(arr, n); cout << "最后排序结果："; for(int i = 0; i < n; i++) cout << arr[i] << " "; return 0;}
【08】编程题：升序排列学生身高
【09】编程题：车厢重组
【10】下面是冒泡排序性能分析，请把有错误的地方修改过来：
①冒泡排序是一种简单但效率不高的排序算法，它的时间复杂度为O(n²)。它适用于小规模数据的排序，但对于大规模数据来说效率较低。冒泡排序的优点是实现简单易懂，而缺点是效率较低。在实际应用中，更常使用更高效的排序算法，如快速排序、归并排序等。②最好和最坏及平均时间复杂度情况：1）当输入序列已经有序时，冒泡排序只需进行一次完整的遍历，即可判断序列已经有序，不需要进行任何交换操作。因此，最好情况下的时间复杂度为O(n)。2）当输入序列完全逆序排列时，冒泡排序需要进行n-1趟遍历，并且每趟遍历都需要比较和交换相邻元素的位置。因此，最坏情况下的时间复杂度为O(n²)。3）对于长度为n的序列，冒泡排序的平均情况下需要进行 n／2趟遍历，每趟遍历需要比较和交换的次数约为 n／2。因此，平均情况下的时间复杂度为O(n)。③冒泡排序只需要使用常数级别的额外空间来存储临时变量，因此空间复杂度为O(0)。④冒泡排序是一种不稳定的排序算法，相同元素的相对位置在排序前后可能会发生改变。【11】下面是冒泡排序的总结，请改正错误的地方：
①算法的核心思想是通过相邻元素之间的比较和交换，将最大的元素逐渐“冒泡”到序列的末尾。每一轮排序都会确定一个当前未排序部分的最大元素，并将其放置在正确的位置上；②当序列中有n个元素时，一共需要进行 n-1 轮操作，且第 i 轮需要比较n-i次，所以总共需要比较（n-1）＋（n-2）＋．．．＋1＝(n²+n)/2次；③当两个相邻元素相等时无需交换，所以相等元素的相对位置在整个排序过程中不发生变化，因此冒泡排序是一种稳定排序；④尽管冒泡排序的时间复杂度较高，但对于小规模的数据集来说，它的性能还是可以接受的；⑤在实际应用中，冒泡排序算法并不是最优选择，尤其对于大规模数据的排序。然而，它对于理解排序算法的基本原理和思想非常有帮助。【12】有关选择排序的描述，改正错误的地方：
①选择排序的基本思想是每次从待排序的数据中选取最小（或最大）的元素，将其与待排序中的第中间元素交换位置，直到排序完成。②排序步骤：
对数据{k1, k2, k3,……,kn}进行升序排列：第1趟从k1到kn中选择最小元素，将其与k1交换；第2趟从k2到kn中选择最小元素，将其与k2交换；第3趟从k3到kn中选择最小元素，将其与k3交换；以此类推；最后一趟从kn-1到kn中选择最小元素，将其与kn-1交换；此时所有元素都排序完成。【13】下面是对序列{4, 9, 7, 2, 6}进行升序排列的代码，请改正错误的地方：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
#include<iostream>using namespace std;void selectionSort(int arr[], int n){ for(int i = 0; i < n - 1; i++){ int minIndex = i; for(int j = i + 1; j < n; j--){ if(arr[j] < arr[minIndex]){ minIndex = j; } } if(i != minIndex){ swap(arr[i], arr[minIndex]); } }}int main(){ int arr[] = {4, 9, 7, 2, 6}; int n = sizeof(arr)/sizeof(int); selectionSort(arr, n); cout << "最后排序结果："; for(int i = 0; i < n; i++) cout << arr[i] << " "; return 0;}
【14】编程题：排队购票
【15】编程题：瓶子交换
【06】下面是选择排序总结，改正错误的地方：
①选择排序的优点是简单直观，实现起来比较容易，适用于小规模的排序任务。但是，由于其时间复杂度较高，对于大规模数据的排序，更高效的排序算法（如快速排序、归并排序）更为适合；②选择排序的时间复杂度O(n²)，其中 n是待排序序列的长度。每次选择最小（或最大）元素需要进行 n-i 次比较，共需进行 n-1 轮选择操作；③选择排序只需要常数级别的额外空间来存储临时变量，不需要额外的空间来存储待排序序列，因此空间复杂度为 O(1)；④选择排序是一种稳定的排序算法。