（贵州省普通高中信息学奥赛CSP-JS NOIP—提高组C++知识点讲解）第6讲 排序2

学科竞赛编程 C++ NOIP NOI IOI 1 1 PART ONE 基本思想  1. 插入排序 当读入一个元素时,在已经排序好的序列中,搜索它正确的位置,再放入读入的元素。但不该忽略一个重要的问题: 在插入这个元素前,应当将它后面的所有元素后移一位,以保证插入位置的原元素不被覆盖。 2、扑克牌-->插入排序 回忆一下打牌时抓牌的情景,为了方便打牌,抓牌时一般一边抓牌一边按花色和大小插入到恰当的位置,当抓完所有的牌时,手中的牌便是有序的,这排序方法即为插入排序。 3、插入排序的过程 【问题描述】使用插入排序的方法将数列6,5,3,4,1,2从小到大排序。 【样例输出】1 2 3 4 5 6 第一步:拿出前2个数进行比较,按照从小到大排列。 【过程分析】 6 5 5 6 第二步:拿出第3个数与前面2个数进行比较,插入从小到大合适的位置。 6 5 3 3 5 6 1 PART ONE 第三步: 拿出第4个数与前面3个数进行比较,插入从小到大合适的位置。 3 5 6 4 3 4 5 6 第四步: 拿出第5个数与前面4个数进行比较,插入从小到大合适的位置 3 4 5 6 1 1 3 4 5 6 第五步:拿出第6个数与前面5个数进行比较,插入从小到大合适的位置,完成排序。 1 3 4 5 6 2 1 2 3 4 5 6 1 PART ONE 【问题描述】 输入n个整数,将n个数按从小到大的顺序输出(n<=10000)。 【样例输入】 8 49 38 65 97 76 13 27 49 【样例输出】 13 27 38 49 49 65 76 97 【问题分析】 具体的实现步骤: (1) 读入数据存放在a数组中。 (2) 对数组中从第2个元素,把它和前面已经排好序的元素按照从后往前的 顺序进行比较, 如果小于前面的元素,则把该元素插入到被比较的元素前面; 如果大于则不变。 (3) 重复前面第二步,依次拿数组中的元素做第2步的运算,直到排序完成,就完成了插入排序。 4、插入排序的应用 1 PART ONE #include<iostream> usingnamespace std; const int MAXN =10001; int main(){ int n,k,i,j; int a[MAXN]; cin>>n; for(i =0;i<n;i++) //输入要排序的数列 cin>>a[i]; for(i=1;i<n;i++){ int key=a[i]; j=i-1; while(j>=0 & key<a[j]){ a[j+1]=a[j]; j--; } a[j+1]= key; } //输出已经排列好顺序的数列 for(i=0;i<n;i++) cout<<a[i]<<" "; return 0; } 完整代码 1 PART ONE 1. 桶排序 点击添加文本 点击添加文本 点击添加文本 基本思想  若干待排序的值在一个明显的有限范围内(整型)时,可设计有限个有序桶,待排序的值装入对应的桶(当然也可以装入若干个值),桶号就是待排序的值,顺序输出各桶的值,将得到有序的序列 1 PART ONE 2. 桶排序的过程 【问题描述】10个小朋友按成绩的 从大到小排序，成绩是十分制。 【样例输入】 3 5 1 7 2 8 5 2 9 3 【样例输出】 9 8 7 5 5 3 3 2 2 1 【过程分析】 第一步: 在该题中由于最大的数字可能是10,所以我们准备11个"桶子"(数组)。 注: 桶适用于数据的范围有限的情况下。 哎,考的真是惨不忍睹.... 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 PART ONE 第二步: 遍历输入待排序的数组,把数字当做我们准备的桶子(数组)下标,桶子(数组)里对应的位置存的数加1,要是待排序的数字列里有重复的数字,则桶子里的数字重复加1。 1 2 2 0 2 0 1 1 2 0 0 1 2 3 4 5 6 7 8 9 10 11