1.直接插入排序

        1.1将数组分为有序和无序部分 无序部分插入到有序部分4

#include<iostream>
using namespace std;
void InsertSort(int a[], int n) {
    int tmp;
    int j;
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            tmp = a[i];
            for ( j = i - 1; j >= 0 && tmp < a[j]; j--) {
                a[j + 1] = a[j];
            }
            a[j + 1] = tmp;
        }
    }
}
void Print_a(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
}
int main() {
    int a[10] = { 1,9,2,8,3,7,4,6,5,10 };
    int n = sizeof(a) / sizeof(a[0]);
    InsertSort(a, n);
    Print_a(a, n);
    return 0;
}

希尔排序

#include<iostream>
using namespace std;
void ShellSort(int a[], int n) {
    int gap = n; 
    while (gap > 1) {
        gap = gap / 3 + 1;
        int i;
        for (int i = 0; i < n -gap; i++) {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0) {
                if (a[end] > tmp) {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else break;
            }
            a[end + gap] = tmp;
        }
    }
}
void print_a(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
}
int main() {
    int a[] = { 1,9,2,8,3,7,4,6,5,10 };
    int n = sizeof(a) / sizeof(a[0]);
    ShellSort(a, n);
    print_a(a, n);
    return 0;
}

简单选择排序

#include<iostream>
using namespace std;
void SelectSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int Min = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[Min]) {
                Min = j;
            }
        }
        if (Min != i) {
            swap(a[i], a[Min]);
        }
    }
}
void print_a(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
}
int main() {
    int a[] = { 1,9,2,8,3,7,4,6,5,10 };
    int n = sizeof(a) / sizeof(a[0]);
    SelectSort(a, n);
    print_a(a, n);
    return 0;
}