1. 选择排序

1.1. 原理

选择排序的原理很简单，首先在未排序数组中选出最小元素放在数组第一个位置，然后现在数组从第二个元素开始处于未排序状态，所以继续在这个范围内寻找最小元素并放在第二个位置，以此类推。

1.2. 实现细节

用minIndex记录每一轮查找过程中最小元素的下标，通过不断比较元素大小来不停更改minIndex的值直到最后找到每轮的最小元素。

1.3. 代码

#include <stdio.h>

void swap(int* i, int* j) {
    int tmp = *i;
    *i = *j;
    *j = tmp;
}

void select_sort(int* arr, int size) {
    int i = 0, j = 0, minIndex = 0;
    for(i = 0; i<size-1; i++) {
        minIndex = i;
        for(j = i+1; j<size; j++) {
            if(arr[j] < arr[minIndex])
                minIndex = j;
        }
        if(minIndex != i) 
            swap(&arr[i], &arr[minIndex]);
    }

}

int main(int argc, char const *argv[])
{
    int arr[] = {2, 4, 1, 7, 9, 3, 6, 5, 8};
    int i;
    select_sort(arr, sizeof(arr) / sizeof(int));
    for(i = 0; i<9; i++) 
        printf("%d\n", arr[i]);
    return 0;
}

2. 冒泡排序

2.1. 原理

在未排序数组中，先比较第一第二个元素的大小，将两个元素中的较大者放在第二个元素的位置，较小者放在第一个元素的位置，然后再比较第二第三个元素的大小，这个过程进行到数组末尾时，数组的最后一个元素就是整个数组的最大值。然后再进行上述过程依次得到剩下未排序数组中的最大值。

2.2. 代码

#include <stdio.h>

void swap(int* i, int* j) {
    int tmp = *i;
    *i = *j;
    *j = tmp;
}

void bubble_sort(int* arr, int size) {
    int i = 0, j = size-1;
    for(j = size-1; j>0; j--)
        for(i = 0; i < j; i++)
            if(arr[i] > arr[i+1])
                swap(&arr[i], &arr[i+1]);
}

int main(int argc, char const *argv[])
{
    int arr[] = {2, 4, 1, 7, 9, 3, 6, 5, 8};
    int i;
    bubble_sort(arr, sizeof(arr) / sizeof(int));
    for(i = 0; i<9; i++) 
        printf("%d\n", arr[i]);
    return 0;
}

3. 插入排序

3.1. 原理

插入排序的原理是，对于一个已经有序的数组，如果现在又来了一个数字要插入这个数组，我们要使这个数字插入到适当的位置使得新数组还是有序的。

3.2. 实现细节

我们把无序数组的第一个元素看作一个有序数组，然后依次让第二个第三个元素插入这个有序数组并保持该数组一直是有序的，这样依次插入所有元素最终就能得到一个有序数组。

3.3. 代码

#include <stdio.h>

void insert_sort(int* arr, int size) {
    int i, j;
    int tmp;
    for(i = 1; i<size; i++) {
        tmp = arr[i];
        for(j = i-1; j>=0&&arr[j]>tmp; j--) {
            arr[j+1] = arr[j];
        }
        arr[j+1] = tmp;
    }
}

int main(int argc, char const *argv[])
{
    int arr[] = {2, 4, 1, 1, 7, 9, 3, 6, 5, 8};
    int i;
    insert_sort(arr, sizeof(arr) / sizeof(int));
    for(i = 0; i<9; i++) 
        printf("%d\n", arr[i]);
    return 0;
}