第二章程序设计基础知识

第二章程序设计基础知识

第一课程序基本常识

1.算法的特性

2.算法的复杂度

时间复杂度
空间复杂度

3.常见的时间复杂度

增长越快，复杂度越高
增长越慢，复杂度越低

4.练习

第一课程序基本常识

第二课 C++语言基础

1.数据类型

2.函数

3.递归函数

示例：

例如编写一求1+2+..+n的值，其中n<=20

#include <iostream>
using namespace std;
int add(int n){
    if(n==1) {
        return 1;
    }
    return add(n-1) + n;
    1 + 2 + 3
}
int main(){
    cout <<  add(4);
    return 0;
}

4.练习

第二课 C++语言基础

第三课排序算法

1.常见算法复杂度与稳定性

2.冒泡排序

小的元素会经由交换慢慢“浮”到顶端，就像泡泡一样，故名“冒泡排序”
它的工作原理是，重复地走访过要排序的元素，依次比较两个相邻的两个元素，如果前面的数比后面的数大就把他们交换过来。
走访元素的工作重复地进行，直到没有相邻元素需要交换

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 10;
int arr[SIZE] = {2,7,8,4,36,78,1,91,42,13};
int main(){
    for(int i = 0 ; i < SIZE - 1; i++){
        for(int j = 0 ; j < SIZE - 1 - i; j++){
            if(arr[j] > arr[j+1])
                swap(arr[j],arr[j+1]);
        }
    }
    for(int x : arr) cout << x << " ";
    return 0;
}

3.选择排序

从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置
然后再从剩余的未排序元素中寻找到最小元素，然后放到已排序的序列的后面

以此类推，直到全部待排序的数据元素的个数为零

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 10;
int arr[SIZE] = {2,7,8,4,36,78,1,91,42,13};
int main(){
  for(int i = 0 ; i < SIZE - 1; i++){
      for(int j = i ; j < SIZE; j++){
          if(arr[i] > arr[j])
              swap(arr[i],arr[j]);
      }
  }
  for(int x : arr) cout << x << " ";
  return 0;
}