C++一维数组的排序

1、第三节数值型一维数组的应用一、数值型一维数组在递推中的应用【例5-3】斐波拉契数列：前两项为0和1,从第三项开始，各项均为前相邻两项之和:0, 1, 1, 2, 3, 5, 8, 11, 19,。写 C程序，输出该数列前 N项。【简要分析】显然这是一个典型的递推问题，结合数组，从第三个数开始，其递推公式是：xi=xi-1+xi-2 ，其中 i=2,3, ,N-1。利用循环结构，用 N-S流程图描述的程序逻辑如图5-2所示。设置环境，定义数组 xN,计数变量i赋初值：令 x0=0 , x1=1 , i=2;产生x数组：i v N产生新项：xi=xi-1+xi-2i=i+1输出x数组，结束图5-2

2、例5-3的N-S流程图参考源代码：/* 例 5-3 , 5-3.cpp */#include <stdlib.h>#define N 20void main()long i, xN;x0 = x1 = 0;/*赋初值*/for ( i = 2; i < N; i+ )/*尚剩18项*/xi = xi - 1 + xi - 2;/* 产生各项 */for ( i = 0; i < N; i+ )/* 输出数列 */cout<< "t" << xi;system( "pause"); 【思考验证】如果将x数组定

3、义为整型int ,程序是否能正常运行？【模仿训练】某数列前三项为 0、1、1,以后各项均为前相邻三项之和，输出该数列前 N项。二、排序【例5-4】键盘输入N个战士的身高，将其升序排列。【简要分析】排序是数组的经典应用，现实生活中用得太多，请读者务必掌握。排序的方法很多，数据结构中有详细介绍，请读者自己查阅，本例用比较法。具体实现逻辑是：将数组元素ai (i=0,1,2 , ,N-2 )与它后边的每一个元素a田(j=i+1, , ,N-1 )逐个比较，凡有 aj<ai 者则对调之(以保证 ai比任何aj都小)。 重复这个过程N-1次，最后a数组中元素便被升序排列。用 N-S图描述的程序逻辑

4、如图 5-3 所示。开始：定义数组aN,下标i、j,临时变量temp初始化a数组，并令i=0确定各ai的位置：i < N-2 ?令 j=i+1 N-1,凡 aj<ai 则交换 aj 、aii=i+1输出排序后的a数组，结束图5-3例5-4的N-S流程图参考源代码:/* 例 5-4 , 5-4_1.cpp */#include <stdlib.h> #define N 10 void main()/*本循环输入N个原始数据*/int aN, t, i, j;for ( i = 0; i < N; i+ )cin>> ai;for ( i = 0; i &

5、lt; N -1; i+ )/*本循环完成排序*/for ( j = i + 1; j < N; j+ )/* xi与它后边所有元素逐一比较，大则交换*/if ( aj < ai) temp = aj; aj = ai; ai = temp; for ( i = 0; i < N; i+ )/*输出排序后的数组 */cout<< ai;system( "pause");【思考验证】怎样修改本程序以实现降序排列?还有一种排序方法称为冒泡法。这种方法可形象描述为：使较小的值象水中的空气泡一样逐渐“上浮”到数组的顶部，而较大的值则逐渐“下沉”到数组的

6、底部。这种技术要排序好几轮，每轮都要比较连续的数组元素对。如果某一对元素的值本身是升序排的，那就保持原样，否则交换其值。排序过程的N-S流程如图5-4所示。开始：定义数组aN,下标i、j,临时变量temp初始化a数组，并令i=0i < N-2 ?j=0j v N-i?若 aj > aj+1则交换 aj、aj+1j=j+1i=i+1输出排序后的a数组，结束图5-4冒泡法排序的N-S流程图排序过程示例（设N=8）:每趟只将方括号中的数据从左向右两两比较，让较大者不断“后沉”到方括号外。假设原始数据4938659776132749第一趟排序后3849657613274997第二趟排序后3

7、849651327497697第三趟排序后3849132749657697第四趟排序后3813274949657697第五趟排序后1327384949657697第六趟排序后1327384949657697第七趟排序后1327384949657697最后排序结果1327384949767697参考源代码:/* 例 5-4 , 5-4_2.cpp */#include <stdlib.h> #define N 10void main()/*输入N个原始数据*/int aN, t, i, j;for ( i = 0; i < N; i+ )cin>> ai;for (

8、 i = 0; i < N -1; i+ )/*本循环完成排序*/for ( j = 0; j < N - i; j+ )/* xi与它后边所有元素逐一比较，大则交换*/if ( aj > aj + 1)/*输出排序后的数组 */( temp = aj; aj = aj + 1; aj + 1 = temp; for ( i = 0; i < N; i+ )cout<< " t" << ai;system( "pause");三、定位与插入【例5-5】 输入一个数，插入到某升序一维数组中，使插入后的数组仍然

9、升序。如设原数组 x6 : -123,-2,2,15,23,45。假设待插入的新数为7，则该数应插入到数 2与15之间，数组长度增加1。插入后的数列为 x7 : -123,-2,2,7,15,23,45。【简要分析】先将a置于数组最后，然后将 a与它前边的元素逐一比较，如果 a小于 某元素xi,则后移xi 一个位置，否则将 a置于xi+1的位置，结束。x0 x1 x2 x3 x4 x5 x6-123, -2, 2, 15, 23, 45,7/* 设 x6=7 */-123, -2, 2, 15, 23,45, 45/* x5后移一个位置 */-123, -2, 2, 15,23, 23,45

10、/* x4后移一个位置 */-123, -2, 2,15, 15,23, 45 /* x3后移一个位置 */-123, -2, 2,7, 23, 45, 65 /* a>x2,将a赋给x3 */用自然语言描述的程序逻辑为： 设置环境，定义变量。输出原始数组x和待插入的新兀素a o 先假设新数a是最大的，作为数组的最后一个元素xN-1。 若 av xi(i=N-2,N-3,N-4,0),则后移 xi: xi xi+1，转;否则a到位：ar xi+1,转。 i自减1,转。输出新x数组，结束。参考源代码：/* 例 5-5 , 5-5.cpp */#include <stdlib.h>

11、;#define N 7void main()(int xN = (-123, -2, 2, 15, 23, 45, i, k, a;for ( i = 0; i < N - 1; i+ )cout<< "t" << xi;cout<< "n请输入待插入的新数a:");cin>> a;xN - 1 = a;for ( i = N - 2; i >= 0; i-)if ( a < xi)xi + 1 = xi;else(xi + 1 = a; break; for ( i = 0; i &l

12、t; N; i+ )cout<< "t" << xi;system( "pause");【思考验证】本例难点有二，其一定位该在什么位置查找；其二插入前怎样腾出一个空位(将指定位置开始的各元素依次后移)。这个算法与排队类似：设有10名同学已按身高排成一排，现要插入一名新同学进去，办法就是先找好位置，把这个位置以后的同学往后挪动一个位置，再让新同学站进去。 注意最先挪动位置的同学是最后的那个同学！下边的代码能否完成同样的工作？#include <stdlib.h>void main()int x11 = -123, -2,

13、 2, 15, 23, 45, 65, 99, 123, 344;int i, k, a;for ( i = 0; i < 10; i+ )cout<< "" << xi;/* 输出原数组 */cout<< "nPlease a:"cin>> a; /*输入待插入元素*/k = 9;for ( i = 0; i < 10; i+ )if ( a < xi ) k = i; break; if ( k = 9 ) x10 = a;elsefor ( i = 9; i >= k; i-

14、)xi+1 = xi;/*定位k */* a放在最后*/* a不是最后一个元素*/*从xk开始后移*/xk = a;/* a作为第k个元素*/for ( i = 0; i < 11; i+ )/*输出新数组*/cout<< "" << xi;system( "pause");【模仿训练】输入一个数，插入到降序一维数组中，使插入后的数组仍然降序。四、查找与删除【例5-6】 假定某数组已经存放有互不相同的正整数。现从键盘输入一个数，要求从 数组中删除与该值相等的元素，并将其后的元素逐个向前递补，并将最后一个元素置0。输出删除后的

15、数组。如原数组中无此数，则输出“无此数”。【简要分析】从数组中删除一个元素主要做两个工作：定位与移动。定位指确定被删除元素的位置；移动指某元素被删除后，跟在它后边的元素将逐个“向前递补”。设一标志变量flag，其作用是表示原数组中是否存在用户要删除的元素。用 N-S流程图描述的程序逻 辑如图5-5所示，变量表见表 5-3 ,。定义并初始化数组aN,整型变量i,at，标志变量flag=0输出原始a数组输入要删除的整数x如果x等于某ai，则flag=1 , at=i是否flag=0?输出：无此数！将各ak+1前移一个位置：ak ak+1 , k=at N-1输出排序后的a数组结束图5-5例5-6的

16、N-S流程图表5-3 例5-6的变量表变量名作用类型值x数组存放原始数据int已知i数组下标int0,9a待删除的元素int键盘输入ka在x数组中的位置int由a确定flaga是否包含在x中的标记int0,1参考源代码：/* 例 5-6 , 5-6.cpp */#include <stdlib.h>void main()int x10 = 1,2, 3, 4, 5, 6, 7, 8, 9, 10, i, a, k, flag;for ( i = 0; i < 10; i+ )cout<< "" << xi;cout<<

17、"n请输入要删除的数:");cin>> a;flag = 0;/*设原数组中不包含被输入的元素*/for ( i = 0; i < 10; i+ )if ( xi = a ) k = i; flag = 1; break; if ( flag = 0 )/* x 数组中包含 a */cout<< n 无此数！ "； exit(0);if ( k = 9 )x9 = 0;/* a刚好是x的末尾元素 */else/* a不是x的末尾元素 */(for ( i = k; i < 9; i+ )xi = xi + 1;/* x各元素向前

18、递补*/xi = 0;/* x最后元素置 0 */for ( i = 0; i < 10; i+ )cout<< "" << xi;system( "pause");【思考验证】当要删除的数在数组中多次出现时，要求全部删除之。请修改本例。【模仿训练】产生N个互不相同的两位自然数放于数组xN中。(设N<90)五、统计【例5-7】 随机产生N个09以内的数字，分别统计每个数字出现的次数。【简要分析】对本例，最容易想到的方法是用if语句逐一判断，10种情况分别计数,当然，这样将需要 10个计数变量和9个if语句！“程序弄巧”，巧是编程功