简单选择排序

笔记

每次从待排序的数组中选择最小的元素，直到所有元素排完

注意

是不稳定的排序

#include<bits/stdc++.h>

using namespace std;


/**
 * 简单选择排序
 * */
void select_sort(int a[], int len) {
    for(int i = 0; i < len-1; i++) {
        int minj = i;
        for(int j = i+1; j < len; j++) {
            if(a[j] < a[minj]) {
                minj = j;
            }
        }
        swap(a[i], a[minj]);
    }
}

int main() {
    int a[] = {9, 3, 1, 4, 2, 7, 8, 6, 5};

    int len = sizeof(a)/sizeof(a[0]);

    select_sort(a, len);

    for(int i = 0; i < len; i++) {
        printf("%d%c", a[i], " \n"[i==len-1]);
    }
    return 0;
}

冒泡排序

笔记

比较相邻的两个元素，如果顺序相反，那么就交换

注意

稳定排序

#include<bits/stdc++.h>

using namespace std;


/**
 * 冒泡排序
 * */
void bubble_sort(int a[], int len) {
    for(int i = 0; i < len-1; i++) {
        for(int j = i+1; j < len; j++) {
            if(a[i] > a[j]) {
                swap(a[i], a[j]);
            }
        }
    }
}

int main() {
    int a[] = {9, 3, 1, 4, 2, 7, 8, 6, 5};

    int len = sizeof(a)/sizeof(a[0]);

    bubble_sort(a, len);

    for(int i = 0; i < len; i++) {
        printf("%d%c", a[i], " \n"[i==len-1]);
    }
    return 0;
}

直接插入排序

笔记

将每个元素插入到已经排好的有序数组部分中

注意

稳定排序

#include<bits/stdc++.h>

using namespace std;


/**
 * 插入排序
 * */
void insert_sort(int a[], int len) {
    for(int i = 1; i < len; i++) {
        // 通过移动元素的方式插入
        int pre = i-1;
        int cur = a[i];
        while(pre >= 0 && cur < a[pre]) {
            a[pre+1] = a[pre];
            pre--;
        }
        a[pre+1] = cur;
    }
}
void insert_sort_swap(int a[], int len) {
    for(int i = 1; i < len; i++) {
        // 通过交换元素的方式插入
        int pre = i;
        while(pre > 0 && a[pre] < a[pre-1]) {
            swap(a[pre-1], a[pre])
            pre--;
        }
    }
}

int main() {
    int a[] = {9, 3, 1, 4, 2, 7, 8, 6, 5};

    int len = sizeof(a)/sizeof(a[0]);

    insert_sort(a, len);

    for(int i = 0; i < len; i++) {
        printf("%d%c", a[i], " \n"[i==len-1]);
    }
    return 0;
}

参考：

稳定排序和不稳定排序 (opens new window)

简单排序 (opens new window)

菜鸟教程-选择排序 (opens new window)