冒泡排序: 比较相邻, 然后交换

#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;


}

选择排序: 每次选最小的

#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;

}

选择排序的优化

#include <iostream>
# define C 6
using namespace std;
int count = 0;
// 选择排序: 每次选出一个值
void select_sort(int a[], int n){
    int i, j, temp;
    for (i = 0; i < n -1; i++) {
        // 选择的过程
        for ( j = i ; j < n; j ++) {
            if(a[i] > a[j]){
                temp = a[i]; a[i] = a[j]; a[j] = 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;
}

插入排序: 像扑克插入一样

#include <iostream>
# define C 6
using namespace std;
int count = 0;
// 插入排序
void ba_ins_sort(int a[], int n) {
    int p, j;
    for (int i = 1; i < n ; i++) {
            p = a[i];
        for ( j = i -1 ; j >= 0&&p < a[j] ; j--) {// 将比p大的元素依次右移一个位置
           a[j+1] =a[j];
        }
        a[j+1] = p;
    }
}
int main()
{
    int a[C] = {8, 4, 9, 6, 5, 2};
    ba_ins_sort(a, C);
    cout<< "ba_ins_sort finised"<< endl;
    for (int i = 0; i < C ; ++i) {
        cout<< a[i]<< "\t";
    }
    cout<< "ba_ins_sort counts"<< endl;
    cout<< count<< endl;
}

查找相关

顺序查找:从第一个一次开始找, 逐个元素与目标值进行比较

找到就返回这个元素

#include <iostream>
# define C 9
using namespace std;
int search(int a[], int n, int target){
    for (int i = 0; i < n; ++i) {
        if (a[i] == target){
            return i;
        }
    }
    return -1;
}
int main()
{
    int p;//找到目标值在数组中的索引
    int target = 555; // 要找的值
    int a[C] = {6, 3, 18, 24, 9, 32, 6, 46, 1};
    p = search(a, C, target);
    cout<< "array = "<< endl;
    for (int i = 0; i < C ; ++i) {
        cout<< a[i]<< "\t";
    }
    cout<< endl;
    if (p >= 0){
        cout<< "the target number index = "<< p <<  endl;
    } else{
        cout<< "not found" <<  endl;
    }
}

折半查找

#include <iostream>
# define C 10
using namespace std;
// 折半查找
int bin_search(int a[], int n, int target){
    int low=0 , mid , up = n -1 ; // 初始化 3个索引
    while (low<=up){
        mid = (low + up)/2;
        if(target == a[mid]){
            return mid;
        } else if(target<a[mid]){
                up = mid -1;
        }else{
            low = mid + 1;
        }
    }
    return  -1;

}
int main()
{
    int p;//找到目标值在数组中的索引
    int target = 6; // 要找的值
    int a[C] = {1, 3, 6, 24, 30, 32, 36, 46, 100, 120};
    p = bin_search(a, C, target);
    cout<< "array = "<< endl;
    for (int i = 0; i < C ; ++i) {
        cout<< a[i]<< "\t";
    }
    cout<< endl;
    if (p >= 0){
        cout<< "the target number index = "<< p <<  endl;
    } else{
        cout<< "not found" << p << endl;
    }
}