算法设计技巧二：分治算法（divide and conquer）

       算法设计的另一有效算法为分治算法，分治算法包括两步：

                1）分（divide）：递归解决较小的问题（当然基本情况除外）；

                2）治（conquer）：从子问题中构建原问题的解；

        可以看到，在之前的归并排序、快速排序、以及无向图深度优先搜索、有向图深度优先搜索等方法中，有效的应用的分的思想，但并未实现治的部分，因此，不能算作分治算法。即正文中至少含有两个递归调用的例程才能成为分治算法。

        分治算法的典型实例为最大子序列求和问题实现解。实现斐波拉契数列时使用递归可以看做是分治算法的一个糟糕的实例（通过非递归调用将更有效）。但这并不意味着分治算法总是很糟糕。在本篇将通过使用一般方法和分治算法求解最近点对问题，通过对比，证明分治算法的有效时间界。

分治算法的运行时间：

        分治算法存在从N-1步到第N步的递推表示：。举例常见的两种形式及其对应的解【证明略】。





 最近点对问题：

        给定平面上的一系列点，求解最近两点的距离及坐标。若点的数量为N,则存在N(N-1)/2个点对，使用一般方式，逐步比较最近点距离将花费时间，通过分治算法有望实现时间。

       分支算法实现步骤：

              1）点数小于等于3直接使用一般方法求解，点数大于3时将平面按x轴排序，取排序中点为分割线，将平面分割成YL和              YR两部分，递归求解YL和YR平面的最小距离left和right;,如果存在最近点对位于分割线内距离小于d,则对带状区域内的每一个点检测内的7个点，求解距离，则。图示如下：



最近点问题编程实现：

//main.cpp
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdlib>
#include<ctime>

using namespace std;
const int REPEAT = 100; //repeat REPEAT time to calcuate the time

class myPoint {
public:
    float x;
    float y;
};

//compare point a and b controlled by type
bool compare(myPoint a, myPoint b, int type) {
    if (type == 1) {
        return a.x > b.x;
    }
    else {
        return a.y > b.y;
    }
}
void Initial(int N, myPoint* X, myPoint* Y) {
    srand(time(0));  //get the system clock 
    int i;
    for (i = 0; i < N; i++) {  //generate the random value [-10, 10]
        X[i].x = rand() / double(RAND_MAX)*20 - 10;
        X[i].y = rand() / double(RAND_MAX)*20 - 10;
        Y[i].x = X[i].x;
        Y[i].y = X[i].y;
        cout << "The rand pair is : (" << X[i].x << ", " << X[i].y << " ) " << endl;
    }
}
double Distance(myPoint p1, myPoint p2) {  //calcuate the distance
    return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}

//quickSort the axis value controlled by type
void quickSort(myPoint* P, int start, int end, int type) {
    if (start == end)	//only one point
        return;
    int primary_start = start; 		//save the original start
    int primart_end = end;			//save the original end
    myPoint pivotKey = P[start]; 	//set pivotKey

    while (start < end)		//quickSort algrithm
    {	//find the right border
        while (start < end && compare(P[end], pivotKey, type))
        {
            end--;
        }
        //update the start
        if (start < end) {
            P[start++] = P[end];
        }
        //find the left border
        while (start < end &&  compare(pivotKey, P[start], type))
        {
            start++;
        }
        //update the end
        if (start < end) {
            P[end--] = P[start];
        }
    }
    //update pivotKey when start = end
    P[start] = pivotKey;
	
	//quickSort the left part
    if (start - 1>primary_start){
    	quickSort(P, primary_start, start - 1, type);
    }
	//quickSort the right part
    if (start + 1<primart_end){
    	quickSort(P, start + 1, primart_end, type);
    }
}

//direct solve the nearest points
double force(int start, int end, myPoint* P, myPoint& P1, myPoint& P2) {
    int i, j;
    if (end - start<1) {	//only one point
        return 0.0;
    }
    double minDis = Distance(P[start], P[start + 1]);  //init the minDis
    P1 = P[start];		//init P1
    P2 = P[start+1];	//init P2
    for (i = start; i <= end; i++) {
        for (j = start; j <= end; j++) {
            if (i != j && Distance(P[i], P[j])<minDis) {
                minDis = Distance(P[i], P[j]);
                P1 = P[i];
                P2 = P[j];
            }
        }
    }
    return minDis;
}

//divide_conquer algrithm for nearest points
double divide_conquer(int start, int end, myPoint* X, myPoint* Y, myPoint& P1, myPoint& P2) {

    if (end - start < 3){
        return force(start, end, X,P1,P2);
   }
   //divide
    int mid = (start + end) / 2; 
    int leftLen = 0, rightLen = 0, i, j; 
    myPoint* YL = new myPoint[(end - start + 1) ];//y left part
    myPoint* YR = new myPoint[(end - start + 1) ];//y right part
	//conquer
    for (i = 0; i <= end - start; i++){
        if (Y[i].x <= X[mid].x) {
            YL[leftLen++] = Y[i];
        }
        else {
            YR[rightLen++] = Y[i];
        }
    }
    double left = divide_conquer(start, mid, X, YL,P1,P2);	//find the left minDis
    myPoint leftP1 = P1;			//save P1
    myPoint leftP2 = P2;			//save P2
    double right = divide_conquer(mid + 1, end, X, YR,P1,P2);  //find the right minDis
    double minDis;
    //take the minDis from left and right, refill P1 and P2
    if (left < right) {
        minDis = left;
        P1 = leftP1;
        P2 = leftP2;
    }
    else {
        minDis = right;
    }
    //setup the danding region
    myPoint* newY = new myPoint[(end - start + 1)];
    int newYLen = 0;
    double leftBorder = X[mid].x - minDis;
    double rightBorder = X[mid].x + minDis;
    //find the points in region
    for (i = 0; i <= end - start; i++) {
        if (Y[i].x >= leftBorder && Y[i].x <= rightBorder){
        	newY[newYLen++] = Y[i];
        }
    }
    //find the nearest 7 distance
    for (i = 0; i<newYLen; i++) {
        for (j = 1; j <= 7; j++) {
        	//keep the newY in region
            if ((i + j)<newYLen) {
                double dis = Distance(newY[i], newY[i + j]);
                if (dis < minDis) {
                    minDis = dis;
                    P1 = newY[i];
                    P2 = newY[i + j];
                }
            }
        }
    }
    delete YL;
    delete YR;
    delete newY;
    return minDis;
}
int main(){
    int N;
    cout << "Enter the total number of points :";
    cin >> N;
    //create X and Y(same as X) points set
    myPoint* X = new myPoint[N];
    myPoint* Y = new myPoint[N];
    int i;
    clock_t start, end;
    double ave = 0.0;
    double minDis = 0.0;
    myPoint P1, P2; //init the nearest points result
    Initial(N, X, Y);	//instantiation the X and Y
    for (i = 0; i < REPEAT; i++) {	//repeat REPEAT times
        start = clock();
        minDis += force(0, N - 1, X,P1,P2);
        end = clock();
        ave += (double)(end - start);
    }
    ave /= REPEAT;
    minDis /= REPEAT;
    cout << "force: minDis : " << minDis << " time loss : " <<ave<<" ms" << setw(4);
    cout << " Position：(" << P1.x << "," << P1.y << "),(" << P2.x << "," << P2.y << ")"<<endl;

    ave = 0.0;
    minDis = 0.0;
    for (i = 0; i < REPEAT; i++) {  
        start = clock();
        quickSort(X, 0, N - 1, 1);	//sort X axis
        quickSort(Y, 0, N - 1, 2);	//sort Y axis
        minDis+= divide_conquer(0, N - 1, X, Y,P1, P2);
        end = clock();
        ave += (double)(end - start);
    }
    ave /= REPEAT;
    minDis /= REPEAT;
    cout << "divide_conquer: minDis : " <<minDis<< " time loss : " << ave << " ms" << setw(4);
    cout << " Position：(" << P1.x << "," << P1.y << "),(" << P2.x << "," << P2.y << ")" << endl;
    delete[]X;
    delete[]Y;
    return 0;
}

实验结果：

N = 10时，直接求解稍快；



N= 50时， 分治算法稍快；



N=100时，分治算法明显更快；



       实验表明，在求解最近点对问题上，当点对数量较大时，分治算法具有更短的运行时间。在很大一类问题上，通过分支算法可以实现高效解法，如矩阵分块、多项式乘法等。

practice makes perfect ！ 

3.1 概述

对程序流程的描述称为算法（algorithm）
	
在程序中，程序的流程控制语句是用语句（statement）来实现的，它指定了表达式的计算次序。
	
程序流程控制包括：选择和循环
	
选择执行是指根据某个条件满足与否来决定是否执行某个语句
		
循环执行是指根据某个条件是否满足来决定是否重复执行某个语句
	
 

设计流程控制时，可先用程序流程图（flowchat）来对程序流程进行描述，然后用编程语言写出程序。
 

从语句的语法构成上，可分为简单语句与结构语句
	
简单语句：不包含其他语句的语句

		
表达式语句
			
无条件转移语句
			
空语句
		
		
结构语句：简单语句和结构语句按一定规则构造出来的语句
		
复合语句
			
选择语句
			
循环语句
		
	
 

C++中的语句
	
顺序执行语句
		
表达式语句、复合语句、空语句
		
		
选择执行语句
		
if语句、switch语句
		
		
循环执行语句
		
while语句、while-do语句、for语句
		
		
无条件转移语句
		
goto语句、break语句、contiune语句、return语句
		
		
数据定义语句（C++可以在数据定义时对其初始化，使得数据定义也包含操作
	
3.2 顺序执行

C++支持顺序执行的语句有：表达式语句、复合语句、空语句

 

3.2.1 表达式语句

在C++表达式的后面加上一个分号“；”就可以构成表达式语句（expression statement），常用语句包括：赋值、自增/自减、输入/输出、无返回值的函数调用等

 

1、从键盘输入一个数，然后输出该数的平方、立方以及平方根

void Expression::test1(){

double x;

cout<<"请输入一个数："<<endl;

cin>>x;

cout<<x<<"的平方是："<<x*x<<endl;

cout<<x<<"的立方是："<<x*x*x<<endl;

cout<<x<<"的平方根是："<<sqrt(x)<<endl;

}

 

2、计算a+2a+3a+...的前n项的和

void Expression::test2(){

 

int n;

double a;

cout<<"请输入首项:"<<endl;

cin>>a;

cout<<"请输入项数:"<<endl;

cin>>n;

cout<<"前n项的和为："<<(a+a*n)*n/2<<endl;

 

}

 

3.2.2 复合语句

复合语句（compound statement）是由一对花括号（{ }）括起来的一个或多个语句构成，又称为块（block）。复合语句的格式为：

{ <语句序列> }

复合语句主要用作结构语句的成分语句和函数体，注意花括号的配对问题

 

3.2.3 空语句

空操作在C++中用空语句实现，空语句的格式为：

；

空语句的作用是用于语法上需要一条语句的地方，而该地方又不需要做任何事

{

...

... goto end;

... ...

end: ; //空语句

}

 

注意：

在分号（；）的使用上，一些语言是作为语句之间的分隔符，语句本身不包含分号；C++中，分号作为语句的结束符，是语句的一部分

3.3 选择执行

选择控制（selection control）又叫分支（branching）控制，是通过if语句和switch语句实现的

 

3.3.1 if语句

 



1、从键盘中输入三个整数，输出最大数

#include<iostream>

using namespace std;

 

//从键盘中输入三个整数，输出最大数

void Selection::test1(){

 

inta,b,c;

cout<<"请输入三个整数，用\"空格或回车\"隔开:"<<endl;

cin>>a>>b>>c;

 

//cout<<"请输入第1个数："<<endl;

//cin>>a;

//cout<<"请输入第2个数："<<endl;

//cin>>b;

//cout<<"请输入第3个数："<<endl;

//cin>>c;

 

if(a>=b){

if(a>c){

cout<<"最大数为"<<a<<endl;

}else{

cout<<"最大数为"<<c<<endl;

}

}else{

if(b>c){

cout<<"最大数为"<<b<<endl;

}else{

cout<<"最大数为"<<c<<endl;

}

}

 

}



 

2、输入a、b、c，求一元二次方程ax^2+bx+c=0的实根

 

void Selection::test2(){

//输入a、b、c，求一元二次方程ax2+bx+c=0的实根

double a,b,c;

cout<<"请输入a、b、c的值，用\"空格或回车\"隔开:"<<endl;

cin>>a>>b>>c;

if((b*b-4*a*c)<0){

cout<<"该方程没有实数根"<<endl;

}elseif((b*b-4*a*c)==0){

cout<<"该方程有两个相等的实数根，x1=x2="<<-b/(2*a)<<endl;

}else{

cout<<"该方程有两个不相等的实数根，x1="<<(-b+sqrt(b*b-4*a*c))/(2*a)<<",x2="<<(-b-sqrt(b*b-4*a*c))/(2*a)<<endl;

}

 

}

 

 

3、输入三角形的三边长，判断其为何种三角形

 

void Selection::test3(){

double a,b,c;

cout<<"请输入a、b、c的值，用\"空格或回车\"隔开:"<<endl;

cin>>a>>b>>c;

boolab=Selection::cmpFloat(a,b);

boolbc=Selection::cmpFloat(b,c);

boolrt=((a*a+b*b==c*c)||(a*a==b*b+c*c)||(b*b==a*a+c*c));

if((a+b)>c&&(a+c)>b&&(b+c)>=a){

if((ab|bc)&&(ab&bc)==0){

cout<<"等腰三角形"<<endl;

}elseif(ab&bc){

cout<<"等边三角形"<<endl;

}elseif((bool)(ab|bc)&rt){

cout<<"等腰直角三角形"<<endl;

}elseif(rt){

cout<<"直角三角形"<<endl;

}else{

cout<<"三角形"<<endl;

}

}else{

cout<<"不是三角形"<<endl;

}

}

 

 

4、从键盘输入两个表示时刻的时间数据（时、分、秒），比较两个时刻的先后次序

 

void Selection::test4(){

int h1,h2,m1,m2,s1,s2;

cout<<"输入第一个时刻(时分秒)"<<endl;

cin>>h1>>m1>>s1;

cout<<"输入第二个时刻(时分秒)"<<endl;

cin>>h2>>m2>>s2;

if(0<=h1&&h1<=24&&0<=m1&&m1<=60&&s1>=0&&s1<=60&&0<=h2&&h2<=24&&0<=m2&&m2<=60&&s2>=0&&s2<=60){

if(h1>h2){

cout<<"第二个时刻在前"<<endl;

}elseif(h1<h2){

cout<<"第一个时刻在前"<<endl;

}elseif(m1>m2){

cout<<"第二个时刻在前"<<endl;

}elseif(m1<m2){

cout<<"第一个时刻在前"<<endl;

}elseif(s1>s2){

cout<<"第二个时刻在前"<<endl;

}elseif(s1<s2){

cout<<"第一个时刻在前"<<endl;

}

}else{

cout<<"输入时刻不正确"<<endl;

}

 

}

 

if-else配对规则：“else子句与前面最近的，没有else子句的if配对”

 

 

3.3.2 switch语句

switch语句又称（开关语句），格式如下：

 

switch （<整型表达式>）{

case <整型常量表达式1>：<语句序列1>

case <整型常量表达式2>：<语句序列2>

... ...

case <整型常量表达式n>：<语句序列n>

[default：<语句序列n+1>]

 

}

 

1、从键盘输入一个星期的一天（0:星期天，1:星期一，···），然后输出对应的英文

void Selection::test5(){

int a;

cout<<"输出数字（0～6）:"<<endl;

cin>>a;

cout<<"a="<<a<<endl;

switch(a){

case 0:cout<<"Sunday"<<endl;

break;

case 1:cout<<"Monday"<<endl;

break;

case 2:cout<<"Tuesday"<<endl;

break;

case 3:cout<<"Wednesday"<<endl;

break;

case 4:cout<<"Thursday"<<endl;

break;

case 5:cout<<"Friday"<<endl;

break;

case 6:cout<<"Saturday"<<endl;

break;

default:cout<<"inputerror"<<endl;

break;

}

}

 

注意：1、当输入为首字符不为数字的字符串时，C++默认转为int值为0。如：df、er32等

   2、当输入首字符为数字的字符串时，C++将其转为int时，保留首字符数字。如2er转为2、43rf3转为43等

 

2、计算某年某月的天数

void Selection::test6(){

 

//计算某年某月的天数

intyear,month;

cout<<"输入年份月数"<<endl;

cin>>year>>month;

switch(month){

case 2:

if((year%4==0||year%400==0)&&year%100!=0){

cout<<year<<"年"<<month<<"月共29天"<<endl;

}else{

cout<<year<<"年"<<month<<"月共28天"<<endl;

}

break;

case 1:case 3:case 5:case 7:case 8:case 10:case 12:

cout<<year<<"年"<<month<<"月共31天"<<endl;

break;

case 4:case 6:case 9:case 11:

cout<<year<<"年"<<month<<"月共30天"<<endl;

break;

}

 

}



3.4 循环（重复）执行

3.4.1 迭代与穷举

代码的重复执行机制一般有两种：循环和递归

循环（loop）是指重复执行一组语句知道某个条件满足（或不满足）为止。由四部分组成：

循环初始化——用于为重复执行的语句提供初始数据
	
循环条件——描述了重复操作需要满足的条件
	
循环体——要重复执行的语句
	
下一次循环准备——为下一次循环更新数据
 

循环控制可实现问题求解的迭代法和穷举法

迭代法：对待问题先指定一个近似的初始解，然后按照某种规则基于这个初始解计算出下一个近似解，知道某个条件满足后得到最终解。如求n！
	
穷举法：对所有“可能”的解逐一去验证它是否满足条件，满足条件则它是一个解，否则它不是解。
 

C++提供三种循环语句：while、do-while、for语句。三种循环语句是等价的，用一种循环语句表示的操作一定能用其他两种循环语句表示出来。

 

循环分为两大类：计数控制的循环（counter-controller loop）和事件控制的循环（evnet-controller loop）

计数控制的循环：对循环次数进行计数，重复执行循环体直到指定的次数，用for语句表达
	
事件控制的循环：循环前不知道循环次数，循环的终止是由循环体满足结束条件引起的，又称条件控制循环（conditional loop），用while或do-while语句实现
如果循环体至少执行一次，用do-while实现。

有时

 

3.4.2 while语句

while（<表达式>） <语句>

3.4.3 do-while语句

do<语句>while（<表达式>）

3.4.4 for语句

for（<表达式1>；<表达式2>；<表达式3>）<语句>

 

1、求n！

void Loop::test1(){

//求n！

int n,m,sum;

cout<<"输入n的值:"<<endl;

cin>>n;

//保存输入的值

m=n;

//保存结果

sum=1;

 

//使用while实现

while(n>0){

sum=n*sum;

n--;

}

 

//使用for实现

for(inti=1;i<=n;i++){

sum=sum*i;

}

 

//使用do-while实现

do{

sum=n*sum;

n--;

}while(n>0);

 

cout<<m<<"!="<<sum<<endl;

}



2、计算从键盘输入的一系列整数的和，要求首先输入整数的个数

void Loop::test2(){

int n,num,sum=0;

cout<<"输入整数的个数："<<endl;

cin>>n;

for(int i=0;i<n;i++){

cout<<"请输入第"<<i+1<<"个数："<<endl;

cin>>num;

sum=sum+num;

}

cout<<"这"<<n<<"个数的和为："<<sum<<endl;

 

}

 

3、计算从键盘输入的一系列整数的和，要求输入以0结束

void Loop::test5(){

 

//计算从键盘输入的一系列整数的和，要求输入以0结束

ints um=0,n;

cout<<"请输入若干整数（以0结束）:"<<endl;

do{

cin>>n;

//cout<<"n为："<<n<<endl;

sum=sum+n;

}while(n!=0);

cout<<"和为："<<sum<<endl;

 

}

 

 

 

4、从键盘接受字符，一直到输入字符y（Y）或n（N）为止

 

void Loop::test6(){

 

//从键盘接受字符，一直到输入字符y（Y）或n（N）为止

//charn[]={};

charc;

//strings="";

cout<<"请输入若干字符:"<<endl;

do{

cin>>c;

cout<<"c为："<<c<<endl;

//s=s.append(to_string(n));

}while(c!='y'&&c!='Y'&&c!='n'&&c!='N');

//cout<<s<<endl;

}



 

5、判断键盘输入的一个整数是否为素数

 

void Loop::test7(){

 

//判断键盘输入的一个整数是否为素数

intn;

boolisPrime=true;

cout<<"输入一个整数："<<endl;

cin>>n;

if(n==0||n==1){

isPrime=false;

}else{

for(inti=2;i<n;i++){

if((n%i)==0){

isPrime=false;

break;

}

}

}

if(isPrime){

cout<<n<<"为素数"<<endl;

}else{

cout<<n<<"不为素数"<<endl;

}

 

 

}

 

 

6、求第n个斐波那契（Fibonacci）数

Fibonacci数定义如下：

𝑓𝑖𝑏(𝑛)1(𝑛=1)1(𝑛=2)𝑓𝑖𝑏𝑛−2+𝑓𝑖𝑏(𝑛−1)(𝑛≥3)

 

void Loop::test8(){

intn,f1=1,f2=1;

cin>>n;

if(n==1||n==2){

cout<<"第"<<n<<"个斐波那契数为1"<<endl;

}else{

for(inti=3;i<=n;i++){

inttmp=f1+f2;//计算新的斐波那契数

f1=f2;//记住前一个斐波那契数

f2=tmp;//记住新的斐波那契数

}

cout<<"第"<<n<<"个斐波那契数为"<<f2<<endl;

}

}



	//递归
int Function::fib(int n){
if(n==1||n==2){
	return 1;
}else{
	return fib(n-2)+fib(n-1);
	}
}


 

7、用牛顿迭代法求3a

𝑥𝑛+1=13(2𝑥𝑛+𝑎𝑥𝑛2)，当｜xn+1-xn｜<ℇ(10-6)时，xn+1即为3a的值

 

 

void Loop::test9(){

 

const double EPS=1e-9;

double a,x1,x2;

cout<<"请输入一个数："<<endl;

cin>>a;

x2=a;

do{

x1=x2;

x2=(2*x1+a/(x1*x1))/3;

}while(fabs(x2-x1)>=EPS);

cout<<a<<"的立方根是"<<x2<<endl;

 

}



 

 

 

8、输出小于n的所有素数

 

void Loop::test10(){

 

//输出小于n的所有素数

int n,count=1;

cout<<"请输入一个数："<<endl;

cin>>n;

if(n<=2){

cout<<"输入错误。"<<endl;

}

cout<<2<<",";//输出第一个素数

for(int i=3;i<n;i+=2){//循环，分别判断3、5、7、是否为素数

int j=2,k=sqrt((double)i);//取i的平方根

while((j<=k) && i%j!=0){

j++;

}

if(j>k){

cout<<i<<",";

count++;

if(count%6==0){

cout<<endl;

}

}

}

 

}

 

 

9、求级数1+x+x2/2！+...+xi/i！···前n项之和

 

void Loop::test11(){

 

double x;

int n;

cin>>x>>n;

double item=x,sum=1+x;

for(inti=2;i<n;++i){

item *= x/i;

sum += item;

}

cout<<"x="<<x<<",n="<<n<<",sum="<<sum<<endl;

 

}

3.5 无条件转移

3.5.1 goto语句

goto <语句标号>；

含义：转向带有相应<语句标号>的语句
	
goto语句的使用可分为两类：向前的转移（forward）和往回的转移（backward）
	
向前的转移隐含的是分支结构，可用if语句实现
		
往回的转移隐含着循环，可用循环语句实现
	
	
理论上，所有程序都可以不用goto语句实现，保留goto的原因：
	
早期的程序流程控制大多采用goto和if语句来实现
		
某些情况下使用goto语句会带来便利（从多层内层循环跳到外层循环等）
	
 

1、用goto语句求n!

void Loop::test3(){

int n;

cin>>n;

int i=1,f=1;

loop:

f*=i;

i++;

if(i<=n){

goto loop;

}

cout<<"factorialof"<<n<<"="<<f<<endl;

}



 

注意：

不能用goto语句从一个函数外部转入该函数的内部（函数体），也不能用goto语句从一个函数的内部转入该函数的外部。
	
goto语句不能掠过带有初始化的变量定义。
	
慎重使用goto语句，它会破坏程序的一些良好的性质
 

3.5.2 break语句

break；

含义：

	
结束switch语句的某个分支的执行；
		
退出包含它的循环语句
		
在循环体中使用break语句，立即跳出循环，break后面的语句也不再执行
			
对于多重循环，内层循环语句循环体中的break语句只能用于结束内层循环语句的执行；要结束外层循环，则可以用goto语句
		
	
 

3.5.3 contiune语句

continue;

只能在循环体中使用
	
含义：立即结束当前循环，准备进入下一次循环
	
continue语句的功能可以用goto语句和带标号的空语句来实现
 

2、从键盘输入一些非零整数，然后输出其中所有正数的平方根

 

void Loop::test4(){

int n;

double square_root;

cout<<"请输入若干整数（以0结束）"<<endl;

for(cin>>n;n!=0;cin>>n){

if(n<0)continue;

square_root=sqrt((double)n);

cout<<n<<"的平方根是"<<square_root<<endl;

}

}

 

 

注意：

continue与break的不同：continue只结束本次循环，break结束整个循环
	
continue与break的相同：循环体中continue后面的语句也将不再执行，并且continue语句一般也作为循环体中某个if语句的字句来使用
	
continue语句不是必须的，可以用循环语句实现；但有时会给循环体中的一些条件性动作带来便利
 

3.6 小结

   语句用于实现对程序执行流程的控制，一系列语句构成了程序的算法描述。
 

C++语句分为：简单语句和结构语句。

	
简单语句包括表达式语句、转移语句和空语句；
		
表达式语句由表达式加上一个分号“；”构成。常用的表达式语句是含有赋值、自增/自减、输入/输出以及函数调用等操作的表达式语句
			
转移语句包括break、continue和goto
			
break语句用于终止switch语句的一个分支或循环语句的循环操作
				
continue语句用于结束当前循环的执行，准备进入下一次循环
				
goto语句用于转向带标号的语句执行
			
			
空语句不做任何事情，其作用是用于语法上需要一条语句的地方，而该地方又不需做任何事情
		
		
结构语句包括复合语句、选择语句和循环语句
		
复合语句是由一对花括号“{}”括起来的一条或多条语句构成，又称为块（block）。在复合语句中，除了普通语句外，还可以包含局部数据的定义。
			
选择语句包括：if语句和switch语句
			
if语句（又称条件语句）是根据一个条件满足与否来决定是否执行某个语句或从两个语句中选择一个语句执行
				
switch语句（又称开关语句）是根据某个表达式的值在多组语句中选择一组语句来执行
			
			
循环（重复）语句是根据某个条件的满足与否来决定是否重复执行一组语句。
			
循环一般有四个部分组成：循环初始化、循环条件、循环体和下一次循环准备
				
循环可以分为两大类：计数控制的循环（一般用for语句实现）和事件控制的循环（用while或do-while实现）
			
		
	
 

程序设计风格通常是指对程序进行静态分析所能确认的程序特性，它涉及程序的易读性
 

结构化程序设计是指“按照一组能够提高程序易读性与易维护性的规则进行程序设计的方法”。一个结构化程序通常由三种语句构成：顺序、分支和循环，按结构化程序设计方法设计的程序具有良好的风格
3.4.2 递归

一个函数在其函数体中直接或间接调用了自己，该函数为递归函数（recursive function）

	
递归函数分为直接递归和间接递归
		
对递归函数的每一次调用都将产生一组局部变量，虽然它们名称相同，但它们是不同的变量，拥有不同的内存空间。递归调用可理解为函数的嵌套调用
	
	
“分而治之”的程序设计
	
定义递归函数时，要对两种情况进行描述：
		
一般情况（general case）：描述了问题的分解和综合过程，其中包含递归调用。
			
特殊情况（又称基础情况，base case）：指出问题求解的特例，在该情况下不需递归就能得到结果。
		
	
	
循环与递归的选择
	
循环与递归的异同
		
同：都可以实现重复操作
			
异
			
循环是在同一组变量上进行重复操作，因此循环有称为迭代；递归是在不同变量组上进行重复操作，这些变量组属于递归函数的不同实例
			
		
		
递归调用层次受栈空间的限制
		
递归是由函数调用实现的，函数调用需要开销。（可用动态规划技术（dynamic programming）解决）
		
分析递归算法的效率要考虑分解和综合两个方面的代价
		
循环实现的重复操作是一种归纳（递推）的过程，即从特殊情况到一般情况进行考虑；递归是一种演绎过程，是从一般情况到特殊情况设计的
	
递归函数应用实例
10、求两个正整数的最大公约数

法一：

 

int Function::gcd(int x,int y){

int d ;

d=(x<=y)?x:y;

while(d>1){

if(x%d==0&&y%d==0){

break;

}

d--;

}

return d;

}

//法二：辗转相除法（欧几里得算法）
int gcd(int x,int y){
	return(y==0)?x:gcd(y,x%y);
}


 

11、汉诺塔问题

void Function::hanoi(char x,char y,char z,int n){

if(n==1){

cout<<"1:"<<x<<"→"<<y<<endl;

}else{

hanoi(x,z,y,n-1);

cout<<n<<":"<<x<<"→"<<y<<endl;

hanoi(z,y,x,n-1);

}

 

}

课后答案（仅供参考）

1、将华氏度转为摄氏度

 

void Test::test1(){

 

double fahrenheit,degree;

cout<<"请输入华氏度："<<endl;

cin>>fahrenheit;

degree=5*(fahrenheit-32)/9;

cout<<fahrenheit<<"华氏度对应的摄氏度为："<<degree<<endl;

 

}

 

 

2、将24小时转为12小时

 

void Test::test2(){

int h1,m1;

cout<<"输入时分："<<endl;

cin>>h1>>m1;

if(h1<12){

cout<<h1<<":"<<m1<<"am"<<endl;

}else{

cout<<h1-12<<":"<<m1<<"pm"<<endl;

}

 

}

 

 

3、正向和逆向输出a～z

 

voidTest::test3(){

 

chara='a';

charz='z';

for(inti=0;i<=25;i++){

if(i==25){

cout<<a;

}else{

cout<<a<<",";

}

a++;

}

cout<<a<<endl;//{

for(inti=0;i<=25;i++){

if(i==25){

cout<<z;

}else{

cout<<z<<",";

}

z--;

}

cout<<z<<endl;//`

 

 

}

 

 

4、判断输入的正整数的位数，并输出

 

void Test::test4(){

 

intn,count=1;

cout<<"输入一个正整数："<<endl;

cin>>n;

for(inti=10;i<n*10;i=i*10){

int m=n/i;

if(m>0){

count++;

}

}

cout<<n<<"是"<<count<<"位数"<<endl;

 

}

 

 

5、对输入的一个算术表达式（以字符#结尾），检查其圆括号的配对情况，输出配对、多左括号、多右括号

 

voidTest::test5(){

 

intleft=0,right=0;

charc;

cout<<"输入一个算术表达式:"<<endl;

while(c!='#'){

cin>>c;

if(c=='{'){

left++;

}

if(c=='}'){

right++;

}

}

 

if(left==right){

cout<<"配对"<<endl;

}elseif(left>right){

cout<<"多左括号"<<endl;

}elseif(left<right){

cout<<"多右括号"<<endl;

}

}

 

 

6、输入一个字符串（以字符#结尾），对其中的'>='计数

 

voidTest::test6(){

 

//输入一个字符串（以字符#结尾），对其中的'>='计数

int count=0;

char ch1='\0',ch2;

cout<<"输入一串字符"<<endl;

while(ch2!='#'){

cin>>ch2;

if(ch2=='='&&ch1=='>'){

count++;

}

ch1=ch2;

}

//for(cin>>ch2;ch2!='#';cin>>ch2){

//if(ch2=='='&&ch1=='>'){

//count++;

//}

//ch1=ch2;

//}

cout<<">=个数："<<count<<endl;

 

}

 

 

7、计算圆周率

 

void Test::test8(){

double sum=0;

for(inti=1;(double)1/(2*i-1)>=1e-8;i++){

int n=1;

sum=sum+(double)1/(2*i-1)*n;

n=n*-1;

}

cout<<"pi="<<setprecision(100)<<4*sum<<endl;

}

 

8、计算邮费

 

voidTest::test7(){

 

doubleweight,distance;

cout<<"输入包裹重量和邮寄距离："<<endl;

cin>>weight>>distance;

if(weight<=0){

cout<<"输入错误"<<endl;

}else if(weight>0&&weight<=15){

cout<<"收费5元"<<endl;

}else if(weight>15&&weight<=30){

cout<<"收费9元"<<endl;

}else if(weight>30&&weight<=45){

cout<<"收费12元"<<endl;

}else if(weight>45&&weight<=60){

if(distance/1000<0){

cout<<"收费14元"<<endl;

}else{

cout<<"收费"<<14+(distance/1000)*1<<"元"<<endl;

}

}else if(weight>60){

if(distance/1000<0){

cout<<"收费15元"<<endl;

}else{

cout<<"收费"<<15+(distance/1000)*2<<"元"<<endl;

}

}

 

}

 

 

9、找出所有三位数，它们等于它们的各个数字的立方和（水仙花数）

 

voidTest::test9(){

 

for(inti=0;i<10;++i){

for(intj=0;j<10;++j){

for(intk=0;k<10;++k){

if(i*i*i+j*j*j+k*k*k==(i*100+j*10+k)&&((i*100+j*10+k)/100)>=1){

cout<<(i*100+j*10+k)<<"";

}

}

}

}

 

 

for(inti=100;i<1000;++i){

inta=i/100;

intb=i%100/10;

intc=i%10;

if(a*a*a+b*b*b+c*c*c==i){

cout<<a<<""<<b<<""<<c<<""<<i<<endl;

}

}

 

 

}

 

 

10、求输入a和b的公约数

 

void Test::test10(){

int a,b,i=2,count=1;

cout<<"输入ab的值"<<endl;

cin>>a>>b;

do{

if(a%i==0&&b%i==0){

count=i;

}

i++;

}while(i<=a||i<=b);

cout<<a<<"和"<<b<<"的最大公约数是："<<count<<endl;

}

 

 

11、1、2、5元货币，购买价值为n元的物品有多少种支付方式

 

voidTest::test11(){

 

int n,w=1;

cout<<"输入商品价格："<<endl;

cin>>n;

for(int i=0;i<=n;++i){

for(int j=0;j<=n/2;++j){

for(int k=0;k<=n/5;++k){

if(i+2*j+5*k==n){

cout<<"第"<<w<<"种支付方式:"<<"一元："<<i<<",二元："<<j<<",五元："<<k<<endl;

w++;

}

}

 

}

}

}

 

 

12、判断输入整数是否为回文数

 

void Test::test12(){

 

int n,reversedInteger=0,remainder,originalInteger;

cout<<"输入一个整数:"<<endl;

cin>>n;

originalInteger=n;

 

//翻转

while(n!=0)

{

remainder=n%10;

reversedInteger=reversedInteger*10+remainder;

n=n/10;

cout<<n<<""<<remainder<<""<<reversedInteger<<endl;

}

 

//判断

if(originalInteger==reversedInteger){

cout<<originalInteger<<"是回文数"<<endl;

}else{

cout<<originalInteger<<"不是回文数"<<endl;

}

}

 

 

13、输出十进制乘法表

 

void Test::test13(){

 

for(int i=1;i<10;++i){

for(intj=1;j<=i;++j){

cout<<i<<"*"<<j<<"="<<i*j<<"";

}

cout<<endl;

}

 

}

 

https://github.com/zzq1996/ProgrameDesign

参考：《程序设计教程：用C++语言编程》 陈家骏，郑滔

一.数据结构基础
1.数据结构概念
就是一组数据在内存中的存储形式，也是对基本数据类型的一次封装
也是数据对象中数据元素之间的关系。
算法与数据结构的区别：
数据结构只是静态的描述了数据元素之间的关系
高效的程序需要在数据结构的基础上设计和选择算法
程序=数据结构+算法
总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题的载体。
2.抽象数据类型(ADT)
就是将数据类型和数据类型上的运算捆在一起，进行封装，相当于类
3.算法效率的衡量
实现算法程序的执行时间可以反映出算法的效率
但是单纯依靠运行的时间来比较算法的优劣不一定是客观准确的
时间复杂度：
反应算法在时间上的效率
我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位，算法对于不同的机器环境而言，确切的单位时间是不同的，但是对于算法进行多少个基本操作在规模数量级上是相同的，因此可以忽略机器环境的影响客观的反应算法的时间效率。
“大O记法”表示算法的时间效率：
计算算法的基本操作的执行次数，为g(n)，使得算法处理规模为n的问题示例所用时间为T(n)=O(g(n))，则称O(g(n))为算法A的渐进时间复杂度，简称时间复杂度，记为T(n)。
理解“大O法”：对于算法的基本操作的执行次数，不用计算的太细致，最重要的是数量级和趋势，这个基本操作数量的规模函数中一些常量因子可以忽略不计。例如：
 和 
属于同一个数量级，他们的时间复杂度都是
级。
最坏时间复杂度(主要关注)：
算法完成工作最多需要多少基本操作
平均时间复杂度(比较全面)：
算法完成工作平均需要多少基本操作
时间复杂度的几条基本计算规则：
(1)基本操作，只有常数项。认为时间复杂度为O(1)
(2)顺序结构，时间复杂度加法计算
(3)循环结构，时间复杂度乘法计算
(4)分支结构，时间复杂度取最大值
(5)判断一个算法的效率时，往往只需要关注数量的最高次项，其他可以忽略。
(6)没有特殊说明的情况下，分析的都是最坏时间复杂度
list内置操作的时间复杂度：
dict内置操作的时间复杂度：
常见的时间复杂度之间的关系：
所消耗的时间的大小：
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

一个程序主要应该包括两方面内容:一个是对数据组织的描述，另一个则是对程序操作的描述。对数据组织的描述称为数据结构，而对程序操作的描述称为算法。因此有这样一个公式:数据结构+算法=程序。对于面向对象程序设计，强调的是数据结构，而对于面向过程程序设计，如C. Pascal. FORTRAN等语言，主要关注的是算法。

 

算法：解决一个问题的完整步骤描述。

五个特征:有穷、正确、可行、输入、输出。

三种基本结构:顺序、选择、循环

流程图：普通流程图    ；  N-S流程图

 

 

下面介绍排序算法：

为什么介绍排序算法呢？因为 排序是数据处理中的一种重要运算。在当今计算机系统中，花费在数据排序的时间占用了一部分系统运行的时间，所以研究并采用好的排序算法，能够提高工作效率是很重要的。

//选择排序
#include<stdio.h>
int main()
{
	int a[10];
	int i,j,k,m;
	printf("10 numbers:\n");
	for(i=0;i<10;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=0;i<9;i++)
	{
		k=i;
		for(j=i+1;j<10;j++)
			if(a[k]>a[j])
				k=j;
			if(k!=i)
			{
				m=a[i];
				a[i]=a[k];
				a[k]=m;
			}
	}
	printf("The sorted array is :  by the chosen method .\n  ");
	for(i=0;i<10;i++)
	{
		printf("%d  ",a[i]);
	}
	printf("\n");
 } 
//9 4 3 34 32 4 38 98 0 99



 

//堆排序
#include<stdio.h>
#define LENGTH 20

 递归方式构建大根堆(len是arr的长度，index是第一个非叶子节点的下标)
void adjust(int arr[],int len,int index)
{
	int left = 2*index + 1; // index的左子节点下表 
	int right = 2*index + 2;// index的右子节点下标 
	int temp;
	int maxIdx=index;
	if(left<len&&arr[left]>arr[maxIdx]) maxIdx=left;
	if(right<len&&arr[right]>arr[maxIdx])  maxIdx=right;
	if(maxIdx!=index)
	{
		temp=arr[maxIdx];
		arr[maxIdx]=arr[index];
		arr[index]=temp;
		adjust(arr,len,maxIdx);
	 } 
}
//堆排序
void heapSort(int arr[],int size)

{
	int i,temp;
	//构建大根堆（从最后一个非叶子节点向上） 
	for(i=size/2-1;i>=0;i--)
	{
		adjust(arr,size,i);
	}
	printf("the max heap:\n");
	for(i=0;i<size;i++)
	{
		printf("%d  ",arr[i]);	
	} 
	printf("\n");
	//调整大根堆
	for(i=size-1;i>=1;i--)
	{
		temp=arr[i];
		arr[i]=arr[0]; // 将当前最大的放置到数组末尾
		arr[0]=temp;
		adjust(arr,i,0);// 将未完成排序的部分继续进行堆排序
	 } 
 } 
 main()
 {
 	int b[LENGTH];
 	int i;
 	for(i=0;i<LENGTH;i++)
 	{
 		scanf("%d ",&b[i]);
	 }
	 printf("\n");
	 heapSort(b,LENGTH);
	 for(i=0;i<LENGTH;i++)
	 {
	 	printf("%d  ",b[i]);
	 }
	 return 0;
	 
 }

 

8 9 0 2 3 4 223 4 3 78 6767 9889 78 67 56 45 34 23 21 213 99



//冒泡排序
#include<stdio.h>
main()
{
	int a[10]; 
	int i,j,k;
	printf("10 numbers:\n");
	for(i=0;i<10;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=0;i<9;i++)//十个数进行九趟排序 
	{
		for(j=0;j<9-i;j++)
		{
			if(a[j]>a[j+1])
			{
				k=a[j];
				a[j]=a[j+1];
				a[j+1]=k;
			}
		}
	 }
	 printf("The sorted array is : by bubble.");
	for(i=0;i<10;i++)
	{
		printf("%d  ",a[i]);
	}
	printf("\n"); 
 } 



//quicksort
//对冒泡的改进 
#include<stdio.h>
#define N 10000
#include<time.h>
main()
{	
	clock_t begin,end;
	double cost;
	int p(int a[],int low,int high);
	void q(int a[],int low,int high); 
	int a[N];
	int i;
	//printf("please input 10 numbers.\n");
	int j=1000;
	begin=clock();
	for(i=0;i<N;i++)
	{
	//	scanf("%d",&a[i]);
	a[i]=j--;
	}
	
	q(a,0,N-1);
	end=clock();
	cost=(double)(end-begin);
	printf("The sorted array is :  by quicksort method .\n  ");
	for(i=0;i<N;i++)
	{
		printf("%d  ",a[i]);
	}
	printf("The cost is: %lf\n",cost); 
} 
int p(int a[],int low,int high)
{
	int key=a[low],p;
	while(low<high)
	{
		while(low<high&&a[high]>=key)
		{
			--high;
		}
		p=a[low];
		a[low]=a[high];
		a[high]=p;
		while(low<high&&a[low]<=key)
		{
			++low;
		}
		p=a[high];
		a[high]=a[low];
		a[low]=p;
	}
	a[low]=key;
	return low;
}
void q(int a[],int low,int high)
{
	int j;
	if(low<high)
	{
		j=p(a,low,high);
		q(a,low,j-1);
		q(a,j+1,high);
	}
}

 



 

 

//quicksort
//对冒泡的改进 
#include<stdio.h>
#define N 5000
#include<time.h>
main()
{	
	clock_t begin,end;
	double cost;
	int p(int a[],int low,int high);
	void q(int a[],int low,int high); 
	int a[N];
	int i;
	//printf("please input 10 numbers.\n");
	int j=1000;
	begin=clock();
	for(i=0;i<N;i++)
	{
	//	scanf("%d",&a[i]);
	a[i]=j--;
	}
	
	q(a,0,N-1);
	end=clock();
	cost=(double)(end-begin);
	printf("The sorted array is :  by quicksort method .\n  ");
	for(i=0;i<N;i++)
	{
		printf("%d  ",a[i]);
	}
	printf("\nThe cost is: %lf\n",cost); 
} 
int p(int a[],int low,int high)
{
	int key=a[low],p;
	while(low<high)
	{
		while(low<high&&a[high]>=key)
		{
			--high;
		}
		p=a[low];
		a[low]=a[high];
		a[high]=p;
		while(low<high&&a[low]<=key)
		{
			++low;
		}
		p=a[high];
		a[high]=a[low];
		a[low]=p;
	}
	a[low]=key;
	return low;
}
void q(int a[],int low,int high)
{
	int j;
	if(low<high)
	{
		j=p(a,low,high);
		q(a,low,j-1);
		q(a,j+1,high);
	}
}

 

 



OPENMP并行快排主要利用了OpenMP里面的#omp parallel sections将对两个子数组的快速排序函数用两个线程并行化执行，至于线程的创建和销毁我们不用管，只要告诉编译器哪里的代码需要并行执行就可以了，具体请看OpenMP资料。

//quicksort
//对冒泡的改进 
#include<stdio.h>
#include<time.h>
#include "omp.h"
#define N 5000
#pragma warning(disable:4996)
int main()
{	
	omp_set_num_threads(2);//----------------设置线程数为2，因为是双核的CPU
	double  cost;
	clock_t begin, end;
	int p(int a[], int low, int high);
	void q(int a[], int low, int high);
	int a[N];
	int b[N / 2];
	int c[N / 2];
	int d[N];
	int j = 1000;

	int i = 0,k = 0,m=0,n=0;
#pragma omp parallel default(none) shared(a,d,N) private(i)//private(list)表示每个线程的变量都是局部的，shared()表示的变量被线程组中所有线程共享，default（）定义缺省范围
	{	//---这个for循环是并行的  
#pragma omp for
		for (i = 0; i < N; i++)
	{
		a[i] = j;
		d[i] = j;
		j--;
	}
	}
	begin = clock();
#pragma omp parallel default(none) shared(a,b,c,N/2) private(i)//---这个for循环是并行的  
	{
#pragma omp for
		for (i = 0; i < N / 2; i++)
		{
			b[i] = a[i];
			c[i] = a[i + N / 2];
		}
	}
#pragma omp parallel default(none) shared(b,c,N/2)//private(i)------快速排序的并行region 
	{
#pragma omp parallel sections
		{
#pragma omp section
			q(b, 0, N/2 - 1);
			
#pragma omp section
			q(c, 0, N / 2 - 1);
		}
	}
	for (; k < N; k++)//----------将D[]和E[]进行归并排序放入B[]里面  
	{
		if (m < N / 2 && n < N / 2)
		{
			if (b[n] <= c[m])
			{
				d[k] = b[n];
				n++;
			}
			else
			{
				d[k] = c[m];
				m++;
			}
		}
		if (m == N / 2 || n == N / 2)
		{
			if (m == N / 2)
				d[k] = c[m];
			else
				d[k] = b[n-1];
			k += 1;
			break;
		}
	}
	if (n < N / 2)
	{
		int tem = N / 2 - n;
		int pp = 0;
		for (pp = 0; pp < tem; pp++)
		{
			d[k] = b[n];
			n++;
			k++;
		}
	}
	else if (m < N / 2)
	{
		int tem = N / 2 - m;
		int pp = 0;
		for (pp = 0; pp < tem; pp++)
		{
			d[k] = c[m];
			m++;
			k++;
		}
	}
	end = clock();
	printf("The sorted array is :  by quicksort method .\n  ");
	for (i = 0; i < N; i++)
	{
		printf("%d  ", d[i]);
	}
	cost = (double)(end - begin);
	printf("\n并行时间为:%lf\n",cost);
}
int p(int a[], int low, int high)
{
	int key = a[low], p;
	while (low < high)
	{
		while (low < high && a[high] >= key)
		{
			--high;
		}
		p = a[low];
		a[low] = a[high];
		a[high] = p;
		while (low < high && a[low] <= key)
		{
			++low;
		}
		p = a[high];
		a[high] = a[low];
		a[low] = p;
	}
	a[low] = key;
	return low;
}
void q(int a[], int low, int high)
{
	int j;
	if (low < high)
	{
		j = p(a, low, high);
		q(a, low, j - 1);
		q(a, j + 1, high);
	}
}

 

 

 



 

 

 

#include <iostream>
using namespace std;
#define LENGTH 20

//直接插入排序：将第一个数据看做一个顺序表，将后面的数据一次插入表中
void InsertSort(int a[], int n)  
{  
for(int i= 1; i<n; i++){  
     int j= i-1;   //表中最后一个数据
    int x = a[i];        //复制为哨兵，即存储待排序元素  
    while(j>=0 && x < a[j]){  //查找在有序表的插入位置  (遍历表)
        a[j+1] = a[j];  
        j--;         //元素后移  
    }  
    a[j+1] = x;      //插入到正确位置  
}  
  
} 

int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}

cout<<"\n";
InsertSort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}



 

 

基本思想是：希尔排序是在插入排序的基础上进行发展的，通过一个希尔增量先排序一定间隔的数据。待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

平均时间复杂度：O(N^3/2)

空间复杂度：O(1)

稳定性：不稳定

#include <iostream>
using namespace std;
#define LENGTH 20
void shellsort(int a[],int n) {  
for (int increment = n / 2; increment > 0; increment /= 2)
{
    for (int i = increment; i < n; i++)
    {
        int insert_num = a[i], j;
        for (j = i - increment; j >= 0; j -= increment)
        {
            if (a[j] > insert_num)
                a[j + increment] = a[j];
            else
                break;
        }
        a[j + increment] = insert_num;
    }
} 
}  
int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}
cout<<"\n";
shellsort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}