数组

练习:五只⼩猪称体重 案例描述： 在⼀个数组中记录了五只⼩猪的体重，如：int arr[5] = {300,350,200,400,250}; 找出并打印最重的⼩猪体重。

#include <iostream>
using namespace std;
int main(){
    int arr[5] = {300,1350,200,400,250};
    int len = sizeof(arr)/sizeof(arr[0]);

    // 本质是求数组中自最大值的问题
    // 假设数组的第一个元素是最大的
    int maxWeight = arr[0];
    for (int i = 0; i < len; ++i) {
        if (arr[i] > maxWeight)
            maxWeight = arr[i];
    }
    cout<< maxWeight << endl;
}

• 数组元素逆置 案例描述：请声明⼀个5个元素的数组，并且将元素逆置. (如原数组元素为：1,3,2,5,4;逆置后输出结果为:4,5,2,3,1);

#include <iostream>
using namespace std;
int main(){
    int a = 100, b = 200;
    cout<< a << b << endl;
    int temp;
    temp = a;
    a = b;
    b = temp;
    cout<< a << b << endl;
    int arr[] = {1, 3, 5, 2, 4, 29, 47, 33};
    int len = sizeof(arr)/sizeof(arr[0]);
    for (int i = 0; i < len/2; ++i) {
        int temp;
        temp = arr[i];
        arr[i] = arr[len-1-i];
        arr[len-1-i] = temp;
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "\t";
    }
}

冒泡排序

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字
的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的
顶端，所以这个算法才被称为“冒泡排序”。

• 1. 比较相邻元素， 如果第一个比第二个大， 就交换他们两个
• 2. 对每一对相邻的元素做同样的工作， 执行完毕后， 找到第一个最大值
• 3. 重复以上步骤， 每次比较 次数 - 1， 直到不需要比较

#include <iostream>
using namespace std;
int main(){
    int arr[] = {5, 9, 3, 1, 2, 8, 4, 7, 6};
    int len = sizeof(arr)/sizeof(arr[0]);
    for (int j = len-1; j > 0; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "\t";
    }
    cout<< endl;
    cout<< "================================" << endl;

    for (int j = len-1; j > 1; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "\t";
    }
    cout<< endl;
    cout<< "================================" << endl;


    for (int j = len-1; j > 2; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "\t";
    }
    cout<< endl;
    cout<< "================================" << endl;

    for (int j = len-1; j > 3; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "\t";
    }
    cout<< endl;
    cout<< "================================" << endl;

    for (int j = len-1; j > 4; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "\t";
    }
    cout<< endl;
    cout<< "================================" << endl;

    for (int j = len-1; j > 5; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "\t";
    }
    cout<< endl;
    cout<< "================================" << endl;
    for (int j = len-1; j > 7; --j) {
        if (arr[j-1] > arr[j]){
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "\t";
    }
    cout<< endl;
    cout<< "================================" << endl;
}

#include <iostream>
using namespace std;
int main(){
    int arr[] = {5, 9, 3, 1, 2, 8, 4, 7, 6};
    int count = 0;
    int len = sizeof(arr)/sizeof(arr[0]);
    for (int i = 0; i < len -1; ++i) {
        for (int j = len-1; j > i; --j) {
            count++;
            if (arr[j-1] > arr[j]){
                int temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    for (int i = 0; i < len; ++i) {
        cout<< arr[i] << "\t";
    }
    cout<< endl;
    cout<<  count << endl;
}

选择排序（Selection-Sort）

先把最小的拿出来
剩下的， 再把最小的拿出来
剩下的， 再把最小的拿出来
。。。
每次选择还没处理的元素里最小的元素

选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”这一操作的算法。在序列中寻找最小值时使用的是线性查找。

比如: 对数字1~9进行排序。 使用线性查找在数据中寻找最小值，于是我们找到了最小值 1

• 一层版

#include <iostream>
using namespace std;
int main(){
    int arr[] = {6, 1, 7, 8, 9, 3, 5, 4, 2};
    int  len = sizeof(arr)/sizeof(arr[0]);
    int minIndex = 0;
    for (int j = 0; j < len; ++j) {
        if (arr[j] < arr[minIndex])
            minIndex = j;
    }
    cout<<"minIndex = "<< minIndex <<endl;
    // 交换
    int temp = arr[0];
    arr[0] = arr[minIndex];
    arr[minIndex] = temp;
    for (int i = 0; i < len; ++i)
        cout<<arr[i]<<"\t";
    cout<<endl;
    cout<<"-------------------------------"<<endl;
    cout<<"-------------------------------"<<endl;
    minIndex = 1;
    for (int j = 1; j < len; ++j) {
        if (arr[j] < arr[minIndex])
            minIndex = j;
    }
    cout<<"minIndex = "<< minIndex <<endl;
    // 交换
    temp = arr[1];
    arr[1] = arr[minIndex];
    arr[minIndex] = temp;
    for (int i = 0; i < len; ++i)
        cout<<arr[i]<<"\t";
    cout<<endl;
    cout<<"-------------------------------"<<endl;
    cout<<"-------------------------------"<<endl;

    minIndex = 2;
    for (int j = 2; j < len; ++j) {
        if (arr[j] < arr[minIndex])
            minIndex = j;
    }
    cout<<"minIndex = "<< minIndex <<endl;
    // 交换
    temp = arr[2];
    arr[2] = arr[minIndex];
    arr[minIndex] = temp;
    for (int i = 0; i < len; ++i)
        cout<<arr[i]<<"\t";
    cout<<endl;
    cout<<"-------------------------------"<<endl;
    cout<<"-------------------------------"<<endl;

}

最终版

#include <iostream>
using namespace std;

int main(){
    int arr[] = { 6, 1, 7, 8, 9, 3, 5, 4, 2};
    int len = sizeof(arr)/sizeof(arr[0]);

    for (int i = 0; i < len - 1; ++i) {
        int minIndex = i;
        for (int j = i; j < len; ++j) {
            if(arr[j] < arr[minIndex])
                minIndex = j;
        }
        // 小优化
        if (minIndex != i){
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    for (int i = 0; i < len; ++i) {
        cout << arr[i] <<"\t";

    }
    cout <<endl;





}