1.数组元素逆置

案例描述：请声明一个5个元素的数组，并且将元素逆置.
(如原数组元素为：1,3,2,5,4;逆置后输出结果为:4,5,2,3,1)
核心思路：
1.可以新建一个数组临时映射当前的数组
2.可以通过指向数组头节点的伪指针start以及指向末尾的 end,然后两个指针不断彼此靠近，即可实现逆置(注意考虑循环终止的条件)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//第一种思路关键代码
    int arr[5]={1,3,2,5,4};
    int arr1[5]={1,3,2,5,4};
    for(int i=0;i<=4; i++ ){
        arr[i]=arr1[4-i];
    }
    for(int j=0;j<=4;j++){
        cout<<arr[j]<<",";
    }
    cout << endl;
    return 0

//第二种思路
 int arr[5]={1,3,2,5,4};
    print(arr,5);  //打印当前数组的值

    int end = sizeof(arr)/sizeof(arr[0]) -1;
    int start=0;
    while(start < end){
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++ ; end--;  
    }
    print(arr,5);  //调用自定

2.冒泡排序

冒泡排序（排序算法，对数组中的元素进行排序）
过程：
1.比较相邻的元素，如果前者比后者大 则交换位置
2.对每一对相邻元素做相同的操作，每轮都会选出最大的一个数字放到最右边 ，即“冒泡”
3.对于n个元素最坏要进行 n-1+n-2+…+1次，

以{ 4,2,8,0,5,7,1,3,9 } 为例子，执行过程：

循环 数组 比较次数
0 2 4 0 5 7 1 3 8 9 8
1 2 0 4 5 1 3 7 8 7
2 0 2 4 1 3 5 7 6
3 0 2 1 3 4 5 5
4 0 1 2 3 4 4
5 0 1 2 3 3
6 0 1 2 2
7 0 1 1
8 0 （不计入循环） 0

总结（最坏时间复杂度）：
循环次数 == n-1;(因为每轮可以理解为弹出一个数，剩下最后一个的时候可以不用进行循环了)
每轮比较次数 == n-i(循环轮次，从0开始)-1
比较总次数 == 1+2+3+…+n-1 = pow(n,2) / 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
using namespace std;

void print(int arr[],int size){
  //对整数型数组进行输出，需要指定数组的size大小
  for(int i=0;i < size ;i++){
  cout << arr[i] <<" ";
  }
  cout <<endl; //这么写保证输出结果在同一行
}

int main()
{
    int arr[9]={ 4,2,8,0,5,7,1,3,9 };
    cout << "原数组:" << endl;
    print(arr,9);
  
    //核心算法代码
    for (int i = 0;i < 9-1;i++){ 
        //外层循环i
        for(int j = 0;j < 9-i-1;j++){
            if(arr[j] > arr[j+1]){
            int temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
            }
        }
    }
    cout << "冒泡排序后的数组：" <<endl;
    print(arr,9);
    return 0;
}