反转数组

#include <iostream>
# define N 9
using namespace std;
void inverse(int b[N]){
    for (int i = 0; i < N/2; ++i) {
        // 等同于交换变量的思想
        int temp = b[i];
        b[i] = b[N -1 - i];
        b[N -1 - i] = temp;
    }
}
int main()
{
    int a[N] = {6, 7, 2, 5, 4, 3, 6, 1, 9};
    // 反转数组
    inverse(a);
    // 输出数组
    for (int i = 0; i < N; ++i) {
        cout << a[i]<<"\t";
    }
}

冒泡排序

思想 :将相邻的两个数进行比较, 将小的调到前面

我们可以看到2这个最小值从最底下像冒泡一样冒到上面

#include <iostream>
# define C 6
using namespace std;
int count = 0;
// 冒泡排序: 比较相邻两个数, 小的调到前面
void bubble_sort(int a[], int n){
    // a[] 要排序的数组  n 为数组中元素个数
    // n - 1 一共启动了多少次 数组的整体全部两两交换
    for (int i = 0; i < n - 1 ; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            count ++;
            // 比较相邻两个数, 小的调到前面
            if(a[j] > a[j+1]){
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;}
        }
    }
}
int main()
{
    int a[C] = {8, 4, 9, 6, 5, 2};
    bubble_sort(a, C);
    cout<< "bubble_sort finised"<< endl;
    for (int i = 0; i < C ; ++i) {
        cout<< a[i]<< "\t";
    }
    cout<< "bubble_sort counts"<< endl;
    cout<< count<< endl;


}

冒泡排序是一种用时间换空间的算法, 如果有n个元素,那么需要执行的次数(n-1) + (n - 2) +... + 1 = n(n - 1) / 2 所以冒泡排序的时间复杂度O(N^2) , 举个栗子, N= 10^4, n(n - 1) / 2 和 10^8来讲, 大约是 0.5 * N^2的差距, O(N^2)表示的是数量级

选择排序

我们正常从头到尾扫描最小的数据, 将数据放到第一个位置, 在将剩余的数组中扫到第二小的值,放到第二个位置, 以此类推

#include <iostream>
# define C 6
using namespace std;
int count = 0;
// 冒泡排序: 比较相邻两个数, 小的调到前面
void select_sort(int a[], int n){
    int i, p, j, temp;
    for (i = 0; i < n -1; i++) {
        p = i; // p是记录最小值的下标,初始值是i的值
        for ( j = i+ 1; j < n; j ++) {
            if(a[j] < a[p]){
                p = j;// 记录每趟最小元素的下标
            }
        }
        if(p!= i){  // p索引如果等于 i位置的话就不用换了
            int temp = a[p];
            a[p] = a[i];
            a[i] = temp;
        }
    }

}
int main()
{
    int a[C] = {8, 4, 9, 6, 5, 2};
    select_sort(a, C);
    cout<< "select_sort finised"<< endl;
    for (int i = 0; i < C ; ++i) {
        cout<< a[i]<< "\t";
    }
    cout<< "select_sort counts"<< endl;
    cout<< count<< endl;

}