一、观看PPT教程
【01】插入排序【02】计数排序
二、练习题（不清楚回头查看有关PPT）
【01】有关插值排序的描述，请改正错误的地方：插入排序算法类似于玩扑克时抓牌的过程，玩家每拿到一张牌都要插入到手中已有的牌里，使之从小到大排好序。插入排序的基本思想是将未排序的元素分批插入到已排序序列中的适当位置，直到排序完成。排序步骤：1．首先将序列中的第一个元素视为已排序部分；2．取下一个待排序元素，从后向前扫描已排序序列；3．直到找到第一个小于或等于所取元素的位置，将所取元素插入该位置的后面，并将插入点之后的数据依次往后移动一个位置；4．重复步骤 2、3，直到所有元素排序完成。【02】下面是对序列{2, 8, 7, 9, 7}进行升序排序的代码，请改正错误的地方（不能增减句子和改变句型）：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
#include<iostream>using namespace std;void insertionSort(int arr[], int n){ for(int i = 1; i < n; i++){ int key = arr[i]; int j = i - 1; while(j>=0 && arr[j] > key){ arr[j + 1] = arr[j]; j--; } if(++j > i)arr[j] = key; }}int main(){ int arr[] = {2, 8, 7, 9, 7}; int n = sizeof(arr)/sizeof(int); insertionSort(arr, n); cout << "最后排序结果："; for(int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; return 0;}
【03】下面是有关插入排序优化的描述，请改正错误的地方：
直接插入排序每次向已排序序列插入数据时，是按顺序依次往前插入，数据量较大时，必然比较耗时，效率低。如：｛2，3，4，5，6，1｝，将未排序元素 1 插入到已排序序列2，3，4，5，6中，需要比较5次。如果在往前查找时采用二分查找的方式，即折半查找，效率上会有所提升。如：｛2，3，4，5，6，1｝，将未排序元素1插入到已排序序列2，3，4，5，6中，需要比较2次。优化步骤：1．将第一个元素视为已排序序列；2．取出下一个元素，在已排序的元素序列中二分查找到第一个比它大的元素的位置，如果找不到，则该位置在末尾；3．将新元素插入到该位置，并将插入点后的元素依次向后移动一个位置；4．重复2、3步骤。【04】下面是优化插入排序代码，请改正错误的地方（不能增减句子和改变句型）：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
#include<iostream>using namespace std;void binaryInsertSort(int arr[], int n){ int key, left, right, middle; for(int i = 1; i < n; i++){ key = arr[i]; left = 0; right = i - 1; while(left <= right){ middle = (left + right)/2; if(arr[middle] >= key) right = middle - 1; else left = middle + 1; } for(int j = i -1; j >= left; j--)arr[j+1]=arr[j]; if(left != i)arr[left] = key; }}int main(){ int arr[] = {2, 8, 7, 9, 7}; int n = sizeof(arr)/sizeof(int); binaryInsertSort(arr, n); cout << "最后排序结果："; for(int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; return 0;}
【05】编程题（插入排序和优化的插入排序两种方法）：书籍排序
【06】编程题（插入排序和优化的插入排序两种方法）：数据排序
【07】下面是插入排序性能分析，请改正错误的地方：1．在插入排序中，最好的情况是未排序数组已经有序，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 n-1次。时间复杂度为O(n)。2．当输入的数组是逆序排列时，插入排序需要每次将当前元素与前面的所有元素进行比较，并且每次比较都需要进行元素的移动操作。在最坏情况下，插入排序的时间复杂度为O(n²)。3．在平均情况下，插入排序的时间复杂度也为O(n²)，因为无论输入的数组是什么顺序，都需要比较和移动元素来保持已排序部分有序。4．插入排序的空间复杂度为O(1)，即它只需要使用常数级别的额外空间来存储临时变量，不随输入规模的增加而增加。这是因为插入排序是在原数组上进行操作，不需要额外的辅助空间来存储排序结果。因此，插入排序是一种原地排序算法。5．插入排序是不稳定的，如果未排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序可能改变。【08】下面是插入排序总结，请改正错误的地方：1）插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。尤其当数据基本有序时，采用插入排序可以明显减少数据交换和数据移动次数，进而提升排序效率。在STL的 sort 算法和 stdlib的qsort 算法中，都将插入排序作为快速排序的补充，用于少量元素的排序；2）直接插入排序的实现是一种不稳定的排序算法。【08】下面是计数排序的概述，请改正错误的地方：
计数排序是一种非比较排序算法，其核心思想是通过记录每个元素的出现次数来进行排序。这个算法的特点是速度快且稳定，适用于较大范围内的整数排序。计数排序本质上是一种特殊的桶排序，所有的桶就是计数数组，当桶的个数最大的时候，就是计数排序。【09】计数排序——基础版的步骤，请改正错误的地方：
1．找出原数组的长度值；2．根据长度值，创建计数数组进行计数3．利用计数数组输出排序元素【10】下面是使用计数排序，排6、1、3、5、9、5、9、5、3、8的代码，请改正错误的地方（不能增减句子和改变句型）：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
#include<iostream>using namespace std;void countSort(int arr[], int n){ int max_val = arr[0]; for(int i = 1; i < n; i++){ if(max_val < arr[i]){ max_val = arr[i]; } } int range = max_val + 1; int count[range] = {0}; for(int i = 0; i < n; i++){ count[arr[i]]++; } cout << "最后排序结果："; for(int i = 0; i < range; i++){ while(--count[i] > 0){ cout << i << " "; } } cout << endl;}int main(){ int arr[] = {6, 1, 3, 5, 9, 5, 9, 5, 3, 8}; int n = sizeof(arr)/sizeof(int); countSort(arr, n); return 0;}
【11】基础版的问题及空间优化，请改正下面描述错误的地方：
例如：给定包含 10个整数的无序数列：16、11、13、15、19、15、19、20、13、18。
按照基础版计数排序完成排序。找到最大值 20，计数数组的范围为0～20，由于给定的整数中不包含0～10，实际的计数过程中，0～10的空间并未使用。如果给定的整数较大且比较集中，浪费的空间会更为明显，体现不出计数排序的优势，也会使效率降低。可以通过序列最大值、最小值的差值建立计数数组范围，将大的区间映射到小的区间，例如上述序列0～20映射到0～9，同时将最大值 20 作为后续元素的基准值，在不浪费空间的同时完成计数排序。
【12】下面是优化了的计数排序步骤，请改正错误的地方：
1．找出原数组中的最大值、平均值；2．根据平均值、最大值，创建计数数组进行计数3．利用计数数组输出排序元素【13】下面是无序数组16、11、13、15、19、15、19、20、13、18的计数排序（优化）的代码，请把错误的地方修改过来（不能增减句子和改变句型）：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
#include<iostream>using namespace std;void countSort(int arr[], int n){ int max_val = arr[0]; int min_val = arr[0]; for(int i = 1; i < n; i++){ if(max_val < arr[i]){ max_val = arr[i]; } if(min_val > arr[i]){ min_val = arr[i]; } } int range = max_val - min_val + 1; int * count = new int[range](); for(int i = 0; i < n; i++){ count[arr[i]-min_val]++; } cout << "最后排序结果："; for(int i = 0; i < range; i++){ while(count[i]-- > 0){ cout << i << " "; } } cout << endl; delete [] count;}int main(){ int arr[] = {16, 11, 13, 15, 19, 15, 19, 20, 13, 18}; int n = sizeof(arr)/sizeof(int); countSort(arr, n); return 0;}
【14】计数排序的稳定性的有关描述，改正错误的地方：一般我们所说的计数排序都是稳定的，上面的计数排序算法在解决空间浪费后依旧不稳定。即相同元素的相对位置在排序后会被改变。那么如何保证计数排序的稳定性呢？其实很简单，只需在统计完待排序元素的次数后，对count 作累加计算（count［i＋1］＝count［i＋1］＋count［i］），即计算元素在排序后的最终位置；然后倒序第二次遍历原数组，根据 count 数组中的排序位置来将待排序元素放入合适的位置（需要容下全部元素的新数组），同时将 count 数组相应的值减 1，使下一个重复的排序元素可以放在后一位的位置上，以保证稳定性。【15】稳定的计数排序步骤，请改正错误的地方：
1. 找出原数组中的最大值、最小值；2. 根据最小值、最大值，创建计数数组进行计数；3. 利用递推统计小于等于该元素个数；4. 利用递推结果，重新遍历原数组进行排序。【16】下面是稳定的计数排序代码，请更正错误之处（不能增减句子和改变句型）：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
#include<iostream>using namespace std;void countSort(int arr[], int n){ int max_val = arr[0]; int min_val = arr[0]; for(int i = 1; i < n; i++){ if(max_val < arr[i]){ max_val = arr[i]; } if(min_val > arr[i]){ min_val = arr[i]; } } int range = max_val - min_val + 1; int * count = new int[range](); int * output = new int[range](); for(int i = 0; i < n; i++){ count[arr[i]-min_val]++; } for(int i = 0; i < range -1; i++){ count[i+1] += count[i]; } for(int i = 0; i < n; i++){ output[--count[arr[i] - min_val]] = arr[i]; } cout << "最后排序结果："; for(int i = 0; i < n; i++){ cout << output[i] << " "; } cout << endl; delete [] count; delete [] output;}int main(){ int arr[] = {16, 11, 13, 15, 19, 15, 19, 20, 13, 18}; int n = sizeof(arr)/sizeof(int); countSort(arr, n); return 0;}
【17】编程题：含负整数的计数排序给定如下含负整数的无序序列，利用计数排序的思想，完成该序列的稳定排序。
初始序列：arr[]={-2，-1，3，-2，-3，3，0}
【18】下面是计数排序的总结，请更正错误的地方：
计数排序是一种简化的桶排序算法，核心是通过元素的值和数组索引完成元素的个数计数及位置排序，元素之间不参与比较。计数排序时间、空间复杂度(这里以稳定的计数排序进行说明)：时间复杂度：O(N + k)；空间复杂度：O(N + k)。优点：稳定性好，通过数组索引来确定元素位置，计数排序可以做到线性的时间复杂度。缺点：1. 需要额外空间来储存计数数组和排序数组；2. 多数情况下，适用于数据范围较小的正整数排序。